在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中是否存在可变的随机访问数组/向量？如果使用ST/IO Monads,这些控件会影响我的设置吗？

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
  

是的,您可能希望在STmonad中进行可变更新.不确定你的意思是"这些控制是否会影响性能":一旦编译器优化了经过验证的类型安全性,就没有任何"控制"也不会出现在命令式语言中.哪个GHC可以做得很好; 你可以非常接近C性能Data.Vector.Unboxed.始终存在一些不可避免的开销,但这主要与垃圾收集等问题有关,这些问题也可以通过Java获得.

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

在许多地方讨论了性能,特别是阵列操作的性能,例如在RWH中.