clojure - 函数式编程 : persistent list that handles freq. 项目更新效率高？

Question

给定:

1. 您有一个项目列表。
2. 您正在使用持久数据结构。
3. 您将经常更新列表中的持久项(数据结构)。
4. 正在修改的项目可能位于列表中的任何位置。

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

什么样的持久数据结构适合这种情况？

Answer 1

Clojure 提供了 vector为此键入。

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

counting conjing (pushing) 和poping 操作都是O(1)载体。