在Haskell中使用向量来提高性能

  • Z时代
  • 2024-01-10
  • 分类：问答

我是Haskell的新手，我对使用不纯的（可变的）数据结构可以提高性能有疑问。我正在尝试整理一些我听到的不同内容，因此，如果我的术语不完全正确，或者有一些小错误，请多多包涵。

为了使这一点具体，请考虑快速排序算法（摘自Haskell Wiki）。

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

这不是“真正的快速排序”。可以使用“真正的”快速排序算法，而事实并非如此。这是非常低效的内存。

另一方面，可以在Haskell中使用向量来实现就地快速排序。[

第二种算法比第一种算法快多少？大O表示法在这里无济于事，因为性能提高将来自更有效地使用内存，而没有一个更好的算法（对吗？）。我很累自己构造一些测试用例，但是我很难让事情运行。

一个理想的答案将使您对理论上使原位Haskell算法更快的原因有所了解，并比较一些测试数据集的运行时间。

回答：

没有比测试更好的了吧？结果并不令人惊讶：对于范围为的随机整数列表[0 .. 1000000]，

list size: 200000         ghc              -O2     -fllvm  -fllvm-O2
────────                   ────────   ────────   ────────   ────────
Data.List.sort            0.878969s  0.883219s  0.878106s  0.888758s
Naïve.quicksort           0.711305s  0.870647s  0.845508s  0.919925s
UArray_IO.quicksort       9.317783s  1.919583s  9.390687s  1.945072s
Vector_Mutable.quicksort   1.48142s  0.823004s  1.526661s  0.806837s

这Data.List.sort就是它的意思，Naïve.quicksort是您引用的算法，UArray_IO.quicksort并且Vector_Mutable.quicksort是从您链接到的问题中提取的：klapaucius和DanBurton的答案 ，都包装好以接受列表（不确定我是否正确）：

quicksort :: [Int] -> [Int]
quicksort l = unsafePerformIO $ do
  let bounds = (0, length l)
  arr <- newListArray bounds l :: IO (IOUArray Int Int)
  uncurry (qsort arr) bounds
  getElems arr

和

quicksort :: Ord a => [a] -> [a]
quicksort = toList . iqsort . fromList

分别。

如您所见，朴素算法Data.Vector在对随机生成的整数列表进行排序的速度方面不落后于可变解决方案，IOUArray实际上 更糟。测试是在运行Ubuntu 11.10 x86-64的Intel i5笔记本电脑上进行的。

考虑到ɢᴏᴏᴅ可变的实现毕竟仍然远远领先于本文中的所有实现，因此以下内容并没有多大意义。

请注意，这并不意味着一个好的基于列表的程序总是可以跟上其可变实现的等价物，但是GHC肯定在使性能接近方面做得很好。同样，它当然也取决于数据：在这些情况下，随机生成的列表进行排序所包含的值介于0到1000之间，而不是如上所述的0到1000000之间的时间，即具有很多重复项：

list size: 200000         ghc               -O2      -fllvm  -fllvm-O2
────────                    ────────   ────────    ────────   ────────
Data.List.sort             0.864176s  0.882574s   0.850807s  0.857957s
Naïve.quicksort            1.475362s  1.526076s   1.475557s  1.456759s
UArray_IO.quicksort       24.405938s  5.255001s  23.561911s  5.207535s
Vector_Mutable.quicksort   3.449168s  1.125788s   3.202925s  1.117741s

更不用说预排序数组了。

有趣的是（只有在非常大的尺寸下才出现，这需要rtsopts来增加堆栈容量），这两种可变的实现如何显着 变慢 了-fllvm -O2：

list size: 3⋅10⁶        ghc      -O1   -fllvm-O1         -O2   -fllvm-O2
────────                    ────────    ────────    ────────    ────────
Data.List.sort            23.897897s  24.138117s  23.708218s  23.631968s
Naïve.quicksort           17.068644s  19.547817s  17.640389s  18.113622s
UArray_IO.quicksort       35.634132s  38.348955s  37.177606s  49.190503s
Vector_Mutable.quicksort  17.286982s  17.251068s  17.361247s  36.840698s

在我看来，不可变的实现在llvm上表现更好（不是在某种程度上可以不变地完成所有工作吗？），虽然我不明白为什么这只是在高度优化时对可变版本的变慢而变得明显，但在我看来还是合乎逻辑的和大数据量。

回答：

$ cat QSortPerform.hs
module Main where
import qualified Data.List(sort)
import qualified Naïve
import qualified UArray_IO
import qualified Vector_Mutable
import Control.Monad
import System.Random
import System.Environment
sortAlgos :: [ (String, [Int]->[Int]) ]
sortAlgos = [ ("Data.List.sort", Data.List.sort)
            , ("Naïve.quicksort", Naïve.quicksort)
            , ("UArray_IO.quicksort", UArray_IO.quicksort)
            , ("Vector_Mutable.quicksort", Vector_Mutable.quicksort) ]
main = do
   args <- getArgs
   when (length args /= 2) $ error "Need 2 arguments"
   let simSize = read $ args!!1
   randArray <- fmap (take simSize . randomRs(0,1000000)) getStdGen
   let sorted = case filter ((== args!!0) . fst) sortAlgos of
        [(_, algo)] -> algo randArray
        _ -> error $ "Argument must be one of " 
                        ++ show (map fst sortAlgos)
   putStr "First element:  "; print $ sorted!!0
   putStr "Middle element: "; print $ sorted!!(simSize`div`2)
   putStr "Last element:   "; print $ sorted!!(simSize-1)

它在命令行上采用算法名称和数组大小。使用此程序进行了运行时比较：

$ cat PerformCompare.hs
module Main where
import System.Process
import System.Exit
import System.Environment
import Data.Time.Clock
import Data.List
import Control.Monad
import Text.PrettyPrint.Boxes
compiler = "ghc"
testProgram = "./QSortPerform"
flagOpts = [[], ["-O2"], ["-fllvm"], ["-fllvm","-O2"]]
algos = ["Data.List.sort","Naïve.quicksort","UArray_IO.quicksort","Vector_Mutable.quicksort"]
main = do
   args <- getArgs
   let testSize = case args of
         [numb] -> read numb
         _      -> 200000
   results <- forM flagOpts $ \flags -> do
      compilerExitC <- verboseSystem
              compiler $ testProgram : "-fforce-recomp" : flags
      when (compilerExitC /= ExitSuccess) .
         error $ "Compiler error \"" ++ show compilerExitC ++"\""
      algoCompare <- forM algos $ \algo -> do
         startTime <- getCurrentTime
         exitC <- verboseSystem testProgram [algo, show testSize]
         endTime <- getCurrentTime
         when (exitC /= ExitSuccess) .
            error $ "Program error \"" ++ show exitC ++"\""
         return . text . show $ diffUTCTime endTime startTime
      return . vcat right $ text(concat flags)
                          : text("────────")
                          : algoCompare
   let table = hsep 2 bottom
         $ vcat left (map text $ ("list size: "++show testSize)
                               : "────────"
                               : algos                          )
         : results
   printBox table
verboseSystem :: String -> [String] -> IO ExitCode
verboseSystem cmd args = do
   putStrLn . unwords $ cmd : args
   rawSystem cmd args

以上是 在Haskell中使用向量来提高性能 的全部内容， 来源链接： utcz.com/qa/398777.html

回到顶部