469,648 Members | 1,436 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,648 developers. It's quick & easy.

List as FIFO in for loop

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
Mar 8 '08 #1
8 4003
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
Mar 8 '08 #2
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
Mar 8 '08 #3
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
Mar 8 '08 #4
On Mar 8, 3:52*pm, duncan smith <buzz...@urubu.freeserve.co.ukwrote:
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
Mar 8 '08 #5
On Mar 8, 9:43*am, malkarouri <malkaro...@gmail.comwrote:
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).
Mar 8 '08 #6
On Mar 8, 4:44*pm, "Martin v. Lwis" <mar...@v.loewis.dewrote:
...
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
Mar 8 '08 #7
On Mar 8, 9:43 am, malkarouri <malkaro...@gmail.comwrote:
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)
Why not just do it like that? With a few changes it'll work fine:

while q:
x = q.pop(0)
for y in process(x):
q.append(y)
And consider collections.deque for q instead of a list, though it
shouldn't make much of a difference if the queue remains small.
Carl Banks
Mar 8 '08 #8
On Mar 8, 10:42*pm, Carl Banks <pavlovevide...@gmail.comwrote:
On Mar 8, 9:43 am, malkarouri <malkaro...@gmail.comwrote:
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)

Why not just do it like that? *With a few changes it'll work fine:

while q:
* * x = q.pop(0)
* * for y in process(x):
* * * * q.append(y)
Or (almost) equivalently...
while q:
x = q.pop(0)
q.extend(process(x))

--
Paul Hankin

Mar 9 '08 #9

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by Tobias Pfeiffer | last post: by
57 posts views Thread by Xarky | last post: by
5 posts views Thread by Dinsdale | last post: by
2 posts views Thread by LTDEV | last post: by
reply views Thread by kmoeWW | last post: by
reply views Thread by gheharukoh7 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.