为什么极简主义者 Haskell 快排不是“真正的”快排？

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

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

They also include a "True quicksort in C". 

// 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 版本下面的链接指向一个说明 简介中引用的快速排序并不是“真正的”快速排序，也不像 c 代码那样适用于较长的列表的页面

为什么上述哈斯克尔功能不是一个真正的快速排序? 为什么它不能扩展到更长的列表？

55968 次浏览
小开

因为从列表中取出第一个元素会导致非常糟糕的运行时。

小开

在我看来，说它“不是一个真正的快排”夸大了情况。我认为这是 快速排序算法的一个有效实现，只是不是一个特别有效的实现。

小开

什么是真正的快排，什么不是真正的快排，目前还没有明确的定义。

他们说这不是一种真正的快速排序，因为它不会就地排序:

在 C 中就地排序的真快排

小开
最佳答案

真正的快速排序有两个美丽的方面:

  1. 分而治之: 把问题分成两个较小的问题。
  2. 就地分区元素。

简短的 Haskell 示例演示了(1) ，但没有演示(2)。如果你还不知道这个技巧，那么(2)是如何完成的可能并不明显！

小开

I think the case this argument tries to make is that the reason why quicksort is commonly used is that it's in-place and fairly cache-friendly as a result. Since you don't have those benefits with Haskell lists, its main raison d'être is gone, and you might as well use merge sort, which guarantees O (n log n), whereas with quicksort you either have to use randomization or complicated partitioning schemes to avoid O (n < sup > 2 ) run time in the worst case.

小开

Here is a transliteration of the "true" quicksort C code into Haskell. Brace yourself.

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 (,,,) z z z z


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，在函数的结尾部分删除了 where，定义了所有的助手，使得前面的代码看起来有些漂亮。

  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

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

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 a x) [0..9]

我不经常在哈斯克尔写命令式代码，所以我相信有很多方法可以清理这些代码。

那又怎样？

您会注意到上面的代码非常非常长。它的核心大约是 C 代码的长度，尽管每一行通常有点冗长。这是因为 C 秘密地做了很多你认为理所当然的讨厌的事情。例如，a[l] = a[h];。它访问可变变量 l和 h，然后访问可变数组 a，然后对可变数组 a进行变异。神圣的变异，蝙蝠侠！在哈斯克尔，变异和访问可变变量是明确的。由于各种原因，“假的”qsort 很有吸引力，但其中最主要的原因是它不使用突变; 这种自我强加的限制使它更容易一目了然。

小开

返回文章页面哈斯克尔真正的快速排序:

import qualified Data.Vector.Generic as V
import qualified Data.Vector.Generic.Mutable as M


qsort :: (V.Vector v a, Ord a) => v a -> v a
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
小开

Ask anybody to write quicksort in Haskell, and you will get essentially the same program--it is obviously quicksort. Here are some advantages and disadvantages:

正方观点: 它通过稳定性改进了“真正的”快排，也就是说，它保持了相等元素之间的序列顺序。

正方: 将其推广到三向分裂(< = >)是很平凡的，它避免了由于某些值出现 O (n)次而导致的二次行为。

正方: 它更容易阅读——即使必须包括过滤器的定义。

缺点: 它使用更多的内存。

反对: 通过进一步抽样来推广支点选择是代价高昂的，它可以避免在某些低熵排序上的二次行为。

小开

我相信，大多数人认为漂亮的 Haskell Quicksort 不是“真正的”Quicksort 的原因是它不在适当的位置——显然，在使用不可变数据类型时它不可能在适当的位置。但是也有反对意见认为它不够“快”: 部分原因是昂贵的 + + ，还因为存在空间泄漏——在对较小的元素进行递归调用时，你保留了输入列表，在某些情况下——例如当列表减少时——这导致了二次空间使用。(您可能会说，使它在线性空间中运行是使用不可变数据最接近于“就地”的方法。)这两个问题都有简洁的解决方案，使用累积参数、元组和融合; 参见 RichardBird 的 使用 Haskell 的函数式编程简介的 S7.6.1。

小开

It isn't the idea of mutating elements in-place in purely functional settings. The alternative methods in this thread with mutable arrays lost the spirit of purity.

要优化快速排序的基本版本(最具表现力的版本) ，至少有两个步骤。

  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. Optimize to ternary quick sort (3-way partition, mentioned by Bentley and Sedgewick), to handle duplicated elements:

    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. Combine 2 and 3, refer to Richard Bird's book:

    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

Or alternatively if the duplicated elements are not the majority:

    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 x y, max x y]
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]

因为它在以下4种情况下仍然表现不佳:

  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，... ]

以上4例均采用强制性中位数法处理。

实际上，对于纯函数式设置，最合适的排序算法仍然是合并排序，但不是快速排序。

详情请访问我正在写的文章: Https://sites.google.com/site/algoxy/dcsort

小开

由于惰性评估，Haskell 程序(几乎是 不行)不会做它看起来像做的事情。

Consider this program:

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

在热切的语言，首先 quicksort将运行，然后 show，然后 putStrLn。函数的参数在该函数开始运行之前被计算。

在哈斯克尔，情况恰恰相反。函数首先开始运行。只有在函数实际使用参数时才计算参数。一个复合参数，就像一个列表，是一次计算一个部分，因为每一个部分都被使用。

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

GHC 的 putStrLn 实现通过将参数 String 的字符复制到输出缓冲区中来工作。但是当它进入这个循环时，show还没有运行。因此，当它从字符串中复制第一个字符时，Haskell 计算计算 那个角色所需的 show和 quicksort调用的分数。然后 putStrLn移动到下一个字符。因此，所有这三个函数的执行是交错的。quicksort以递增的方式执行，留下一个 show0的图来记住它停止的位置。

Now this is wildly different from what you might expect if you're familiar with, you know, any other programming language ever. It's not easy to visualize how quicksort actually behaves in Haskell in terms of memory accesses or even the order of comparisons. If you could only observe the behavior, and not the source code, 你不会认识到它作为一个快速排序是做什么的.

例如，快速排序的 C 版本在第一次递归调用之前对所有数据进行分区。在 Haskell 版本中，结果的第一个元素将在 第一分区运行完之前被计算(甚至可能出现在屏幕上) ，实际上是在 greater上完成任何工作之前。

附言。Haskell 代码会更加快速排序——如果它执行的比较次数与快速排序相同; 编写的代码执行的比较次数是快速排序的两倍，因为指定 lesser和 greater是独立计算的，对列表进行两次线性扫描。当然，从原则上讲，编译器有可能足够聪明地消除额外的比较; 或者可以更改代码以使用 Data.List.partition。

附注。Haskell 算法的经典例子就是计算素数的 sieve of Eratosthenes。

小开

看起来 Haskell 版本会为它划分的每个子列表分配更多的空间。所以它可能会大规模地耗尽内存。虽然说这样更优雅。我想这就是你选择功能性和命令式编程性的权衡吧。


提交答案