一句话：提出两种随机访问表变体，将 cons 表任意元素访问的指针遍历上界从 3⌈lg n⌉−5 改进至接近信息论最优。
单链表（cons 表）的任意元素访问最坏需线性遍历指针。applicative random-access list 将这一代价降至对数级，此前最好上界为 3⌈lg n⌉−5。本文研究如何进一步逼近信息论下界 ⌈lg(n+1)⌉−1。作者先给出一个简单变体，把访问任意元素的指针遍历次数上界改进为 2⌈lg(n+1)⌉−3；随后提出更复杂的变体，对任意 σ≥1 达到 (1+1/σ)⌊lg n⌋+σ+9。该结果表明，在保持 cons 表式接口的同时，随机访问的遍历代价可以渐近接近信息论最优。评估以最坏情况指针遍历次数的上界证明为主，并与已有随机访问表及信息论下界比较。
Accessing an arbitrary element of a singly linked list or cons list requires traversing up to a linear number of pointers. The applicative random-access list is a data structure that behaves like a cons list except that accessing an arbitrary element traverses only a logarithmic number of pointers. Specifically, in a list of length n , an arbitrary element can be accessed by traversing at most 3 ⌈ lg n ⌉ − 5 pointers. In this paper, we present a simple variation on random-access lists that improves this bound and requires traversing at most 2 ⌈ lg ( n + 1 ) ⌉ − 3 pointers. We then present a more complicated variation that improves this bound to ( 1 + 1 σ ) ⌊ lg n ⌋ + σ + 9 for any σ ≥ 1 . This shows that it is possible to get asymptotically close to the information-theoretically optimal bound of ⌈ lg ( n + 1 ) ⌉ − 1 .
@article{paperbot3034,
title = {Pushing the Information-Theoretic Limits of Random Access Lists: Traversing Cons Lists in (1 + 1/𝜎 ) ⌊lg 𝑛⌋ + 𝜎 + 9 Steps},
author = {Edward Peters and Yong Qi Foo and Michael D. Adams},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {ICFP},
year = {2025},
doi = {10.1145/3747536}
}