arrays - Haskell 中具有高性能的可变、随机访问数组/向量

Question

这是 Haskell 上的一个主题，讨论了很多(例如 mutable-array-implementation )，但我仍然不确定对于需要频繁修改和随机访问数组/向量的情况，最佳实践是什么。

假设一个长度为 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 中确实存在可变的随机访问数组/向量吗？如果使用 ST/IO Monad，此类控件是否会影响我的设置中的性能？

Answer 1

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

• 有STUArray ，它具有相当复杂但通常不必要的 Ix 索引方法，具有许多边界检查和很少的特殊优化，这使得它比理论上可能慢一些。

• 全部 Data.Vector开销很小，大量使用流融合优化，更喜欢简单的“类似列表”的界面。这意味着您实际上可以非常轻松地将示例直接转移到不可变向量，并且仍然可以获得比您预期更好的性能:

  import Data.Vector.Unboxed as VU
  
  type 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 is just an example of modifications on the values.
      where h x i
             | i`elem`inds   = x VU.! i + 1
             | otherwise     = x VU.! i
  

是的，您可能希望在 ST monad 中进行可变更新。不确定“此类控制是否会影响性能”是什么意思:一旦编译器优化了经过验证的类型安全性，实际上就没有任何“控制”不存在于命令式语言中。其中GHC可以做得相当好；您可以使用 Data.Vector.Unboxed 获得非常接近 C 的性能。总会有一些不可避免的开销，但这主要与垃圾收集等问题有关，这些问题在 Java 中也会遇到。

由于 ST 和 IO 是 monad，编译器实际上可以进行一些更高级的优化，这在命令式语言中是不可能的，尽管编译器不是还没有那么远。

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