"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). 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.
A naive implementation of iteration would be O(nlogn), with a minimal amount of work, it could be optimized to O(nlogn) worst case (mutations all the time everywhere) but O(n) when no mutations occur (the majority of iteration cases seen in the wild). > What's the performance of concatenation in these BLists? O(n) ? It would seem to be O(1), because one could trivially add a single new node that points to the copy-on-write root nodes of each input tree. At worst, it would take O(log n + log m) to combine the rightmost branch of the left addend and the leftmost branch of the right addend. > Are you suggesting BList as part of the standard library? He is, in fact, suggesting it as a replacement for list(). - Josiah _______________________________________________ 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
