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


Do you have any performance tests to show that the asymptotic
improvements are worth the constant factors?  Examples of complex
programs that are best expressed using this data structure, and which
consequently perform much better than the would with vanilla lists?

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.

For instance, while this is not guaranteed, a list of length n will
usually occupy O(n) storage, and in particular usually no more than 4
n words of memory.  A vector of length n will also usually occupy O(n)
storage, often with O(1) extra space, and in particular usually no
more than 2 n + 4 or so words of memory and often no more than n + 1.

Assuming the overhead of every record is a constant, how does the
space used by a random-access list grow as a function of its length;
and, given the constant overhead of a record, and assuming that there
is one word of memory per field per record, how many words does a
random-access list of length n occupy?