迭代在python中不断增长的集合

Question

我有一个set,setOfManyElements,它包含n个元素.我需要遍历所有这些元素并在S的每个元素上运行一个函数:

for s in setOfManyElements:
   elementsFound=EvilFunction(s)
   setOfManyElements|=elementsFound

EvilFunction(s)返回它找到的元素集.其中一些已经在S中,一些将是新的,一些将在S中并且将已经过测试.

问题是每次我运行EvilFunction时,S都会扩展(直到最大设置,此时它将停止增长).所以我基本上在不断增长的集合上进行迭代.此外,EvilFunction需要很长时间才能计算,因此您不希望在相同数据上运行两次.

有没有一种有效的方法来解决Python 2.7中的这个问题？

LATE EDIT:更改变量名称以使其更易理解.谢谢你的建议

Answer 1

您可以保留一组已访问过的元素,并且每次都选择一个非访问过的元素

visited = set()
todo = S
while todo:
    s = todo.pop()
    visited.add(s)
    todo |= EvilFunction(s) - visited

Answer 2

我建议使用6502的增量版本的方法:

seen   = set(initial_items)
active = set(initial_items)

while active:
    next_active = set()
    for item in active:
        for result in evil_func(item):
            if result not in seen:
                seen.add(result)
                next_active.add(result)
    active = next_active

这仅访问每个项目一次,并在完成时seen包含所有访问过的项目.

进一步研究:这是一个广度优先的图搜索.