这是 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,此类控件是否会影响我的设置中的性能?
最佳答案
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 .
关于arrays - Haskell 中具有高性能的可变、随机访问数组/向量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17892065/