[Python-3000] Two proposals for a new list-like type: one modest, one radical

Adam Olsen 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
slicing.

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 mailing list