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

[Neville Grech Neville Grech]

You're right (I was seeing the statistics). Seems that it will outperform
the built in list in most cases then. I would be +1 for both proposals if
there are no underlying integration issues. Great work.

On 4/23/07, Daniel Stutzbach <agthorr at barsoom.org> wrote:
>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/python-3000/attachments/20070423/2a4efde8/attachment.html