是否可以只通过一次就对列表进行快速排序? [英] is it possible to do quicksort of a list with only one passing?
问题描述
我正在学习haskell,我看到的函数定义是:
I am learning haskell and the function definition I see is:
quickSort (x : xs) = (quickSort less) ++ (x : equal) ++ (quickSort more)
where less = filter (< x) xs
equal = filter (== x) xs
more = filter (> x) xs
是否可以只遍历列表一次而不是 3 次来编写它?
Is it possible to write it with only one traversal of the list, instead of 3?
推荐答案
虽然晚了,但这里的版本应该不会泄漏太多空间(并且似乎比其他 3 个版本快两倍-方式版本在这里):
Although late, here's a version that's supposed to not leak space as much (and seems to run about twice faster than the other 3-way version here):
qsort3 xs = go xs []
where
go (x:xs) zs = part x xs zs [] [] []
go [] zs = zs
part x [] zs a b c = go a ((x : b) ++ go c zs)
part x (y:ys) zs a b c =
case compare y x of
LT -> part x ys zs (y:a) b c
EQ -> part x ys zs a (y:b) c
GT -> part x ys zs a b (y:c)
这解决了使用元组可能存在的问题,其中 let (a,b) = ...
实际上被翻译成 let t= ...;a=fst t;b=snd t
这导致即使在 a
被消费和处理后,它仍然保持活动状态,作为元组 t
的一部分, 用于从它读取 b
- 尽管当然完全没有必要.这被称为Wadler 对空间泄漏"问题.或者也许 GHC(带有 -O2
)比这更聪明.:)
This addresses the possible problem with using tuples, where let (a,b) = ...
is actually translated into let t= ...; a=fst t; b=snd t
which leads to the situation where even after a
has been consumed and processed, it is still kept around alive, as part of the tuple t
, for b
to be read from it - though of course completely unnecessary. This is known as "Wadler pair space leak" problem. Or maybe GHC (with -O2
) is smarter than that. :)
此外,这显然使用了差异列表方法(感谢,hammar),这也使其效率更高(比使用元组的版本快大约两倍).我认为 part
使用累加器参数,因为它以相反的顺序构建它们.
Also this apparently uses difference lists approach (thanks, hammar) which also makes it a bit more efficient (about twice faster than the version using tuples). I think part
uses accumulator parameters, as it builds them in reversed order.
这篇关于是否可以只通过一次就对列表进行快速排序?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!