[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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).
[*] 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.