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

[Josiah Carlson]

"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). 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.

A naive implementation of iteration would be O(nlogn), with a minimal
amount of work, it could be optimized to O(nlogn) worst case (mutations
all the time everywhere) but O(n) when no mutations occur (the majority
of iteration cases seen in the wild).


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

It would seem to be O(1), because one could trivially add a single new
node that points to the copy-on-write root nodes of each input tree.  At
worst, it would take O(log n + log m) to combine the rightmost branch of
the left addend and the leftmost branch of the right addend.


> Are you suggesting BList as part of the standard library?

He is, in fact, suggesting it as a replacement for list().

 - Josiah