我对Haskell很新,我对使用不纯(可变)数据结构可以提高性能有疑问.我正在尝试拼凑一些我听过的不同的东西,所以如果我的术语不完全正确,或者如果有一些小错误,请耐心等待.
为了具体化,请考虑快速排序算法(取自Haskell wiki).
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
这不是"真正的快速入门"."真正的"快速排序算法就位,但事实并非如此.这是非常低效的内存.
另一方面,可以在Haskell中使用向量来实现就地快速排序.这个stackoverflow答案给出了一个例子.
第二种算法比第一种算法快多少？Big O符号在这里没有用,因为性能的提高将来自更有效地使用内存,而不是更好的算法(对吧？).我厌倦了自己构建一些测试用例,但是我很难让事情运行起来.
理想的答案可以让我们了解在理论上使原位Haskell算法更快的原因,以及某些测试数据集上运行时间的示例比较.