[Python-3000] Two proposals for a new list-like type: one modest, one radical
rhamph at gmail.com
Tue Apr 24 01:32:45 CEST 2007
On 4/23/07, Daniel Stutzbach <daniel at stutzbachenterprises.com> wrote:
> If a user creates a BList from whole-cloth (e.g., BList(iterable)),
> they will get a best-case BList. This would probably be the common
> case for user's who don't plan to modify their list much.
> If a user is doing lots of inserts and deletes, the BList's node's
> will typically be three-quarters full, translating into 33% extra
> memory above a regular Python list. However (and this is a big
> however!), these users will greatly appreciate the BList's additional
> speed for these operations.
For contrast, the existing list seems to over-allocate by 12.5%, for
an average of 6.25% wasted. However, when deleting it only resizes
when it drops below half full, leaving it with a worst case of 100%,
the same as BList.
The usage patterns can make a big difference there though. A list's
worst-case is only reached if you have a spike, then drop to just
above half-full. A BList's worst-case is reached through random
Daniel, does repeated getitem/setitem (as in random.shuffle())
increase memory usage, or does it have no effect?
A random.shuffle() benchmark might be a better a better demonstration
of the overall costs.
Adam Olsen, aka Rhamphoryncus
More information about the Python-3000