在Python中迭代一个增长的集合

Question

我有一个集合，叫做setOfManyElements，其中包含n个元素。我需要遍历所有这些元素并对S的每个元素运行一个函数：

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

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

问题在于每次运行EvilFunction，S都会扩展（直到达到最大集合为止）。因此，我本质上是在迭代一个不断增长的集合。此外，EvilFunction需要很长时间来计算，因此您不希望在相同的数据上运行两次。

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

最后修改：更改变量名称以使其更易于理解。感谢建议。

- Pietro Speroni

---

你能否对 EvilFunction 进行一些控制？能否让它返回被添加到集合中的元素？那个集合有多大？你能否保留一个已访问元素的集合？ - tobias_k

你的问题不够清晰，如果你想得到一个满意的答案，需要准备更多关于你的问题的信息。你可以添加一个样例输入和期望输出，并添加你的函数代码。 - Mazdak

你们的变量名有点令人困惑，因为很难看出s和S之间的区别。顺便说一下，普通变量名应该是小写的，以大写字母开头的名称应该用于类（全局常量则全部使用大写字母）。 - PM 2Ring

你说“EvilFunction(s)返回它找到的元素集合。”但是你的代码没有保存从EvilFunction(s)返回的对象。EvilFunction(s)修改了小s还是大S的内容？一般来说，不应该修改正在迭代的容器。如果你小心，它可能会工作，但这会使代码更难阅读和调试。 - PM 2Ring

好的，我更改名称。 - Pietro Speroni

Answer 1

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

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

- Hugh Bothwell

---

这是一个图形（特别是格子），所以我不惊讶于解决问题的函数是图形解决函数。再次感谢。 - Pietro Speroni

Answer 2

您可以维护一个已访问元素列表，并每次选择一个未被访问的元素。

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

- 6502

---

谢谢。但是S-visited可能会非常昂贵，而且我需要运行几次。我不确定这是最有效和Pythonic的方法。我想到了迭代器，但我对它们不是很熟悉。 - Pietro Speroni

邪恶函数在开始时寻找新元素时速度较慢，然后会变得更快 :-) - Pietro Speroni

如果 EvilFunction 的结果包含了所有添加的元素（以及更多），那么你可以将它们加入到 todo 中，并且如果该元素在 visited 中，则 continue。 - tobias_k

是的，但这需要计算两个集合之间的差异，这也是一个相当昂贵的操作。 - Pietro Speroni

你为什么说集合差是“昂贵”的？它减慢了你的速度吗？你有分析结果吗？ - Reut Sharabani

不，我的电脑上甚至无法通过第一个邪恶函数。我正在准备将代码运行到大学的监控系统中 :-). - Pietro Speroni

Answer 3

在您的情况下迭代一个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足够昂贵了，那就无所谓了。

- MariusSiuram