Haskell 数组与列表

Question

我正在玩 Haskell 和 Project Euler 的第 23 个问题。用列表解决后我去了here我在哪里看到了一些阵列工作。这个解决方案比我的要快得多。
所以这就是问题所在。我什么时候应该在 Haskell 中使用数组？它们的性能是否优于列表？在哪些情况下？

Answer 1

最明显的区别与其他语言相同:数组的查找时间为 O(1)，列表的查找时间为 O(n)。将某些内容附加到列表的头部( : )需要 O(1)；附加 (++) 需要 O(n)。

数组还有其他一些潜在的优势。您可以拥有未装箱的数组，这意味着条目只是连续存储在内存中，而没有指向每个条目的指针(如果我正确理解了这个概念)。这有几个好处——它占用更少的内存并且可以提高缓存性能。

修改不可变数组很困难——你必须复制整个数组，这需要 O(n)。如果您使用的是可变数组，则可以在 O(1) 时间内修改它们，但您必须放弃拥有纯函数解决方案的优势。

最后，如果性能无关紧要，列表更容易使用。对于少量数据，我总是使用列表。