ryb*_*ome 112 sorting haskell quicksort
Haskell的网站介绍了一个非常有吸引力的5行快速排序功能,如下所示.
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
它们还包括"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代码那样扩展更长的列表.
为什么上面的Haskell函数不是真正的快速排序？如何缩放更长的列表？
pat*_*pat 69
真正的quicksort有两个美丽的方面:
简短的Haskell示例演示(1),但不是(2).如果您还不知道该技术,那么(2)如何完成可能并不明显!
kla*_*ius 56
Haskell中真正的inplace quicksort:
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
Dan*_*ton 29
这是"真正的"快速排序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 (,,,) 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]
我不经常在Haskell中编写命令式代码,因此我确信有很多方法可以清理这些代码.
所以呢？
您会注意到上面的代码非常非常长.它的核心与C代码一样长,尽管每一行通常都有点冗长.这是因为C秘密地做了许多你可能认为理所当然的讨厌的事情.例如,a[l] = a[h];.这个访问可变变量l和h,然后访问可变数组a,然后变异的可变数组a.圣变,蝙蝠侠!在Haskell中,突变和访问可变变量是明确的.由于各种原因,"假"qsort很有吸引力,但其中最主要的是它不使用变异; 这种自我限制使得一目了然更容易理解.
Kei*_*son 24
在我看来,说它"不是真正的快速排序"夸大了这个案例.我认为这是Quicksort算法的有效实现,只是不是特别有效.
ham*_*mar 15
我认为这个论点试图提出的情况是,通常使用quicksort的原因是它是就地的并且因此对缓存友好.由于你没有Haskell列表的这些好处,它的主要存在理由已经消失,你也可以使用合并排序,它保证O(n log n),而使用quicksort你要么必须使用随机化或复杂化分区方案,以避免在最坏的情况下运行O(n 2).
Jas*_*rff 15
由于懒惰的评估,Haskell程序不会(几乎不能)执行它看起来的样子.
考虑这个程序:
main = putStrLn (show (quicksort [8, 6, 7, 5, 3, 0, 9]))
在热切的语言,首先quicksort将运行,然后show,然后putStrLn.在函数开始运行之前计算函数的参数.
在Haskell中,情况正好相反.该功能首先开始运行.仅在函数实际使用它们时才计算参数.复合参数(如列表)一次一个地计算,因为每个参数都被使用.
所以在这个程序中发生的第一件事就是putStrLn开始运行.
GHCputStrLn通过将参数String的字符复制到输出缓冲区来实现工作.但是当它进入这个循环时,show还没有运行.因此,当它从字符串中复制第一个字符时,Haskell 会计算计算该字符所需的部分show和quicksort调用.然后转到下一个角色.所以,这三个职能时的执行,和-进行了交错.以增量方式执行,留下未评估的thunks图表,以便记住它停止的位置.putStrLnputStrLnshowquicksortquicksort
现在,如果您熟悉任何其他编程语言,那么这与您可能期望的完全不同.quicksort在内存访问或甚至比较顺序方面,可视化Haskell中的实际行为并不容易.如果您只能观察行为而不是源代码,那么您将无法识别它作为快速排序的行为.
例如,快速排序的C版本在第一次递归调用之前分割所有数据.在Haskell版本中,结果的第一个元素将在第一个分区完成运行之前计算(甚至可能出现在您的屏幕上)- 确实在完成任何工作之前greater.
PS如果Haskell代码与quicksort进行相同数量的比较,那么Haskell代码将更加快速; 写入的代码执行两倍的比较因为lesser并且greater被指定为独立计算,在列表中进行两次线性扫描.当然,编译器原则上可以足够聪明地消除额外的比较; 或者代码可以更改为使用Data.List.partition.
PPS Haskell算法的典型例子不是表现出你的预期,而是Eratosthenes用于计算质数的筛子.
Jer*_*ons 11
我相信大多数人说漂亮的Haskell Quicksort不是一个"真正的"Quicksort的原因是它不是就地 - 显然,它不能在使用不可变数据类型时.但也有人反对它不是"快速":部分是因为昂贵的++,还因为存在空间泄漏 - 你在对较小元素进行递归调用时会挂起输入列表,并且在某些情况下 - 例如,当列表减少时 - 这会导致二次空间使用.(你可能会说,使它在线性空间中运行是最接近你可以使用不可变数据"就地"获得的.)这两个问题都有很好的解决方案,使用累积参数,元组和融合; 参见Richard Bird的使用Haskell的函数式编程简介的 S7.6.1 .