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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4