如何使用Data.Vector.Generic.Mutable进行排序？

Question

如何使用Data.Vector.Generic.Mutable对象和Data.Vector.Algorithms中的排序算法对从大文件(比如几百万行)读取的长数据列表(字符串,浮点数等)进行排序？

Answer 1

这是在一般情况下如何做到这一点.

首先,你需要一个可变的载体.您可以在扫描文件时以递增方式构建它; 分配一个大约你需要的矢量,并在空间不足时增加大小并复制.或者,您可以读取整个文件,计算记录分隔符,并一次性分配适当的空间量.这更容易,但可能在现实生活中不可接受.(按需扩展的策略非常普遍;如果您使用像Perl这样的语言并将从文件中读取的行读到数组的末尾,这就是正在发生的事情.当您使用Perl为数组分配一些空间时填充它,它增加了空间量,分配新的空间和副本.)

无论如何,我太懒了,所以我只是想创建一个带有一些随机数的向量.

我们需要一堆库来实现这个目标:

import Control.Monad
import System.Random
import qualified Data.Vector as IV
import qualified Data.Vector.Mutable as MV
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Algorithms.Intro as VA

我们并不需要这一切,但我们最终还是需要它,所以我想我会把它弄掉.

无论如何,我们的可变载体将是一个"正常"的可变载体,在这里MV.MVector.

可变矢量的概念是您创建它并在许多步骤中修改它.在Haskell中,有几种方法可以使调用代码变得纯粹; 一个是在STmonad中完成所有操作.你的ST动作是创建向量,修改它,并将其"冻结"为不可变向量.在内部,你正在使用快速修改 - 这个内存位置 - 一堆时间的操作,但在外部,你有一些纯粹的东西.(阅读关于 ST你是否想要争论为什么这是安全的论文.)

处理可变数据的另一种方法是在Everything,erm IO,monad中进行处理.这就是我们要做的,因为它最方便.

(Data.Vector.Mutable有两个预定义的向量类型为你, IOVector和STVector我们正在使用IOVector,它把所有的向量操作进入IO.)

就像8段前一样,我们要创建一个可变的向量来排序.我们在这里:

randVector :: IO (MV.IOVector Int)
randVector = do
  v <- MV.new 10
  forM [0..9] $ \x -> do
    r <- randomIO :: IO Int
    MV.write v x r
  return v

这是一个IO动作,返回一个新的可变向量,其中包含10个随机数.(随机数生成也可以方便地提升到IO monad中,所以我们也这样做了,为了方便!就像我们编写C一样,但语法更好,类型更安全.)

这实际上是困难的部分.要进行排序,我导入 Data.Vector.Algorithms.Intro的基本上就是一个就地快速排序.一个被调用的函数sort进行实际排序(在可变向量所在的monad中).

创建随机可变矢量并对其进行排序的操作如下所示:

sort = VA.sort =<< randVector

现在,要打印出来,我们需要做的就是将矢量"冻结"成一个不可变的向量,并打印出来.toList.或者你可以迭代每个元素并打印出来.

以下是我提出的例子:

main = do
  v <- randVector
  VA.sort v
  iv <- V.unsafeFreeze v :: IO (IV.Vector Int)
  print . V.toList $ iv

V.unsafeFreeze来自Data.Vector.Generic(如何使用相同的API与所有矢量类型进行交互)V.toList.

无论如何,值得注意的是IO在这里纯粹是为了方便.由于您正在从文件数据构建矢量,因此它是合适的.但是,99%的时间你应该使用ST.在ST动作中,创建矢量,对其进行排序,冻结并返回冻结版本.

一个类似的例子STVector:

randVector :: ST s (Vector Int)
randVector = do
  vec <- new 10
  rand <- newSTRef 17
  forM_ [0..9] $ \index -> do
    randN <- readSTRef rand
    let randN' = (fst . next . mkStdGen) randN
    writeSTRef rand randN'
    write vec index randN'
  unsafeFreeze vec

然后运行:

*Main> runST randVector
fromList [679560,1422110406,306332632,1905242129,692062628,393451229,355476175,1240028023,873588529,1181443777] :: Data.Vector.Vector