不可变数据结构替代数组

Question

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

- Wlofrevo Kcast

---

不确定您所说的“带有最快访问/更新的不可变列表”的意思是什么——您无法更新不可变列表... - arshajii

这句话的意思是“创建一个新的不可变结构，除了从现有结构中保留一个部分之外，其余全部都要复制”。@arshajii 这里使用了一个常见的简写。 - user395760

如果您想要快速更新，请使用可变数组/列表。 - Peter Lawrey

@WlofrevoKcast 我不会这样做。在当前线程中对集合进行所有必要的处理。这通常比传递复杂的数据结构或将它们复制到另一个线程中更快。你不仅仅是传递一个引用，而是需要从一个CPU缓存中提取数据到另一个缓存中，开销可能超过你获得的好处。 - Peter Lawrey

@PeterLawrey 我不确定你在说什么，如果缓存行没有被写入（而且它们不会被写入，因为数据结构是不可变的），那么就不会触发过多的 CPU 间通信。至少这是我对缓存一致性协议的理解。但让我们假设你是正确的。我仍然不会说“不要那样做”——在只有引用类型的语言中，缓存本来就很难处理，即使有可测量的性能影响，不可变的变体可能也有更简单的接口。 - user395760

Answer 1

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

除此之外，还有一些纯函数数据结构可以为这些情况提供更好的边界。2-3 Finger Trees（Haskell的Data.Sequence背后的数据结构）是一个例子。另一个选择是Clojure的向量和相关数据结构（例如Relaxed Radix-Balanced Trees），它们使用高扇出（32或更多）的树来保持读取廉价，并使用结构共享来避免太多的复制。

然而，所有这些都相对棘手，特别是如果性能很重要，我不知道是否存在现有的实现（我认为Clojure的向量不易于从Java中使用）。

- user395760

---

谢谢delnan。事实上，我对Haskell感兴趣已经有一段时间了。这些数据结构是否经常使用，或者当一个习惯于oop的人转向函数式编程并错过数组时，是否存在其他方法？我对学习更多关于函数式数据结构很感兴趣。 - Wlofrevo Kcast

Answer 2

我不确定我理解你在寻找什么，但我会尝试根据一些标准类中看到的东西给出一些指针：

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

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

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

• AWTEventMulticaster实现了类似的目标，但最小化了复制。它是一个聪明的二叉树。请参见源代码。

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

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

- Boann