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

*To*: Taylor R Campbell <campbell@xxxxxxxxxx>*Subject*: Re: performance*From*: David Van Horn <dvanhorn@xxxxxxxxxxxxxxx>*Date*: Fri, 18 Sep 2009 08:21:51 -0400*Cc*: srfi-101@xxxxxxxxxxxxxxxxx*Delivered-to*: srfi-101@xxxxxxxxxxxxxxxxx*In-reply-to*: <20090918031501.3471DE403F@xxxxxxxxxxxxxxxx>*References*: <20090918031501.3471DE403F@xxxxxxxxxxxxxxxx>*User-agent*: Thunderbird 2.0.0.23 (Macintosh/20090812)

Taylor R Campbell wrote:

Date: Thu, 17 Sep 2009 20:53:55 -0400 From: David Van Horn <dvanhorn@xxxxxxxxxxxxxxx> 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, justas with sequential lists.I ought to have been more precise: while of course it takes O(n) space to store a sequence of n elements, I was interested more in the amount of extra space. E.g., in most systems, a vector of length n will use a constant amount of extra space (a header with its length at the beginning), while a list of length n will use O(n) extra space (one car for each element, plus one cdr extra space for each element, and sometimes another word for a header or similar).

A random-access list is a forest of complete binary trees. The forestcontains at most log n trees, and the space of each tree is proportionalto the number of elements it contains. If you represent binary treesusing pairs [*], then it takes m-1 pairs to represent a complete binarytree with m elements. The forest can be represented as a list, and thustakes a pair per tree, which is at most log n. So the overall spaceconsumption need not be more than n + log n. My implementation storesthe size of each tree in the forest making it n + 2 * log n.I'm a little puzzled by the formulae you've computed here. If my cursory examination of the reference implementation is right, the trees have data associated with each internal node, not with the leaves. So you need one location for each element, one location for each left branch, and one location for each right branch, for a total of 2 n extra locations in each tree, plus whatever constant overhead each tree has: + 1 for the size, + 1 for the node, + 1 for the link to the next tree? This sounds like a total space usage of 3 n + 3 log n, neglecting the overhead of records, which means an extra space usage of 2 n + 3 log n = O(n). I suppose I ought to have expected that, though.

David

**Follow-Ups**:**Re: performance***From:*Taylor R Campbell

**References**:**Re: performance***From:*Taylor R Campbell

- Prev by Date:
**Re: performance** - Next by Date:
**Re: performance** - Previous by thread:
**Re: performance** - Next by thread:
**Re: performance** - Index(es):