50

我正在执行以下类型的多次迭代：

masterSet=masterSet.union(setA)

随着集合的增长，执行这些操作所花费的时间也在增长（正如人们所期望的那样，我猜）。

我希望花时间检查 setA 的每个元素是否已经在 masterSet 中？

我的问题是，如果我知道 masterSet 还没有包含 setA 中的任何元素，我可以更快地做到这一点吗？

[更新]

鉴于这个问题仍然在吸引观点，我想我会从下面的评论和答案中澄清一些事情：

在迭代时，虽然我知道 有很多迭代setA会因为它的构造方式而有所不同masterSet（无需处理任何检查），但有几次迭代我需要唯一性检查。

我想知道是否有一种方法可以“告诉”masterSet.union()程序这次不要打扰唯一性检查，因为我知道这与masterSet只是快速添加这些元素不同，相信程序员的断言它们肯定是不同的。可以通过调用一些不同的“ .unionWithDistinctSet()”程序什么的。

我认为响应表明这是不可能的（并且真正设置的操作无论如何应该足够快）但是使用masterSet.update(setA)而不是联合，因为它稍微快一点。

我已经接受了这些方面最明确的回应，解决了我当时遇到的问题并继续我的生活，但我仍然很想听听我的假设.unionWithDistinctSet()是否会存在？

4

4 回答 4

88

您可以使用set.update原地更新您的主集。这样可以节省一直分配新集合的时间，因此它应该比set.union...快一点

>>> s = set(range(3))
>>> s.update(range(4))
>>> s
set([0, 1, 2, 3])

当然，如果您在循环中执行此操作：

masterSet = set()
for setA in iterable:
    masterSet = masterSet.union(setA)

您可能会通过执行以下操作来提高性能：

masterSet = set().union(*iterable)

最终，集合的成员资格测试是 O(1)（在平均情况下），因此测试元素是否已经包含在集合中并不会真正影响性能。

于 2013-06-05T12:07:10.043 回答
8

正如 mgilson 指出的那样，您可以使用update从另一个集合就地更新一个集合。这实际上工作得稍微快一些：

def union():
    i = set(range(10000))
    j = set(range(5000, 15000))
    return i.union(j)

def update():
    i = set(range(10000))
    j = set(range(5000, 15000))
    i.update(j)
    return i

timeit.Timer(union).timeit(10000)   # 10.351907968521118
timeit.Timer(update).timeit(10000)  # 8.83384895324707
于 2013-06-05T12:13:38.733 回答
6

如果你知道你的元素是独一无二的，那么集合不一定是最好的结构。

一个简单的列表可以更快地扩展。

masterList = list(masterSet)
masterList.extend(setA)
于 2013-06-05T12:23:33.913 回答
1

__eq__(..)当然，当该方法非常昂贵时，放弃此检查可能会节省大量资金。在 CPython 实现中，__eq__(..)使用哈希到相同数字的集合中已经存在的每个元素调用。（参考：源代码set。）

然而，一百万年后永远不会有这种功能，因为它开辟了另一种破坏集合完整性的方法。与此相关的麻烦远远超过（通常可以忽略不计的）性能增益。如果这被确定为性能瓶颈，那么编写 C++ 扩展并使用它的 STL 并不难<set>，它应该会快一个或多个数量级。

于 2015-08-02T14:13:05.827 回答