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

[Daniel Stutzbach]

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