RRB-Trees: Efficient Immutable Vectors
RRB-Trees: Efficient Immutable Vectors
复制标题
RRB-Trees：高效的不可变向量
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Tiark Rompf
中科院分区：
文献类型：
--
作者：
P. Bagwell;Tiark Rompf
不变的向量是功能编程的方便数据结构，也是Clojure和Scala等现代语言标准库的一部分。常见的实现基于宽树，每个节点有固定数量的儿童，这允许快速索引查找和更新操作。在本文中，我们使用新的基础数据结构，放松的radix平衡树（RRB-Trees）扩展了矢量数据类型，并显示该结构如何允许在维持O（log n）时间中允许不可变的矢量串联，插入和拆分原始矢量数据结构的索引，更新和迭代速度。
Immutable vectors are a convenient data structure for functional programming and part of the standard library of modern languages like Clojure and Scala. The common implementation is based on wide trees with a fixed number of children per node, which allows fast indexed lookup and update operations. In this paper we extend the vector data type with a new underlying data structure, Relaxed Radix Balanced Trees (RRB-Trees), and show how this structure allows immutable vector concatenation, insert-at and splits in O(log N) time while maintaining the index, update and iteration speeds of the original vector data structure.