clojure - 函数式编程：处理频率的持久列表。项目更新有效吗？

Question

鉴于：

1. 你有一个项目列表。
2. 您正在使用持久数据结构。
3. 您将频繁更新列表中的持久性项目（数据结构）。
4. 正在修改的项目可能位于列表中的任何位置。

Lisps 常用的单链表结构在此目的上似乎不是很有效。每次更改项目时，我们都需要提供一个新的持久列表，用扩充的项目替换原始项目。我知道，对于单链表，您可以重复使用项目替换点之后的尾部，但这看起来仍然很浪费。

什么样的持久性数据结构会成为这种场景的好清单？

Answer 1

Clojure为此提供了向量类型。

它有一个有趣的实现——一个小数组树——它允许log_32(n)复杂的随机访问。更多关于http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/的信息。

counting conj（推）和ing的操作pop都是O(1)针对向量的。