4

当您需要具有最快访问/更新的不可变列表时，您会使用什么？如果您必须从中间访问一个元素，LinkedList 可能会很慢，并且禁止创建和重新填充它。二叉树？四叉树？

4

2 回答 2

2

如果更新很少（或集合很小），那么初始化后不写入的数组是值得的。在这些情况下，低得多的常数因子（时间和空间）超过了线性时间更新。

除此之外，还有许多纯函数式数据结构为这些情况提供了更好的界限。2-3 手指树（Haskell 背后的数据结构Data.Sequence）就是一个例子。另一种选择是 Clojure 的向量和相关数据结构（例如，松弛的基数平衡树），它们使用具有高扇出（32 或更多）的树来保持读取成本低廉和结构共享以避免过多的副本。

所有这些手动实现都比较棘手，特别是如果性能很重要，而且我不知道现有的实现（我不认为 Clojure 的向量在 Java 中使用起来并不容易或方便）。

于 2013-11-02T18:10:36.837 回答
-1

我不确定我是否理解您在寻找什么，但我会尝试根据我在标准课程中看到的一些内容给出一些建议：

  • CopyOnWriteArrayList是一个可变但线程安全的列表，因为它在更新时复制内部数组。也许您可以从中调整一些想法，尽管对于大型列表显然效率不高。

  • ConcurrentHashMap在更复杂的结构上实现了类似的想法。它将内部哈希表划分为单独的分区，这样更改只需要锁定对相关分区的访问即可。

    对于不可变列表，您可以做类似的事情：将列表的内部数组分成几个分区，并将它们都视为不可变的。当需要更改列表时，只需克隆一个分区和分区的索引，这将比复制整个列表便宜。

  • AWTEventMulticaster实现了类似的目标，但重复了绝对最小值。这是一棵聪明的二叉树。查看源代码。

使用较小的内部分区或块，您可以获得更快的更新，但通常访问速度较慢。对于较大的块（例如，整个阵列），您会获得较慢的更新但更快的访问。

如果您确实需要最快的访问和更新，则必须使用可变数组。

于 2013-11-02T18:23:53.483 回答