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

Question

我有一个集合，setOfManyElements，它包含 n 个元素。我需要遍历所有这些元素和运行 S 的每个元素的函数：

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

EvilFunction(s) returns 它找到的元素集。其中一些已经在 S 中，一些是新的，还有一些在 S 中并且已经过测试。

问题是每次我运行 EvilFunction 时，S 都会扩展（直到达到最大值，此时它将停止增长）。所以我基本上是在迭代一个不断增长的集合。 EvilFunction 也需要很长时间来计算，因此您不希望运行对同一数据进行两次计算。

在 Python 2.7 中是否有解决此问题的有效方法？

后期编辑：更改了变量的名称，使它们更易于理解。感谢建议

Answer 1

你可以只保留一组已经访问过的元素，每次都选择一个尚未访问过的元素

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

Answer 2

在您的场景中迭代 set 不是一个好主意，因为您无法保证顺序，并且迭代器不打算用于修改集中。所以你不知道迭代器会发生什么，也不知道新插入的元素的位置

但是，使用 list 和 set 可能是个好主意：

list_elements = list(set_elements)

for s in list_elements:
  elementsFound=EvilFunction(s)
  new_subset = elementsFound - list_elements
  list_elements.extend(new_subset)
  set_elements |= new_subset

编辑

根据所有内容的大小，您甚至可以完全删除 set

for s in list_elements:
  elementsFound=EvilFunction(s)
  list_elements.extend(i for i in elementsFound if i not in list_elements)

但是，我不确定它的性能。我认为你应该配置文件。如果列表很大，那么基于 set 的解决方案似乎不错——执行基于集合的操作的成本很低。但是，对于中等尺寸，也许 EvilFunction 已经够贵了，没关系。

Answer 3

我建议使用 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 包含所有访问过的项目。

进一步研究：这是广度优先图搜索。

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

iterating over a growing set in python

python

iteration

set

python-2.7