Heuristics That Dynamically Organize Data Structures
Heuristics That Dynamically Organize Data Structures
复制标题
动态组织数据结构的启发式方法
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
J. Bitner
中科院分区：
文献类型：
--
作者：
J. Bitner
我们首先考虑动态改变链接列表的启发式方法，导致更频繁访问的键移近列表的“顶部”。我们证明移到前面规则比转置规则更快地减少访问时间，然后给出这两个规则的“混合”，它快速减少访问时间并且具有较低的渐近成本。我们还讨论了假设计数器与每个键相关联的规则。其次，我们考虑二叉搜索树的规则。仅当关键请求的概率分布的熵较低时，单调树规则才表现良好；否则，不会减少访问时间。使用轮换的最后一类规则提供了近乎最佳的性能。
We first consider heuristics that dynamically alter linked lists, causing more frequently accessed keys to move nearer the “top” of the list. We show that the move to front rule reduces the access time much more quickly than the transposition rule, then give a “hybrid” of these two rules which decreases the access time quickly and has low asymptotic cost. We also discuss rules that assume a counter is associated with each key. Second, we consider rules for binary search trees. The monotonic tree rule performs well only when the entropy of the probability distribution for key requests is low; otherwise, it does not reduce the access time. A final class of rules using rotations give nearly optimal performance.