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

首先,你需要一个可变的向量.你可以逐渐建立这个
你扫描文件;分配一个与您需要的一样大的向量,
并在空间不足时增加大小并复制.或者你可以
读取整个文件,计数记录分隔符,并分配
适量的空间一次.这很容易,但可能不是
在现实生活中可以接受(按需扩展的策略很漂亮
共同;如果你使用像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,有几种方法可以让这个外观
纯电话代码;一个是在ST monad里面做的.
您的ST动作正在创建向量,进行修改,并将其“冻结”
成为一个不变的向量.在内部,你使用得很快
修改这个内存位置 – 一堆一次的操作,但是
在外面,你有一些纯粹的东西. (阅读论文
ST,如果你想要一个争论,为什么这是安全的.)

处理可变数据的另一种方法是在其中进行
一切,呃,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的函数实际排序(in
以可变向量为单位).

创建随机可变向量并将其排序的动作
好像：

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