我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]
好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.
但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.
我正在编写一些一次性的Haskell脚本来解决Project Euler的一些问题.我真的不想编译它们,因为我经常要做的改变很多,但在少数情况下我发现我的堆栈空间已经用完了.
说明runhaskell以下语法应该增加堆栈空间的文档:
runhaskell +RTS -K5M -RTS Script.hs
这永远不会有效(在我试过的任何排列中).堆栈大小始终为8,388,608.这令人抓狂,我在Google上找不到多少帮助.
有什么建议？我究竟做错了什么？
如果我需要获取包含内存密集元素的大型列表的值,我对GHC抛出堆栈溢出感到有些惊讶.我确实预计GHC有TCO,所以我永远不会遇到这种情况.
为了最简化这个案例,请看下面返回Fibonacci数的函数的简单实现(取自HaskellWiki).目标是显示百万分之一的数字.
import Data.List
# elegant recursive definition
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
# a bit tricky using unfoldr from Data.List
fibs' = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)
# version using iterate
fibs'' = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)
# calculate number by definition
fib_at 0 = 0
fib_at 1 = 1
fib_at n = fib_at (n-1) + fib_at (n-2)
main = do
{-- All following expressions abort with
Stack …我的问题是,当使用Haskell中的任何Map实现时,我总是在使用一百万个值时得到"堆栈空间溢出".
我要做的是处理一对配对列表.每一对包含两个Ints(不是整数,我失败了,所以我尝试了Ints).我想浏览列表中的每一对,并使用第一个Int作为键.对于每个唯一键,我想构建第二个元素的列表,其中每个第二个元素都在一对中,具有相同的第一个元素.所以我最终想要的是从Int到Int列表的"Map".这是一个例子.
给出这样的对列表:
[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]
我想最终得到一个像这样的"地图":
{1 : [42,79,10], 2 : [11], 3 : [18,99]}
(我在上面使用类似Python的符号来说明"地图".我知道它不是Haskell.它仅用于说明目的.)
所以我尝试的第一件事是我自己手工制作的版本,我在其中排序了Ints对的列表,然后通过列表构建了一个新的对列表,但这次第二个元素是一个列表.第一个元素是键,即每对的第一个元素的唯一Int值,第二个元素是每个原始对的第二个值的列表,其中键作为第一个元素.
所以给出这样的对列表:
[(1,10),(2,11),(1,79),(3,99),(1,42),(3,18)]
我最终得到了一对像这样的对:
[(1, [42,79,10], (2, [11]), (3, [18,99])]
这很容易做到.但是有一个问题.原始列表(1000万对)中"排序"功能的表现令人震惊.我可以在不到一秒的时间内生成原始的对列表.我可以在不到一秒的时间内将已排序的列表处理到我手工制作的地图中.但是,对原始列表对进行排序需要40秒.
所以我想在Haskell中使用其中一个内置的"Map"数据结构来完成这项工作.我的想法是构建我的原始对列表,然后使用标准Map函数构建标准Map.
这就是梨形的地方.它在100,000个值的列表上运行良好但是当我移动到100万个值时,我得到"堆栈空间溢出"错误.
所以这里是一些遭遇问题的示例代码.请注意,这不是我想要实现的实际代码.它只是一个非常简化的代码版本,存在同样的问题.我真的不想将一百万个连续数字分成奇数和偶数分区!!
import Data.IntMap.Strict(IntMap, empty, findWithDefault, insert, size)
power = 6
ns :: [Int]
ns = [1..10^power-1]
mod2 n = if odd n then 1 else 0
mod2Pairs = zip (map mod2 ns) ns
-- Takes a list of pairs and returns a Map where the key is the unique Int values
-- …我提出了以下尾递归斐波纳契生成器:
let {
fibo :: Integral x => [x]->x->x->x->[x]
fibo l x y 0 = l
fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)
}
请原谅我把整个实现放在一行,因为我使用GHCi并且还没有完全学会如何把它放在一个文件中并运行(我还没到达那里).我想知道的是这个电话:
fibo [0, 1] 0 1 5
可以改进.我不想用0和1传递初始列表,然后再次使用限制传递0和1.我相信可以改变实施.可以做些什么改变？