为什么简单的例子Haskell quicksort不是一个“真正的”quicksort？

Haskell的网站介绍了一个非常有吸引力的5行快速sortingfunction ，如下所示。

quicksort [] = [] quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater) where lesser = filter (< p) xs greater = filter (>= p) xs 

他们还包括一个“真正的C快速sorting” 。

 // To sort array a[] of size n: qsort(a,0,n-1) void qsort(int a[], int lo, int hi) { int h, l, p, t; if (lo < hi) { l = lo; h = hi; p = a[hi]; do { while ((l < h) && (a[l] <= p)) l = l+1; while ((h > l) && (a[h] >= p)) h = h-1; if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; } } while (l < h); a[hi] = a[l]; a[l] = p; qsort( a, lo, l-1 ); qsort( a, l+1, hi ); } } 

C版本下面的链接指向一个页面，该页面声明“引言中引用的快速sorting不是”真正的“快速sorting，并且不像c代码那样对较长的列表进行缩放。

为什么上面的Haskell函数不是真正的quicksort？ 它如何不能扩展更长的列表？

Answer 1

真正的quicksort有2个美丽的方面：

1. 分而治之; 把问题分解成两个小问题。
2. 分隔元素。

简短的Haskell示例演示了（1），但没有（2）。 如果你不知道这个技术，（2）如何做并不明显。

Answer 2

真正的Haskell inplace快速sorting：

 import qualified Data.Vector.Generic as V import qualified Data.Vector.Generic.Mutable as M qsort :: (V.Vector va, Ord a) => va -> va qsort = V.modify go where go xs | M.length xs < 2 = return () | otherwise = do p <- M.read xs (M.length xs `div` 2) j <- M.unstablePartition (< p) xs let (l, pr) = M.splitAt j xs k <- M.unstablePartition (== p) pr go l; go $ M.drop k pr 

Answer 3

这里是将“真正的”quicksort C代码转换成Haskell的代码。 振作起来。

 import Control.Monad import Data.Array.IO import Data.IORef qsort :: IOUArray Int Int -> Int -> Int -> IO () qsort a lo hi = do (h,l,p,t) <- liftM4 (,,,) zzzz when (lo < hi) $ do l .= lo h .= hi p .=. (a!hi) doWhile (get l .< get h) $ do while ((get l .< get h) .&& ((a.!l) .<= get p)) $ do modifyIORef l succ while ((get h .> get l) .&& ((a.!h) .>= get p)) $ do modifyIORef h pred b <- get l .< get h when b $ do t .=. (a.!l) lVal <- get l hVal <- get h writeArray a lVal =<< a!hVal writeArray a hVal =<< get t lVal <- get l writeArray a hi =<< a!lVal writeArray a lVal =<< get p hi' <- fmap pred (get l) qsort a lo hi' lo' <- fmap succ (get l) qsort a lo' hi 

那很有趣，不是吗？ 实际上，我在开始时删除了这个大的内容，以及函数末尾的位置，定义了所有的帮助器，使前面的代码有点漂亮。

  let z :: IO (IORef Int) z = newIORef 0 (.=) = writeIORef ref .=. action = do v <- action; ref .= v (!) = readArray (.!) a ref = readArray a =<< get ref get = readIORef (.<) = liftM2 (<) (.>) = liftM2 (>) (.<=) = liftM2 (<=) (.>=) = liftM2 (>=) (.&&) = liftM2 (&&) -- ... where doWhile cond foo = do foo b <- cond when b $ doWhile cond foo while cond foo = do b <- cond when b $ foo >> while cond foo 

在这里，一个愚蠢的testing，看看它是否工作。

 main = do a <- (newListArray (0,9) [10,9..1]) :: IO (IOUArray Int Int) printArr a putStrLn "Sorting..." qsort a 0 9 putStrLn "Sorted." printArr a where printArr a = mapM_ (\x -> print =<< readArray ax) [0..9] 

我不经常在Haskell中编写命令代码，所以我确信有很多方法可以清除这些代码。

所以呢？

你会注意到上面的代码非常非常长。 它的核心是和C代码一样长，尽pipe每一行往往有点冗长。 这是因为C秘密地做了很多令人讨厌的事情，你可能认为是理所当然的。 例如， a[l] = a[h]; 。 这访问可变variablesl和h ，然后访问可变数组a ，然后改变可变数组a 。 神圣的变种，蝙蝠侠！ 在Haskell中，突变和访问可变variables是显式的。 “假”qsort由于各种原因有吸引力，但其中主要是它不使用突变; 这种自我限制使得一眼就可以更容易理解。

Answer 4

在我看来，说这是“不是真正的快速sorting”夸大了案件。 我认为这是一个Quicksortalgorithm的有效实现，只是不是一个特别有效的。

Answer 5

我认为这个观点试图做的事情是，为什么quicksort常被使用的原因是它的就地和相当caching友好的结果。 由于Haskell列表没有这些好处，所以它的主要存在理由已经消失了，你还可以使用合并sorting来保证O（n log n） ，而使用快速sorting你必须使用随机或复杂的分区scheme在最坏的情况下避免O（n ² ）运行时间。

Answer 6

由于懒惰的评估，一个Haskell程序不（几乎不能 ）做它看起来像。

考虑这个程序：

 main = putStrLn (show (quicksort [8, 6, 7, 5, 3, 0, 9])) 

在一个渴望的语言，第一个quicksort会运行，然后show ，然后putStrLn 。 在函数开始运行之前计算函数的参数。

在Haskell中，情况恰恰相反。 该function首先开始运行。 参数只在函数实际使用时计算。 像列表一样，复合参数是一次一个地计算出来的，因为每一个参数都被使用了。

所以在这个程序中发生的第一件事就是putStrLn开始运行。

GHC的putStrLn实现通过将参数String的字符复制到输出缓冲区来工作。 但是当它进入这个循环时， show还没有运行。 因此，当它从string中复制第一个字符时，Haskell将计算show和计算该字符所需的quicksort的部分。 然后putStrLn移动到下一个字符。 因此，所有三个函数（ putStrLn ， show和putStrLn的执行都是交错的。 quicksort以递增方式执行，留下未经评估的thunk的graphics，以便记住它停留的位置。

现在，如果您熟悉任何其他编程语言，那么这与您所期望的大相径庭。 从内存访问甚至比较顺序的angular度来看，Haskell的实际行为是如何的不容易。 如果你只能观察行为，而不是源代码， 你不会意识到它是做什么的快速sorting 。

例如，C版本的quicksort在第一次recursion调用之前分割所有的数据。 在Haskell版本中，结果的第一个元素将在第一个分区运行完成之前计算出来（甚至可能出现在屏幕上），事实上，在任何工作完成之前，都是在greater范围内完成的。

PS如果Haskell的代码和quicksort做了相同数量的比较，那么Haskell代码会更快一些。 所写的代码执行两倍的比较，因为lesser和greater的指定是独立计算的，通过列表进行两次线性扫描。 当然，编译器原则上可以足够聪明以消除额外的比较; 或者代码可以改为使用Data.List.partition 。

PPS Haskellalgorithm的一个典型例子就是不像你预期的那样运行，就是Eratosthenes计算素数的筛选 。

Answer 7

我相信大多数人都认为漂亮的Haskell Quicksort不是“真正的”Quicksort的原因是它不在位 – 显然，使用不可变数据types时不能这样做。 但也有人反对说，它不是“快”：部分是因为昂贵的++，还有一个空间泄漏 – 你挂在input列表，而对较小的元素进行recursion调用，在某些情况下 – 例如，当列表正在减less时 – 这会导致二次空间使用。 （你可能会说，使它在线性空间中运行是最接近你可以使用不可变数据就地获得的。）对于这两个问题都有很好的解决scheme，使用累加参数，tupling和fusion。 请参阅Richard Bird“ 使用Haskell进行函数式编程入门”的 S7.6.1。

Answer 8

对于什么是非真正的快速sorting没有明确的定义。

他们称这不是一个真正的快速sorting，因为它不是在原地sorting：

在C中真正的快速sorting就地

Answer 9

在纯粹的function设置中，并不是将元素就地变换的想法。 这个线程可变的替代方法失去了纯洁的精神。

至less有两个步骤来优化快速sorting的基本版本（这是最具performance力的版本）。

1. 通过累加器优化连接（++），这是一个线性操作：

    qsort xs = qsort' xs [] qsort' [] r = r qsort' [x] r = x:r qsort' (x:xs) r = qpart xs [] [] r where qpart [] as bs r = qsort' as (x:qsort' bs r) qpart (x':xs') as bs r | x' <= x = qpart xs' (x':as) bs r | x' > x = qpart xs' as (x':bs) r 

2. 优化到三元快速sorting（由Bentley和Sedgewick提到的3路分区），以处理重复的元素：

    tsort :: (Ord a) => [a] -> [a] tsort [] = [] tsort (x:xs) = tsort [a | a<-xs, a<x] ++ x:[b | b<-xs, b==x] ++ tsort [c | c<-xs, c>x] 

3. 结合2和3，参考Richard Bird的书：

    psort xs = concat $ pass xs [] pass [] xss = xss pass (x:xs) xss = step xs [] [x] [] xss where step [] as bs cs xss = pass as (bs:pass cs xss) step (x':xs') as bs cs xss | x' < x = step xs' (x':as) bs cs xss | x' == x = step xs' as (x':bs) cs xss | x' > x = step xs' as bs (x':cs) xss 

或者，如果重复的元素不是多数：

  tqsort xs = tqsort' xs [] tqsort' [] r = r tqsort' (x:xs) r = qpart xs [] [x] [] r where qpart [] as bs cs r = tqsort' as (bs ++ tqsort' cs r) qpart (x':xs') as bs cs r | x' < x = qpart xs' (x':as) bs cs r | x' == x = qpart xs' as (x':bs) cs r | x' > x = qpart xs' as bs (x':cs) r 

不幸的是，三位数的中位数不能实现相同的效果，例如：

  qsort [] = [] qsort [x] = [x] qsort [x, y] = [min xy, max xy] qsort (x:y:z:rest) = qsort (filter (< m) (s:rest)) ++ [m] ++ qsort (filter (>= m) (l:rest)) where xs = [x, y, z] [s, m, l] = [minimum xs, median xs, maximum xs] 

因为以下四种情况仍然performance不佳：

1. [1，2，3，4，…，n]

2. [n，n-1，n-2，…，1]

3. [m-1，m-2，… 3,2,1，m + 1，m + 2，…，n]

4. [n，1，n-1,2，…]

所有这四个案例都是由命令式三位中立的方法处理的。

实际上，纯function设置的最合适的sortingalgorithm仍然是合并sorting，但不是快速sorting。

有关详情，请访问我的正在撰写的文章： https ： //sites.google.com/site/algoxy/dcsort

Answer 10

问任何人在Haskell编写快速sorting，你将得到基本相同的程序 – 这显然是快速sorting。 这里有一些优点和缺点：

Pro：它通过稳定性改进了“真正的”快速sorting，即它保留了相同元素之间的序列次序。

Pro：推广到三向分裂（<=>）是微不足道的，它避免了由于某个值出现O（n）次而导致的二次行为。

Pro：即使必须包含filter的定义，也更容易阅读。

Con：它使用更多的内存。

Con：通过进一步抽样来概括枢轴select是昂贵的，这可以避免对某些低熵sorting的二次行为。

Answer 11

因为从列表中获取第一个元素会导致非常糟糕的运行时间。 使用中位数3：第一，中间，最后一个。