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