efficient idiomatic queue?
eppstein at ics.uci.edu
Tue Jan 15 12:24:12 EST 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, 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