deque vs list: performance notes

[Peter Schneider-Kamp]

Courageous wrote:
> 
> A C-native bidirectionally linked list (deque) was
> tested versus the performance of native python lists
> as a LIFO. Items were appended to the end of each
> data structure, but always removed from the beginning.

You win ;-) I've been working on the same but couldn't
get all the things like "__add__", "__repr__" working
correctly together. But to get some numbers out, I
implemented a Python only version and timed that for
the same scenario as you (actually only the 10000
and the 100,000 element cases):

#              deque(tottime)            list(tottime)

10,000                    3.28                    0.94
100,000                  32.68                  173.47

Conclusions:

Even a pure Python implementation beats Python lists
if used as a FIFO. I agree with Courageous that Python
lists are in general very useful and efficient, but I
would like to have a choice. My proposal would be to
include them as a standard module much like the array
module. Somebody who does not know what a deque is
will not use them and someone who knows he might need
it, will use them.

it's-getting-bad-for-deques-with-random-access-though-ly y'rs
Peter

P.S.: Can you send me your deque implementation?
      I'd like to see how you handle things.
--
Peter Schneider-Kamp          ++47-7388-7331
Herman Krags veg 51-11        mailto:peter at schneider-kamp.de
N-7050 Trondheim              http://schneider-kamp.de