Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #74450 > unrolled thread

Iterating through set

Back to article view | Back to comp.lang.python

Contents

  Iterating through set LJ <luisjosenovoa@gmail.com> - 2014-07-14 17:10 -0700
    Re: Iterating through set Roy Smith <roy@panix.com> - 2014-07-14 20:30 -0400
    Re: Iterating through set Chris Kaynor <ckaynor@zindagigames.com> - 2014-07-14 18:08 -0700
    Re: Iterating through set Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2014-07-17 15:22 +0200

#74450 — Iterating through set

Hi All.

I'm coding a Dynamic Programming algorithm to solve a network flow problem. At some point in the algorithm I have to iterate through a set of nodes, while adding and/or removing elements, until the set is empty. I know a regular set() object does not work in a case like this, so I wonder if anyone knows of an efficient pythonic way to handle this.

Thanks in advance!

[toc] | [next] | [standalone]

#74451

In article <d70b2c77-d3d5-42f8-9c8e-d25ef78b3963@googlegroups.com>,
 LJ <luisjosenovoa@gmail.com> wrote:

> Hi All.
> 
> I'm coding a Dynamic Programming algorithm to solve a network flow problem. 
> At some point in the algorithm I have to iterate through a set of nodes, 
> while adding and/or removing elements, until the set is empty. I know a 
> regular set() object does not work in a case like this, so I wonder if anyone 
> knows of an efficient pythonic way to handle this.


You've already figured out that you can't alter a set while you're 
iterating over it.  Which means you basically have two choices:

1) Build a new set while you're iterating over the first one, then 
delete the first set.  This might make sense if you expect there will be 
a large number of items (relative to the size of the original set) added 
or deleted.

2) Keep lists, of those items which need adding or deleting, and do them 
in bulk, after the iteration is completed.  Then, delete the lists.  
This makes sense if you expect the number of add/deletes will be small.

Either way is O(n) in the size of the set, so which you pick is a 
second-order optimization.

[toc] | [prev] | [next] | [standalone]

#74454

[Multipart message — attachments visible in raw view] — view raw

On Mon, Jul 14, 2014 at 5:10 PM, LJ <luisjosenovoa@gmail.com> wrote:

> Hi All.
>
> I'm coding a Dynamic Programming algorithm to solve a network flow
> problem. At some point in the algorithm I have to iterate through a set of
> nodes, while adding and/or removing elements, until the set is empty. I
> know a regular set() object does not work in a case like this, so I wonder
> if anyone knows of an efficient pythonic way to handle this.
>

Your description of your need is somewhat vague, but this sounds like a
queue/stack which should be handled with a while loop and poping items.

Something like (untested):
mySet = [] # Typically, this would be a list. If you only want items
processed once per iteration, you'd likely use a separate set, however the
exact structure would vary based on the data and use-case.
# Some code to add initial items.
while mySet:
    item = mySet.pop()
    # Do something with item, which may call mySet.add(), and possibly
mySet.remove().


> Thanks in advance!
> --
> https://mail.python.org/mailman/listinfo/python-list
>

[toc] | [prev] | [next] | [standalone]

#74641

Am 15.07.2014 02:10 schrieb LJ:
> Hi All.
>
> I'm coding a Dynamic Programming algorithm to solve a network flow problem. At some point in the algorithm I have to iterate through a set of nodes, while adding and/or removing elements, until the set is empty. I know a regular set() object does not work in a case like this, so I wonder if anyone knows of an efficient pythonic way to handle this.
>
> Thanks in advance!
>

This sounds like you want to avoid processing of an item as soon as it 
is removed.

Then I'd suggest the following:

add = set()
remove = set()

while myset or add:
     for item in myset:
         if item not in remove:
             # process
     myset -= remove
     myset += add
     remove.clear()
     add.clear()

Adding happens via add.add(item), removing via remove.add(item).

If there is additionally the need to take care in which order to apply 
add/remove, or if it can happen that item X is added and removed in the 
same loop run, it gets a bit more complicated.

Then adding would be like

if item in remove:
     remove.remove(item)
elif item not in myset and item not in add:
     add.add(item)

and removing like

if item in add:
     add.remove(item)
elif item in myset:
     remove.add(item)


HTH,

Thomas

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web