在haskell中具有高性能的可变随机访问阵列/矢量

Question

这是Haskell上的一个主题(例如可变数组实现)，但我仍然不确定需要频繁修改和随机访问数组/向量的情况下的最佳实践是什么。

假设长度为1,000,000的向量。对它的操作包括基于输入访问(小的，例如1000)子集，并根据输入修改值。此外，这种操作重复了2,000,000次。任务本身可以在纯数据结构(如列表)中实现，例如，尽管效率很低，但如下所示：

type Vect = [Int]

f :: Vect -> [[Int]] -> Vect
f x indsList = foldl g x indsList

-- g is just an example of random-access and modifications on the values.
g :: Vect -> [Int] -> Vect
g x inds = map h $ zip x [0..]
    where h (x, i) = if i `elem` inds then x !! i + 1 else x !! i

散列/映射数据结构(如IntMap)可以用于高效的大量随机访问，但数组/向量也应该这样做。更重要的是，大量的修改仍然需要通过可变结构来解决，以避免内存复制。在Haskell中是否确实存在一个可变的随机acesss数组/向量？如果使用ST/IO单元组，这种控制在我的设置中会影响性能吗？

Answer 1

Haskell确实有高效的可变数组。

• 有一个STUArray，它拥有相当复杂但通常只是不必要的Ix-indexing方法，有许多边界检查和很少的特殊优化，这使得它比理论上的可能慢一些。
• 所有Data.Vector的开销都很小，大量使用流融合优化，更喜欢简单的“列表式”接口。这意味着您实际上可以非常容易地将您的示例直接传递给不可变的向量，并且仍然可以获得比您预期的更好的性能： 将Data.Vector.Unboxed导入VU类型Vect = VU.Vector Int f :：Vect -> [ Int ] -> Vect f x indsList = VU.foldl g x indsList g :：Vect -> Int -> Vect g x inds = VU.zipWith h x 0.-h只是修改值的一个例子。其中h，i，elem，inds=x。我+1否则=似曾相识。！我

是的，您可能希望在ST monad中进行可更改的更新。不确定您所说的“此类控件是否会影响性能”：一旦编译器优化了经过验证的类型安全性，就没有任何在命令式语言中也不存在的“控件”。哪个GHC可以做得很好；您可以非常接近于Data.Vector.Unboxed的C性能。总有一些不可避免的开销，但这主要与垃圾收集等问题有关，您也可以在Java中得到这些问题。

由于ST和IO是单变量，编译器实际上可以进行更高级别的优化，这在命令式语言中是不可能的，尽管编译器还不是很远。

性能，特别是数组操作的性能，在许多地方都有讨论，例如在RWH。

Answer 2

来自雅尔的国外UArrays是可变的，随机访问和最大快速.此外，它们是“快速和肮脏的”，也就是说，不要强加冻结/解冻样板的每一个突变操作。

缺点:几乎所有的“低级”操作都在IO下。