[Python-3000] Two proposals for a new list-like type: one modest, one radical
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
> 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