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

*To*: srfi-101@xxxxxxxxxxxxxxxxx*Subject*: performance*From*: Taylor R Campbell <campbell@xxxxxxxxxx>*Date*: Thu, 17 Sep 2009 15:46:36 -0400*Delivered-to*: srfi-101@xxxxxxxxxxxxxxxxx*User-agent*: IMAIL/1.21; Edwin/3.116; MIT-Scheme/7.7.90.+

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?

**Follow-Ups**:**Re: performance***From:*David Van Horn

**Re: performance***From:*David Van Horn

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