List as FIFO in for loop

[malkarouri]

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

 

[Roel Schroeven]

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]

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]

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]

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. Löwis]

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]

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

 

[castironpi]

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]

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]

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]

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

 

[Paul Hankin]

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

 

[rockingred]

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

If the variables are "throwaways" and will be used in a really small
function, then it's probably okay to name them the way you did. I'm
just against single character names on principal, because if you need
to search a program to find where the variable was used you get too
many hits. I prefer to name the variables for what they do. For
example, instead of "q" you could use "queue".

 

[Arnaud Delobelle]

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

You could make it safe this way ('emulating' what a listiterator
object does in CPython):
... try:
... for i in count(): yield l
... except IndexError:
... return
...... if c == 'A': l += list(' EGGS')
... if c == 'S': l += list(' NI')
...
Of course in practice this is no different from doing 'for c in l:...'
but it is safe against implementation changes.