在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单子，这样的控件是否会影响我的性能设置？

- Causality

---

你确定在从更功能性的角度解决整个问题时，不能更优雅地（甚至更高效地）完成这项任务吗？为什么需要逐步进行这些修改，难道你不能通过一些懒惰的重定向“直接”获得所需的结果吗？ - leftaroundabout

[] 不是一种类型。map h $ zip x [0..] - 我认为你的意思是 zipWith h x [0..]，否则你需要使用 uncurry h。 - leftaroundabout

@leftaroundabout，已经更新了代码，尽管g的实现只是一个示例。从更高的函数角度来考虑它会很好，但在这种情况下可能会比较困难。我考虑过缓存每个修改并定期重新压缩修改。然而，对于成千上万的修改，用不可变的结构模拟可变结构肯定比真正的可变结构效率低得多。 - Causality

你能告诉我们你实际的问题是什么吗？ - augustss

Answer 1

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

• There is STUArray, which has the quite sophisticated but often just unnecessary Ix-indexing methodology with many bounds-checks and little special optimisation, which makes it a bit slower than theoretically possible.

• All Data.Vector have very little overhead, make heavy use of stream fusion optimisation, prefer a simple, "list-like" interface. That means you can actually transfer your example very easily directly to immutable vectors, and may still get better performance than you might expect:

  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单子。不确定您所说的“这样的控制是否会影响性能”的意思是什么：一旦编译器已经优化了已经被证明的类型安全，不存在任何“控制”不出现在命令式语言中。 GHC可以做得非常好；您可以使用Data.Vector.Unboxed接近C性能。总会有一些不可避免的开销，但这主要与垃圾收集等问题有关，这也是Java中可以得到的。

由于ST和IO都是单子，因此编译器实际上可以进行一些更高级别的优化，在命令式语言中是不可能实现的，尽管编译器还没有达到那么远。

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

- leftaroundabout

Answer 2

来自Yarr的外国UArrays是可变的、随机访问和非常快速的。同时它们也是“快速而脏”的，即不会为每个变异操作强制执行冻结/解冻样板代码。

缺点：几乎所有“低级”操作都在IO下进行。

- leventov