An adaptive packed-memory array
An adaptive packed-memory array
复制标题
自适应打包内存阵列
DOI：
10.1145/1142351.1142355
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Haodong Hu
中科院分区：
文献类型：
--
作者：
M. A. Bender;Haodong Hu
封装存储器阵列（PMA）是在大小为Θ（N）的阵列中以排序顺序维持N个元素的动态集合的数据结构。其思想是在元素之间散布Θ（N）个空白空间或间隙，使得在插入或删除时仅需要移动少量元素。由于元素在物理上以排序顺序存储在内存或磁盘中，因此PMA可用于支持极其高效的范围查询。具体地说，扫描L个连续元素的成本是O（1+L/B）的存储器传输。与原始PMA一样，任何模式的更新每次更新都只花费O（log 2 N）的摊销元素移动和O（1+（log 2 N）/B）的摊销内存传输。然而，APMA在许多常见的输入分布上表现得更好，仅实现O（logN）摊销的元素移动和O（1+（logN）/B）摊销的内存传输。本文分析了顺序插入，其中的插入是在APMA的前面，锤插入，其中的插入“锤”在APMA的一部分，随机插入，其中的插入是在APMA中的随机元素之后，和散装插入，其中常数α∈[0，1]，Nα元素插入在APMA中的随机元素之后.然后，本文给出的模拟结果是一致的渐近界。对于大约140万个元素的顺序插入，APMA每次插入的元素移动比传统PMA少四倍，运行时间快七倍以上。
The packed-memory array (PMA) is a data structure that maintains a dynamic set of N elements in sorted order in a Θ(N)-sized array. The idea is to intersperse Θ(N) empty spaces or gaps among the elements so that only a small number of elements need to be shifted around on an insert or delete. Because the elements are stored physically in sorted order in memory or on disk, the PMA can be used to support extremely efficient range queries. Specifically, the cost to scan L consecutive elements is O(1+L/B) memory transfers.This paper gives the first adaptive packed-memory array (APMA), which automatically adjusts to the input pattern. Like the original PMA, any pattern of updates costs only O(log2 N) amortized element moves and O(1+(log2 N)/B) amortized memory transfers per update. However, the APMA performs even better on many common input distributions achieving only O(logN) amortized element moves and O(1+(logN)/B) amortized memory transfers. The paper analyzes sequential inserts, where the insertions are to the front of the APMA, hammer inserts, where the insertions "hammer" on one part of the APMA, random inserts, where the insertions are after random elements in the APMA, and bulk inserts, where for constant α∈[0,1], Nα elements are inserted after random elements in the APMA. The paper then gives simulation results that are consistent with the asymptotic bounds. For sequential insertions of roughly 1.4 million elements, the APMA has four times fewer element moves per insertion than the traditional PMA and running times that are more than seven times faster.