[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: performance

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.