This page is part of the web mail archives of SRFI 101 from before July 7th, 2015. The new archives for SRFI 101 are here. Eventually, the entire history will be moved there, including any new messages.
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.