On Mon, Jan 25, 2010 at 12:24 PM, Steve Howell <showel...@yahoo.com> wrote:
> Hi Daniel, I agree with what Raymond Hettinger says toward the top of > the PEP. Blist, while extremely useful, does seem to have to trade > off performance of common operations, notably "get item", in order to > get better performance for other operations (notably insert/delete). > Actually, the latest version of blist is competitive for "get item" and similar operations. See: http://stutzbachenterprises.com/performance-blist/item http://stutzbachenterprises.com/performance-blist/set-item http://stutzbachenterprises.com/performance-blist/lifo http://stutzbachenterprises.com/performance-blist/shuffle I added a flat cache of the leaf nodes, yielding O(1) get/set item operations whenever those operations dominate over insert/delete operations. The cache adds around 1.5% memory overhead. > My algorithm does exactly N pops and roughly N list accesses, so I > would be going from N*N + N to N + N log N if switched to blist. That > would be at least a theoretical gain over the current performance, but > if pop() were O(1), I could get the whole thing down to N time. > If I understand correctly, you feel strongly that a list.pop(0) that runs in O(n) time is "broken", but you're comfortable with a list.pop(1) that runs in O(n) time. Is that correct? How do you feel about a bisect.insort(list, item) that takes O(n) time? Different people are bound to have different opinions about which operations are most important and where lies the best tradeoff between different operations (as well as code complexity). I am not sure why you feel so strongly that particular spot is best. Obviously, I prefer a slightly different spot, but I also respect the core developers' choice. -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-- http://mail.python.org/mailman/listinfo/python-list
