Haskell数组与列表

Question

我正在玩Haskell和Project Euler的第23个问题.用列表解决后,我去了这里看了一些数组工作.这个解决方案比我的快得多.所以这就是问题所在.我什么时候应该在Haskell中使用数组？他们的表现比名单更好吗？在哪些情况下？

Answer 1

最明显的区别与其他语言相同:数组有O(1)查找,列表有O(n).将某些东西附加到列表的头部(:)需要O(1); appending(++)需要O(n).

阵列还具有一些其他潜在优势.您可以使用未装箱的数组,这意味着条目只是连续存储在内存中而没有指向每个条目的指针(如果我理解正确的话).这有几个好处 - 它占用更少的内存并可以提高缓存性能.

修改不可变数组很困难 - 你必须复制整个数组,它需要O(n).如果你正在使用可变数组,你可以在O(1)时间内修改它们,但是你必须放弃拥有纯粹功能性解决方案的优势.

最后,如果性能无关紧要,列表更容易使用.对于少量数据,我总是会使用一个列表.

Answer 2

如果你做了很多索引以及更新,你可以

• 使用Maps(或IntMaps),O(日志大小)索引和更新,足以满足大多数用途,代码易于正确使用
• 或者,如果Maps太慢,则使用可变(未装箱)的数组(STUArray来自矢量包中的Data.Array.ST或STVectors ; O(1)索引和更新,但代码更容易出错,通常不那么好.

对于特定用途,功能也可以accumArray提供非常好的性能(在引擎盖下使用可变数组).

Answer 3

数组有O(1)索引(这曾经是Haskell定义的一部分),而列表有O(n)索引.另一方面,任何类型的数组修改都是O(n),因为它必须复制数组.因此,如果您要进行大量索引但很少更新,请使用数组.