8

我在 Haskell 中寻找一种同时支持快速索引和快速追加的数据结构。这是针对递归引起的记忆问题。

从向量在 c++ 中的工作方式（它是可变的，但在这种情况下这不重要）看来，具有（摊销）O(1) 附加和 O(1) 索引的不可变向量应该是可能的（好吧，它不是，请参阅对此问题的评论）。这在 Haskell 中是否可行，还是我应该使用具有（AFAICT 无论如何）O(1) 附加和 O(log(min(i,ni))) 索引的 Data.Sequence？

在相关的说明中，作为一名 Haskell 新手，我发现自己渴望一份实用、简洁的 Haskell 数据结构指南。理想情况下，这将对最实用的数据结构以及性能特征和指向实现它们的 Haskell 库的指针提供相当全面的概述。似乎那里有很多信息，但我发现它有点分散。我要求太多了吗？

4

3 回答 3

10

对于简单的记忆问题，您通常希望构建表一次，以后不要修改它。在这种情况下，您可以避免担心追加，而是将记忆表的构造视为一项操作。

一种方法是利用惰性求值并在我们构建表时引用它。

import Data.Array
fibs = listArray (0, n-1) $ 0 : 1 : [fibs!(i-1) + fibs!(i-2) | i <- [2..n-1]]
  where n = 100

当表格元素之间的依赖关系使得难以提前制定简单的评估顺序时，此方法特别有用。但是，它需要使用盒装数组或向量，由于额外的开销，这可能使这种方法不适合大型表。

对于未装箱的向量，您有类似constructN这样的操作，可以让您以纯粹的方式构建表格，同时在下面使用突变来提高效率。它通过给函数传递一个到目前为止构造的向量前缀的不可变视图来实现这一点，然后你可以使用它来计算下一个元素。

import Data.Vector.Unboxed as V
fibs = constructN 100 f
  where f xs | i < 2 = i
             | otherwise = xs!(i-1) + xs!(i-2)
             where i = V.length xs
于 2012-05-03T22:40:56.417 回答
9

如果内存服务，C++ 向量被实现为具有边界和大小信息的数组。当插入会增加超出大小的范围时，大小会加倍。这是摊销的 O(1) 时间插入（不是您声称的 O(1)），并且可以在 Haskell 中使用该类型很好地模拟Array，可能带有合适的IO或ST前置的。

于 2012-05-03T21:59:59.313 回答
7

看看这个，以便对您应该使用的内容做出更明智的选择。

但简单的一点是，如果您想要 C++ 向量的等价物，请使用Data.Vector.

于 2012-05-03T22:06:23.537 回答