Taylor R Campbell wrote:
What space usage are random-access lists guaranteed to exhibit? Growth order and constant factors are both interesting -- growth order to specify in the SRFI, and constant factors to satisfy my curiosity.
Representing a random-access list of n elements takes O(n) space, just as with sequential lists.
A random-access list is a forest of complete binary trees. The forest contains at most log n trees, and the space of each tree is proportional to the number of elements it contains. If you represent binary trees using pairs [*], then it takes m-1 pairs to represent a complete binary tree with m elements. The forest can be represented as a list, and thus takes a pair per tree, which is at most log n. So the overall space consumption need not be more than n + log n. My implementation stores the size of each tree in the forest making it n + 2 * log n.
Does this answer your question satisfactorily? (I will respond to the benchmark question separately).
David[*] With the caveat that these pairs be distinguishable from any kind of data you wish to store in a random-access list, hence my use of records.