<div class="gmail_quote">On Mon, Jan 25, 2010 at 12:24 PM, Steve Howell <span dir="ltr"><<a href="mailto:showell30@yahoo.com" target="_blank">showell30@yahoo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Hi Daniel, I agree with what Raymond Hettinger says toward the top of<br>
the PEP.  Blist, while extremely useful, does seem to have to trade<br>
off performance of common operations, notably "get item", in order to<br>
get better performance for other operations (notably insert/delete).<br></blockquote><div><br>Actually, the latest version of blist is competitive for "get item" and similar operations.  See:<br><br><a href="http://stutzbachenterprises.com/performance-blist/item" target="_blank">http://stutzbachenterprises.com/performance-blist/item</a><br>

<a href="http://stutzbachenterprises.com/performance-blist/set-item" target="_blank">http://stutzbachenterprises.com/performance-blist/set-item</a><br><a href="http://stutzbachenterprises.com/performance-blist/lifo" target="_blank">http://stutzbachenterprises.com/performance-blist/lifo</a><br>

<a href="http://stutzbachenterprises.com/performance-blist/shuffle" target="_blank">http://stutzbachenterprises.com/performance-blist/shuffle</a><br><br>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.<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
My algorithm does exactly N pops and roughly N list accesses, so I<br>
would be going from N*N + N to N + N log N if switched to blist.  That<br>
would be at least a theoretical gain over the current performance, but<br>
if pop() were O(1), I could get the whole thing down to N time.<br></blockquote><div><br>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? <br>
<br>How do you feel about a bisect.insort(list, item) that takes O(n) time?<br>

<br>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.<br>
<br>Obviously, I prefer a slightly different spot, but I also respect the core developers' choice.<br></div></div><blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>