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.<br><br><div><span class="gmail_quote">
On 4/23/07, <b class="gmail_sendername">Daniel Stutzbach</b> <<a href="mailto:agthorr@barsoom.org">agthorr@barsoom.org</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On 4/23/07, Neville Grech Neville Grech <<a href="mailto:nevillegrech@gmail.com">nevillegrech@gmail.com</a>> wrote:<br>> I like the implementation of the BList, however I'm not so sure whether<br>> replacing a list with BList is a good idea since there are many instances
<br>> where python scripts will iterate through endless lists of items. In such<br>> case time complexity (to iterate a whole list) as you have mentioned is O<br>> (nlog(n)) instead of O(n).<br><br>Iteration using an iterator object is O(n). For example, see the
<br>left-hand graph at:<br> <a href="http://stutzbachenterprises.com/blist/forloop.html">http://stutzbachenterprises.com/blist/forloop.html</a><br><br>Of course, the following idiom is still O(n log n):<br><br>for i in range(len(x)):
<br> do_something(x[i])<br><br>(but the base of the logarithm is large, so for n < 100 or so, ceil(log n) = 1)<br><br>> You will probably find that such cases (iterating<br>> through long lists) are very common and at the same time the developer still
<br>> wants his lists to be mutable. If a developer wants to optimise his lists<br>> for insertion and deletion speed he can then use an optimised implementation<br>> like the one you're proposing anyway.<br>
><br>> What's the performance of concatenation in these BLists? O(n) ?<br><br>Concatenating a BList to a BList is O(log n + log m) where n and m are<br>the size of the two BLists.<br><br>Concatenating any other iterable to a BList is (log n + m) where n is
<br>the size of the BList and m is the length of the iterable.<br><br>> Are you suggesting BList as part of the standard library?<br><br>I'm making two mutually exclusive but related suggestions:<br><br>1) Add BList to the standard library as part of the collections module
<br>(which I hope will be accepted), or<br>2) Replace list() with BList (which I expect to be rejected)<br><br>--<br>Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises LLC<br></blockquote></div><br>