Understanding Clojure's Persistent Vectors, pt. 1 (2013)
5 days ago
- #Clojure
- #Persistence
- #Data Structures
- Clojure中的持久化向量实现了近乎常数时间的追加、更新、查找和子向量操作。
- 它们通过在平衡树中使用路径复制来实现持久性，避免了完整的数组复制。
- 更新操作会复制目标叶节点路径上的所有节点，并替换其中的值。
- 追加操作处理三种情况：叶节点有空位、需要创建新节点，或根节点溢出。
- 弹出操作移除最后一个元素，涉及叶节点删除、空节点清理和根节点缩减等情况。
- 具有高分支因子（Clojure中为32）的浅层树使得这些操作的实际时间复杂度接近O(1)。