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 <[EMAIL PROTECTED]> wrote:
On 4/23/07, Neville Grech Neville Grech <[EMAIL PROTECTED]> 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
_______________________________________________
Python-3000 mailing list
Python-3000@python.org
http://mail.python.org/mailman/listinfo/python-3000
Unsubscribe:
http://mail.python.org/mailman/options/python-3000/archive%40mail-archive.com
