efficient idiomatic queue?

David Eppstein eppstein at ics.uci.edu
Tue Jan 15 18:24:12 CET 2002


In article <mailman.1011111645.10873.python-list at python.org>,
 "Jason Orendorff" <jason at jorendorff.com> wrote:

> > I'm not sure what you mean by quick enough, but when I tried draining a
> > list by repeated del L[0], on lists of 10000 elements it took roughly a
> > second -- more time than I'd like to spend in most interactive situations.
> 
> All you had to say was, "5000 items won't do it for me.  I want
> genuine O(N log N) behavior."

I didn't say it that way because I think it's important to understand why 
good asymptotics are important, and under what circumstances it would be ok 
to use slower algorithms, rather than just blindly using the math.

Anyway, thanks for all the solutions posted so far.
The reverse trick is looking cleanest for merge sort, although Alex M.'s 
queue implementation looks good (better I think than the more obvious 
linked list version) and I also like the ADT-ized generator version.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/



More information about the Python-list mailing list