检查集合列表是否具有任何包含关系的最快方法

Question

我有一个包含 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)

很明显，我的代码在每次迭代中检查包含时都没有利用以前的信息。任何人都可以建议最快的方法吗？

Answer 1

似乎按长度排序更快，然后首先尝试将小集合作为子集（对于每个集合，首先尝试将大集合作为超集）。十个案例中以毫秒为单位的时间，像您一样生成的数据但没有播种：

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

代码(Try it online!):

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%。与其先将最小的集合与潜在的 all 较大的集合进行比较，然后再给 second-最小的机会，这确实给了其他小集合一个早期机会。

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

与我的旧解决方案 (Try it online!) 的比较：

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

另一个想法

一个捷径可能是首先收集所有 single-element 集的并集，然后检查它是否与任何其他集相交（或者不对它们进行排序，或者在排序后再次从大到小）。这可能就足够了。如果不是，则像以前一样继续，但没有 single-element 集。

检查集合列表是否具有任何包含关系的最快方法

Fastest way to check if a list of sets has any containment relationship

python

algorithm

performance

set

python-3.x

改进

另一个想法