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

Daniel Stutzbach daniel at stutzbachenterprises.com
Tue Apr 24 02:37:12 CEST 2007

On 4/23/07, Adam Olsen <rhamph at gmail.com> wrote:
> 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?

getitem and setitem have no effect on the BList's internal structure
(and thus no effect on memory usage).  Only operations that add or
remove elements do.

> A random.shuffle() benchmark might be a better a better demonstration
> of the overall costs.

Here you go: http://stutzbachenterprises.com/fig/shuffle.html

The regular list's has an advantage due to the special casing of x[k]
within the Python bytecode interpreter.  After that, the O(log n) cost
of BList's item is visible in the right-hand graph via the step at
n=128.  The next step would be at n=16384.

Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC

More information about the Python-3000 mailing list