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.
<br><br>What's the performance of concatenation in these BLists? O(n) ?<br><br>Are you suggesting BList as part of the standard library?<br><span class="sg"><br>-Neville</span><br><br><div><span class="gmail_quote">On 4/23/07,
<b class="gmail_sendername">Daniel Stutzbach</b> <<a href="mailto:daniel@stutzbachenterprises.com">daniel@stutzbachenterprises.com</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;">
I have two proposals for Python 3000 that I'll write PEP(s) for if<br>there's interest. The first proposal is, I think, a modest one. The<br>second proposal is related, but more radical. I fully expect the<br>second proposal to be rejected for that alone, especially since I am a
<br>relatively an outsider to the Python developer community (though it<br>was great to meet some of you at PyCon this year). I bring up the<br>more radical proposal primarily for completeness.<br><br>The Modest Proposal
<br>-------------------------------<br><br>As a pet project, I've written a container type that looks, acts, and<br>quacks like a Python list(), but has better asymptotic performance.<br>Specifically, O(log n) time for inserts and deletes in the middle of
<br>the list. I'd like to offer it for inclusion in the collections<br>module.<br><br>Probably, you have encountered some other proposals for types that<br>meet this description. Here are some of the unique features of mine,
<br>called a BList, which is based on B+Trees. I'm open to suggestions<br>for a better name.<br><br>- just as fast as a Python list() when the list is small<br>- getslice runs in O(log n) time<br>- making a shallow copy runs in O(1) time
<br>- setslice runs in O(log n + log k) time if the inserted slice is a<br>BList of length k<br>- multipling a BList by k takes O(log k) time and O(log k) memory<br><br>Example:<br><br>>>> from blist import *<br>
>>> x = BList([0])<br>>>> x *= 2**29<br>>>> x.append(5)<br>>>> y = x[4:-234234]<br>>>> del x[3:1024]<br><br>None of the above operations have a noticeable delay, even though the
<br>lists have over 500 million elements due to line 3.<br><br>The BList has two key features that allow it to pull this off this performance:<br><br>1) The BList type features transparent copy-on-write. If a non-root<br>
node needs to be copied (as part of a getslice, copy, setslice, etc.),<br>the node is shared between multiple parents instead of being copied.<br>If it needs to be modified later, it will be copied at that time.<br>This is completely behind-the-scenes; from the user's point of view,
<br>the BList works just like a regular Python list.<br><br>2) A B+Tree is a wide, squat tree. The maximum number of children per<br>node is defined by a compile-time parameter (LIMIT). If the list is<br>shorter than LIMIT, then there is only one node, which simply contains
<br>an array of the objects in the list. In other words, for short lists,<br>a BList works just like Python's array-based list() type. Thus, it<br>has the same good performance on small lists.<br><br>So you can see the performance of the BList in more detail, I've made
<br>several performance graphs available at the following link:<br> <a href="http://stutzbachenterprises.com/blist/">http://stutzbachenterprises.com/blist/</a><br><br>Each webpage shows two graphs:<br> - The raw execution time for the operation as a function of the list size
<br> - The execution time for the operation, normalized by the execution<br>time of Python's list()<br><br>These graphs were made using LIMIT=128.<br><br>The only operation where list() is much faster for small lists is
<br>getitem through the x[5] syntax. There's a special case for that<br>operation deep inside the Python bytecode interpreter. My extension<br>module can't compete with that. :-) BList is just as fast as list()
<br>for small lists via .__getitem__().<br><br>The source code for the type is available for compilation as an external module:<br> <a href="http://stutzbachenterprises.com/blist/blist.tar.gz">http://stutzbachenterprises.com/blist/blist.tar.gz
</a><br><br>I wrote it against Python 2.5.<br><br>The Radical Proposal<br>-------------------------------<br><br>Replace list() with the BList.<br><br>There are only a few use-cases (that I can think of) where Python's
<br>list() regularly outperforms the BList. These are:<br><br>1. A large LIFO stack, where there are many .append() and .pop(-1)<br>operations. These are O(1) for a Python list, but O(log n) for the<br>BList(). (BList's are just as fast for small lists)
<br><br>2. An large, unchanging list, where there are many getitem() calls,<br>and none of the inserts or deletes where the BList() shines. Again,<br>these are O(1) for a Python list, but O(log n) for the BList(), and<br>
the BList() is just as fast if the list is small.<br><br>Use case #1 is covered by collections.deque. Use case #2 is covered by tuples.<br><br>When I first started learning Python, I often ended up inadvertently<br>writing O(n**2) algorithms by putting a O(n) list operation inside a
<br>loop (which is a problem when n=100,000). Since nothing in the<br>signature of list() informs the user when an operation is going to be<br>slow, it took me a while to learn how to write my code to work around<br>this constraint. In fact, I initially assumed "list" meant "linked
<br>list" so most of my assumptions about which operations would be fast<br>vs. slow were backwards. I think it would be more Pythonic if the<br>user can trust that the implementation will always be fast (at least<br>
O(log n)).<br><br>I recognize that the Python developer community is understandably very<br>attached to the current array-based list, so I expect this to get shot<br>down. I hope this doesn't reflect badly on the more modest proposal
<br>of including a new type in the collections module. Also, please don't<br>kill the messenger. :-)<br><br>--<br>Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises LLC<br>_______________________________________________
<br>Python-3000 mailing list<br><a href="mailto:Python-3000@python.org">Python-3000@python.org</a><br><a href="http://mail.python.org/mailman/listinfo/python-3000">http://mail.python.org/mailman/listinfo/python-3000</a><br>
Unsubscribe: <a href="http://mail.python.org/mailman/options/python-3000/nevillegrech%40gmail.com">http://mail.python.org/mailman/options/python-3000/nevillegrech%40gmail.com</a><br></blockquote></div><br>