efficient idiomatic queue?
Aahz Maruch
aahz at panix.com
Wed Jan 16 07:07:29 EST 2002
In article <a23cjl$dps$1 at serv1.iunet.it>, Alex Martelli <aleax at aleax.it> wrote:
>"David Eppstein" <eppstein at ics.uci.edu> wrote in message
>news:eppstein-3B0408.21320615012002 at news.service.uci.edu...
>> In article <a22rhr$bn1$1 at panix3.panix.com>, aahz at panix.com (Aahz Maruch)
>> wrote:
>>>
>>> Just to be a jerk, why not use a dict with a couple of index variables?
>>
>> Maybe you could unpack that a little? dicts are useful but AFAIK they
>> aren't the same thing as queues, index variables or no.
>
>Well, they obviously CAN be used to IMPLEMENT queues -- performance
>characteristics apart:
>
>class DictFifo:
> def __init__(self):
> self.data = {}
> self.nextin = 0
> self.nextout = 0
> def append(self, value):
> self.data[self.nextin] = value
> self.nextin += 1
> def pop(self):
> value = self.data[self.nextout]
> del self.data[self.nextout]
> self.nextout += 1
>
>No "being the same" asserted or implied, of course -- the dict and
>the two indices are just tools to _implement_ a fifo queue, here.
Yup. Note that for Python < 2.2, you should use:
def __init__(self):
self.data = {}
self.nextin = 0L
self.nextout = 0L
to make sure that you can use it for more than two billion entries. ;-)
I haven't tested this, but I think that if you expect queues to be
large, this might actually be a fast, clear implementation.
--
--- Aahz <*> (Copyright 2002 by aahz at pobox.com)
Hugs and backrubs -- I break Rule 6 http://www.rahul.net/aahz/
Androgynous poly kinky vanilla queer het Pythonista
"There are times when effort is important and necessary, but this should
not be taken as any kind of moral imperative." --jdecker
More information about the Python-list
mailing list