Asp Forum - List as FIFO in for loop

malkarouri

3/8/2008 2:43:00 PM

Hi everyone,

I have an algorithm in which I need to use a loop over a queue on
which I push values within the loop, sort of:

while not(q.empty()):
x = q.get()
#process x to get zero or more y's
#for each y:
q.put(y)

The easiest thing I can do is use a list as a queue and a normal for
loop:

q = [a, b, c]

for x in q:
#process x to get zero or more y's
q.append(y)

It makes me feel kind of uncomfortable, though it seems to work. The
question is: is it guaranteed to work, or does Python expect that you
wouldn't change the list in the loop?

Regards,

Muhammad Alkarouri

13 Answers

Roel Schroeven

3/8/2008 3:21:00 PM

malkarouri schreef:
> Hi everyone,
>
> I have an algorithm in which I need to use a loop over a queue on
> which I push values within the loop, sort of:
>
> while not(q.empty()):
> x = q.get()
> #process x to get zero or more y's
> #for each y:
> q.put(y)
>
> The easiest thing I can do is use a list as a queue and a normal for
> loop:
>
> q = [a, b, c]
>
> for x in q:
> #process x to get zero or more y's
> q.append(y)
>
> It makes me feel kind of uncomfortable, though it seems to work. The
> question is: is it guaranteed to work, or does Python expect that you
> wouldn't change the list in the loop?

Changing a loop while iterating over it is to be avoided, if possible.
In any case, a deque is more efficient for this kind of use. I'd use it
like this:

from collections import deque

q = deque([a, b, c])
while q:
x = q.popleft()
# ...
q.append(y)

--
The saddest aspect of life right now is that science gathers knowledge
faster than society gathers wisdom.
-- Isaac Asimov

Roel Schroeven

duncan smith

3/8/2008 3:52:00 PM

malkarouri wrote:
> Hi everyone,
>
> I have an algorithm in which I need to use a loop over a queue on
> which I push values within the loop, sort of:
>
> while not(q.empty()):
> x = q.get()
> #process x to get zero or more y's
> #for each y:
> q.put(y)
>
> The easiest thing I can do is use a list as a queue and a normal for
> loop:
>
> q = [a, b, c]
>
> for x in q:
> #process x to get zero or more y's
> q.append(y)
>
> It makes me feel kind of uncomfortable, though it seems to work. The
> question is: is it guaranteed to work, or does Python expect that you
> wouldn't change the list in the loop?
>

I have used exactly the same approach. I think it's a clean (even
elegant) solution. I'd be surprised if it ceased to work in some future
implementation of Python, but I don't know if that's absolutely guaranteed.

Duncan

malkarouri

3/8/2008 4:01:00 PM

On Mar 8, 3:20 pm, Roel Schroeven <rschroev_nospam...@fastmail.fm>
wrote:
> malkarouri schreef:
>
>
>
> > Hi everyone,
>
> > I have an algorithm in which I need to use a loop over a queue on
> > which I push values within the loop, sort of:
>
> > while not(q.empty()):
> > x = q.get()
> > #process x to get zero or more y's
> > #for each y:
> > q.put(y)
>
> > The easiest thing I can do is use a list as a queue and a normal for
> > loop:
>
> > q = [a, b, c]
>
> > for x in q:
> > #process x to get zero or more y's
> > q.append(y)
>
> > It makes me feel kind of uncomfortable, though it seems to work. The
> > question is: is it guaranteed to work, or does Python expect that you
> > wouldn't change the list in the loop?
>
> Changing a loop while iterating over it is to be avoided, if possible.
> In any case, a deque is more efficient for this kind of use. I'd use it
> like this:
>
> from collections import deque
>
> q = deque([a, b, c])
> while q:
> x = q.popleft()
> # ...
> q.append(y)
>
> --
> The saddest aspect of life right now is that science gathers knowledge
> faster than society gathers wisdom.
> -- Isaac Asimov
>
> Roel Schroeven

Thanks for your response. My same feeling, avoid loop variable, but no
explicit reason.
Thanks for reminding me of the deque, which I never used before.
Alas, in terms of efficiency - which I need - I don't really need to
pop the value on the list/deque.
This additional step takes time enough to slow the loop a lot. So its
not ideal here.

Still, why avoid changing loop variable? Does python treat looping
over a list differently from looping over an iterator, where it
doesn't know if the iterator future changes while loop running?

Regards,

Muhammad Alkarouri

malkarouri

3/8/2008 4:20:00 PM

On Mar 8, 3:52 pm, duncan smith <buzz...@urubu.freeserve.co.uk> wrote:
> malkarouri wrote:
> > Hi everyone,
>
> > I have an algorithm in which I need to use a loop over a queue on
> > which I push values within the loop, sort of:
>
> > while not(q.empty()):
> > x = q.get()
> > #process x to get zero or more y's
> > #for each y:
> > q.put(y)
>
> > The easiest thing I can do is use a list as a queue and a normal for
> > loop:
>
> > q = [a, b, c]
>
> > for x in q:
> > #process x to get zero or more y's
> > q.append(y)
>
> > It makes me feel kind of uncomfortable, though it seems to work. The
> > question is: is it guaranteed to work, or does Python expect that you
> > wouldn't change the list in the loop?
>
> I have used exactly the same approach. I think it's a clean (even
> elegant) solution. I'd be surprised if it ceased to work in some future
> implementation of Python, but I don't know if that's absolutely guaranteed.
>
> Duncan

Thanks Duncan, I think I will go ahead and use it. Though the Python
tutorial says otherwise in section 4.2:
"It is not safe to modify the sequence being iterated over in the loop
(this can only happen for mutable sequence types, such as lists). If
you need to modify the list you are iterating over (for example, to
duplicate selected items) you must iterate over a copy.".

More explicitly, in 7.3 of the Python Reference Manual:
"Warning: There is a subtlety when the sequence is being modified by
the loop (this can only occur for mutable sequences, i.e. lists). An
internal counter is used to keep track of which item is used next, and
this is incremented on each iteration. When this counter has reached
the length of the sequence the loop terminates. This means that if the
suite deletes the current (or a previous) item from the sequence, the
next item will be skipped (since it gets the index of the current item
which has already been treated). Likewise, if the suite inserts an
item in the sequence before the current item, the current item will be
treated again the next time through the loop."
This can be interpreted as don't play with the past. However, the part
"When this counter has reached the length of the sequence the loop
terminates." is interpretable as either the starting sequence length
or the running sequence length.

Testing:

In [89]: x=range(4)

In [90]: for i in x:
....: print i
....: x.append(i+4)
....: if i>=8:break
....:
....:
0
1
2
3
4
5
6
7
8

So it is the running sequence length. But I am still not sure if that
is guaranteed.

Regards,

Muhammad Alkarouri

Martin v. Loewis

3/8/2008 4:44:00 PM

> Still, why avoid changing loop variable? Does python treat looping
> over a list differently from looping over an iterator, where it
> doesn't know if the iterator future changes while loop running?

Take a look at Objects/listobject.c:listiterobject. It contains
an it_index, which is the index into the list of the current
iterator position.

So if you delete items with indices smaller than the iterator
index, the iterator index won't change, causing the iterator
to skip over elements, e.g.

L=range(10)
for i in L:
print i
del L[0]

Appending to lists will cause the new elements to
be iterated over later. Whether that's desirable or not depends
on the application. E.g. the following loop never terminates

L=range(10:
for i in L:
L.append(i)

Notice that the language specification *deliberately* does not
distinguish between deletion of earlier and later items, but
makes modification of the sequence undefined behavior to allow
alternative implementations. E.g. an implementation that would
crash, erase your hard disk, or set your house in flames if you
confront it with your code still might be a conforming Python
implementation.

Regards,
Martin

rockingred

3/8/2008 6:25:00 PM

On Mar 8, 9:43 am, malkarouri <malkaro...@gmail.com> wrote:
> Hi everyone,
>
> I have an algorithm in which I need to use a loop over a queue on
> which I push values within the loop, sort of:
>
> while not(q.empty()):
> x = q.get()
> #process x to get zero or more y's
> #for each y:
> q.put(y)
>
> The easiest thing I can do is use a list as a queue and a normal for
> loop:
>
> q = [a, b, c]
>
> for x in q:
> #process x to get zero or more y's
> q.append(y)
>
> It makes me feel kind of uncomfortable, though it seems to work. The
> question is: is it guaranteed to work, or does Python expect that you
> wouldn't change the list in the loop?
>
> Regards,
>
> Muhammad Alkarouri

I think it's a bad practice to get into. Did you intend to do the
"process" step again over the added variables? If not I would set a
new variable, based on your awful naming convention, let's call it z.
Then use z.append(y) within the for loop and after you are out of your
for loop, q.append(z).

Aaron Brady

3/8/2008 8:27:00 PM

> Notice that the language specification *deliberately* does not
> distinguish between deletion of earlier and later items, but
> makes modification of the sequence undefined behavior to allow
> alternative implementations. E.g. an implementation that would
> crash, erase your hard disk, or set your house in flames if you
> confront it with your code still might be a conforming Python
> implementation.

Actually, PEP 4122 makes this a SetHouseInFlames error. Do you want
to include this one? Just use _toaddafter= type( container )().

P.S. Equivalence class light, on the rocks.

malkarouri

3/8/2008 10:21:00 PM

On Mar 8, 4:44 pm, "Martin v. Löwis" <mar...@v.loewis.de> wrote:
...
> Notice that the language specification *deliberately* does not
> distinguish between deletion of earlier and later items, but
> makes modification of the sequence undefined behavior to allow
> alternative implementations. E.g. an implementation that would
> crash, erase your hard disk, or set your house in flames if you
> confront it with your code still might be a conforming Python
> implementation.

Really appreciated, Martin. It was exactly the *deliberately* part I
am interested in. Settles it for me.

Thanks,

Muhammad Alkarouri

malkarouri

3/8/2008 10:37:00 PM

On Mar 8, 6:24 pm, rockingred <willsteve2...@yahoo.ca> wrote:
> I think it's a bad practice to get into. Did you intend to do the
> "process" step again over the added variables? If not I would set a
> new variable, based on your awful naming convention, let's call it z.
> Then use z.append(y) within the for loop and after you are out of your
> for loop, q.append(z).

Thanks, rockingred, for the advice. I hope that you didn't assume that
I was a newbie, even if my question looks so. What I was trying to do
is write some Python code which I need to optimize as much as
possible. I am using Cython (Pyrex) and would probably end up
rewriting my whole module in C at one point, but it is really hard to
beat Python data structures at their home turf. So meanwhile, I am
making use of dubious optimizations - on my own responsibility. There
have been a lot of these along the years - like using variables
leaking from list expressions (not anymore). Think of it as a goto.
Yes, I intend to do the process step again over the added variables.
The suggested deque is probably the best, though I need the speed
here.
What are the variable naming you would suggest, for a throwaway -
probably anonymized for the same of publishing on the web - code?

Cheers,

Muhammad Alkarouri

Carl Banks

3/8/2008 10:43:00 PM

comp.lang.python

List as FIFO in for loop

malkarouri

Roel Schroeven

duncan smith

malkarouri

malkarouri

Martin v. Loewis

rockingred

Aaron Brady

malkarouri

malkarouri

Carl Banks

x Login to ForumsZone