Clojure 可变性：O(1) 性能更新向量

Question

在Java中，让我们说我有一个整数数组：int[] a = {1, 2, 3, 4, 5};。如果我想更改数组中的某个元素，可以通过更改内存中某个地址处的数据来实现：a[2] = 9;=> {1, 2, 9, 4, 5}。

在Clojure中，我能有一个向量：(def a [1 2 3 4 5])。如何在保证最坏情况时间复杂度为 O(1) 的情况下更改向量中某个位置的元素？我读过该assoc关键字的平均时间复杂度为 O(1)，但这不是我要找的。另外，我查看了瞬态向量，但我还没有找到一个很好的简单示例来更新 O(1) 中的向量。

Answer 1

在当前的实现中，Clojure 向量的复杂度为 O(log_32(n))（以 32 为底的对数）。在数学上，O(log_32(n)) 与 O(log(n)) 是一回事。差异不是理论上的，而是实际的：

• AFAICT，因为 Clojure 持久向量不能包含超过 40 亿个元素，所以 log_32(n) 永远不会大于 7。所以，在某种程度上，它是恒定时间:)。这说明了 Persistent Hash Tries 中的分支因子为 32（与许多分支因子为 2 的树数据结构不同）的事实。
• 不变的因素很重要！Java 数组的更新将比持久向量快得多。您不应该考虑渐近复杂性，而是想知道这个常数因子是否对您来说太大了。如果是，请查看瞬态。