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

Daniel Stutzbach agthorr at barsoom.org
Mon Apr 23 19:53:34 CEST 2007

On 4/23/07, Neville Grech Neville Grech <nevillegrech at gmail.com> wrote:

I like the implementation of the BList, however I'm not so sure whether replacing a list with BList is a good idea since there are many instances where python scripts will iterate through endless lists of items. In such case time complexity (to iterate a whole list) as you have mentioned is O (nlog(n)) instead of O(n).

Iteration using an iterator object is O(n). For example, see the left-hand graph at: http://stutzbachenterprises.com/blist/forloop.html

Of course, the following idiom is still O(n log n):

for i in range(len(x)): do_something(x[i])

(but the base of the logarithm is large, so for n < 100 or so, ceil(log n) = 1)

You will probably find that such cases (iterating through long lists) are very common and at the same time the developer still wants his lists to be mutable. If a developer wants to optimise his lists for insertion and deletion speed he can then use an optimised implementation like the one you're proposing anyway.

What's the performance of concatenation in these BLists? O(n) ?

Concatenating a BList to a BList is O(log n + log m) where n and m are the size of the two BLists.

Concatenating any other iterable to a BList is (log n + m) where n is the size of the BList and m is the length of the iterable.

Are you suggesting BList as part of the standard library?

I'm making two mutually exclusive but related suggestions:

  1. Add BList to the standard library as part of the collections module (which I hope will be accepted), or
  2. Replace list() with BList (which I expect to be rejected)

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

More information about the Python-3000 mailing list