如何快速检查一组集合是否存在包含关系

Question

如何快速检查一组集合是否存在包含关系

4

我有一个长度不同的包含10,000个随机集合的列表：

import random

random.seed(99)
lst = [set(random.sample(range(1, 10000), random.randint(1, 1000))) for _ in range(10000)]

我想知道检查是否有一个集合是另一个集合的子集（或者说是否有一个集合是另一个集合的超集）的最快方法。目前，我正在使用以下非常基本的代码：

def any_containment(lst):
    checked_sets = []
    for st in lst:
        if any(st.issubset(s) for s in checked_sets):
            return True
        else:
            checked_sets.append(st)
    return False

%timeit any_containment(lst)
# 12.3 ms ± 230 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

显然，我的代码在每次迭代中检查包含时没有利用先前的信息。有人能建议最快的方法吗？

- Shaun Han

2

我认为您提供的代码与先前的语句不正确。它只检查一个集合是否是前一个集合的子集，而不是后面的集合。因此，在您的代码中，顺序很重要，但在先前的语句中却不重要。请使用[{1}, {1,2}]和[{1,2}, {1}]进行检查（这将得到不同的结果）。 - Jérôme Richard

@Jérôme Richard 哇，你说得对。我认为每一对集合都需要检查子集和超集。 - Shaun Han

我不明白你如何想使用“先前的信息”。就此用例而言，唯一适用于集合之间的关系是 a < b and b < c 暗示着 a < c（尽管反过来并不成立）。然而，由于在找到任意一者即可终止，似乎没有下一个迭代可以使用它。 - MisterMiyagi

@ShaunHan 是的，或者你可以测试所有组合而不仅仅是与前一个项目。在这两种情况下，这应该会慢两倍，但我认为前者更容易优化和理解。 - Jérôme Richard

例如，他们可以构建所有先前集合的联合，并首先将新的st与其进行比较。 - Kelly Bundy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kelly Bundy · Accepted Answer

根据长度排序，然后先尝试小集合作为子集（对于每个子集，尝试将大集合作为超集）。以下是从十个测试案例中得出的毫秒计时数据，数据的生成方式与您类似，但没有进行种子处理：

agree yours   mine  ratio  result
True   2.24   2.98   0.75  True
True 146.25   3.10  47.19  True
True 121.66   2.90  41.91  True
True   0.21   2.73   0.08  True
True  37.01   2.82  13.10  True
True   5.86   3.13   1.87  True
True  54.61   3.14  17.40  True
True   0.86   2.81   0.30  True
True 182.51   3.06  59.60  True
True 192.93   2.73  70.65  True

代码 (在线尝试):

import random
from timeit import default_timer as time

def original(lst):
    checked_sets = []
    for st in lst:
        if any(st.issubset(s) for s in checked_sets):
            return True
        else:
            checked_sets.append(st)
    return False

def any_containment(lst):
    remaining = sorted(lst, key=len, reverse=True)
    while remaining:
        s = remaining.pop()
        if any(s <= t for t in remaining):
            return True
    return False

for _ in range(10):
    lst = [set(random.sample(range(1, 10000), random.randint(1, 1000))) for _ in range(10000)]
    t0 = time()
    expect = original(lst)
    t1 = time()
    result = any_containment(lst)
    t2 = time()
    te = t1 - t0
    tr = t2 - t1
    print(result == expect, '%6.2f ' * 3 % (te*1e3, tr*1e3, te/tr), expect)

改进

以下内容似乎快了约20%。不是先将最小的集合与潜在的所有更大的集合进行比较，而是在给予第二个最小值一次机会之前，这确实为其他小集合提供了早期机会。

def any_containment(lst):
    sets = sorted(lst, key=len)
    for i in range(1, len(sets)):
        for s, t in zip(sets, sets[-i:]):
            if s <= t:
                return True
    return False

与我以前的解决方案进行比较 (在线尝试！)：

agree  old    new   ratio  result
True   3.13   2.46   1.27  True
True   3.36   3.31   1.02  True
True   3.10   2.49   1.24  True
True   2.72   2.43   1.12  True
True   2.86   2.35   1.21  True
True   2.65   2.47   1.07  True
True   5.24   4.29   1.22  True
True   3.01   2.35   1.28  True
True   2.72   2.28   1.19  True
True   2.80   2.45   1.14  True

另一个想法

一个快捷的方法是首先收集所有单元素集合的并集，并检查其是否与任何其他集合相交（无需对它们进行排序，或者在排序后再次从最大到最小进行）。这可能已经足够了。如果不行，则按照以前的方式继续，但不包括单元素集合。