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

[Daniel Stutzbach]

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