[Python-Dev] FIFO data structure?

[andrew cooke]

hi,

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.)

cheers,
andrew

Jeremy Fincher said:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> 2.3 seems to focus somewhat on adding a wider variety of data structures
> to
> 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
> O(N)
> in the size of the queue.  I'm curious what the possiblity of getting a
> queue
> module (which would probably have to be named "fifo", since Queue is
> already
> taken and some operating systems use case-insensitive filesystems) added
> to
> the standard library would be.
>
> If it is a possibility, I have a pure-Python implementation using the
> mechanism described at
> <http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=a23cjl%24dps%241%40serv1.iunet.it>.
> 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>.
>
> Jeremy
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.1 (FreeBSD)
>
> iD8DBQE+omVRqkDiu+Bs+JIRAilOAKCWe7CfZqyBboi/zGZ5jHxnKSiS5ACfTBEt
> D2Hz+k7dzXTW3HjXByzlA2M=
> =juHN
> -----END PGP SIGNATURE-----
>
>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev@python.org
> http://mail.python.org/mailman/listinfo/python-dev
>
>


-- 
http://www.acooke.org/andrew