[Python-Dev] FIFO data structure?
Sun, 20 Apr 2003 06:53:41 -0400 (CLT)
i haven't looked at the code, but when you mention lists are you referring
to standard python structures? i understood that the thing in python that
looks like a list is actually an array (a simple one, not a vlist), so
access to index elements is done in constant time.
however, that doesn't necesarily alter your argument as using an array for
a fifo queue in a naieve manner is going to cause problems too (unless the
implementation explicitly implements a circular buffer, say, or the array
implementation is clever enough to drop leading elements whch contain
nulls - note that circular buffers are a bit tricky to extend in size).
see eg http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52246
(the links you gave don't work for me.)
Jeremy Fincher said:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 2.3 seems to focus somewhat on adding a wider variety of data structures
> Python -- well, sets and heapq, at least :) One thing I've found lacking,
> though, is a nice O(1) FIFO queue -- even the standard Queue module
> underlying uses a list as a queue, which means the dequeue operation is
> in the size of the queue. I'm curious what the possiblity of getting a
> module (which would probably have to be named "fifo", since Queue is
> taken and some operating systems use case-insensitive filesystems) added
> the standard library would be.
> If it is a possibility, I have a pure-Python implementation using the
> mechanism described at
> The module itself is at <http://www.cis.ohio-state.edu/fifo.py>; the tests
> are at <http://www.cis.ohio-state.edu/test_fifo.py>.
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.1 (FreeBSD)
> -----END PGP SIGNATURE-----
> Python-Dev mailing list