在haskell快速排序整数

Question

haskell库中是否有任何函数在O(n)时间内对整数进行排序？[By,O(n)我的意思是比比较排序更快,特定于整数]

基本上我发现下面的代码花了很多时间进行排序(与没有排序的列表相加):

import System.Random
import Control.DeepSeq
import Data.List (sort)

genlist gen = id $!! sort $!! take (2^22) ((randoms gen)::[Int])

main = do
    gen <- newStdGen
    putStrLn $ show $ sum $ genlist gen

总结一个列表不需要deepseq,但我想要的是,但上面的代码对于我正在寻找的指针来说已经足够了.

时间:6秒(不排序); 约35秒(有排序)

内存:大约80 MB(没有排序); 约310 MB(有排序)

注1:对于我来说,内存对于我来说是一个比时间更大的问题,因为手头的任务我出现了内存错误(内存使用量变为3GB!运行时间为30分钟后)

我假设更快的算法也会提供下注内存打印,因此寻找O(n)时间.

注2:我正在寻找Int64的快速算法,尽管其他特定类型的快速算法也会有所帮助.

---

使用的解决方案:带有未装箱的向量的IntroSort足以完成我的任务:

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I

sort :: [Int] -> [Int]
sort = V.toList . V.modify I.sort . V.fromList

Answer 1

我会考虑使用向量而不是列表,因为列表每个元素有很多开销,而未装箱的向量基本上只是一个连续的字节块.该矢量算法软件包包含各种排序算法,你可以使用这个,包括基数排序,这是我希望应该在你的情况下做的很好.

这是一个简单的例子,但如果您计划对其进行进一步处理,那么将结果保持为矢量形式可能是个好主意.

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Radix as R

sort :: [Int] -> [Int]
sort = V.toList . V.modify R.sort . V.fromList

此外,我怀疑您的示例的大部分运行时间来自随机数生成器,因为标准的运行时并不完全以其性能而闻名.您应该确保只对排序部分进行计时,如果您的程序中需要大量随机数,则Hackage上有更快的生成器.

Answer 2

使用数组对数字进行排序的想法是减少内存使用的正确方法。

但是，使用列表的最大值和最小值作为边界可能会导致内存使用量超出，甚至运行时失败maximum xs - minimum xs > (maxBound :: Int)。

因此，我建议将列表内容写入未装箱的可变数组，对其进行就地排序（例如使用快速排序），然后再次从中构建列表。

import System.Random
import Control.DeepSeq
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST

myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
   | lo < hi   = do
       let lscan p h i
               | i < h = do
                   v <- unsafeRead a i
                   if p < v then return i else lscan p h (i+1)
               | otherwise = return i
           rscan p l i
               | l < i = do
                   v <- unsafeRead a i
                   if v < p then return i else rscan p l (i-1)
               | otherwise = return i
           swap i j = do
               v <- unsafeRead a i
               unsafeRead a j >>= unsafeWrite a i
               unsafeWrite a j v
           sloop p l h
               | l < h = do
                   l1 <- lscan p h l
                   h1 <- rscan p l1 h
                   if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
               | otherwise = return l
       piv <- unsafeRead a hi
       i <- sloop piv lo hi
       swap i hi
       myqsort a lo (i-1)
       myqsort a (i+1) hi
   | otherwise = return ()


genlist gen = runST $ do
    arr <- newListArray (0,2^22-1) $ take (2^22) (randoms gen)
    myqsort arr 0 (2^22-1)
    let collect acc 0 = do
            v <- unsafeRead arr 0
            return (v:acc)
        collect acc i = do
            v <- unsafeRead arr i
            collect (v:acc) (i-1)
    collect [] (2^22-1)

main = do
    gen <- newStdGen
    putStrLn $ show $ sum $ genlist gen

相当快并且使用更少的内存。它仍然使用大量的列表内存，2 ²² Int秒需要 32MB 原始存储（64 位Int），每个元素的列表开销为 iirc 5 个单词，加起来约为 200MB，但不到一半原来的。