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

Question

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

\n

import random\n\nrandom.seed(99)\nlst = [set(random.sample(range(1, 10000), random.randint(1, 1000))) for _ in range(10000)]\n

\n

我想知道检查是否存在任何集合是另一个集合的子集（或者等效地是否存在任何集合是另一个集合的超集）的最快方法。现在我正在使用以下非常基本的代码：

\n

def any_containment(lst):\n    checked_sets = []\n    for st in lst:\n        if any(st.issubset(s) for s in checked_sets):\n            return True\n        else:\n            checked_sets.append(st)\n    return False\n\n%timeit any_containment(lst)\n# 12.3 ms \xc2\xb1 230 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100 loops each)\n

\n

显然，我的代码在每次迭代中检查包含性时没有利用以前的信息。谁能建议最快的方法来做到这一点？

\n

Answer 1

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

\n

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

\n

代码（在线尝试！）：

\n

import random\nfrom timeit import default_timer as time\n\ndef original(lst):\n    checked_sets = []\n    for st in lst:\n        if any(st.issubset(s) for s in checked_sets):\n            return True\n        else:\n            checked_sets.append(st)\n    return False\n\ndef any_containment(lst):\n    remaining = sorted(lst, key=len, reverse=True)\n    while remaining:\n        s = remaining.pop()\n        if any(s <= t for t in remaining):\n            return True\n    return False\n\nfor _ in range(10):\n    lst = [set(random.sample(range(1, 10000), random.randint(1, 1000))) for _ in range(10000)]\n    t0 = time()\n    expect = original(lst)\n    t1 = time()\n    result = any_containment(lst)\n    t2 = time()\n    te = t1 - t0\n    tr = t2 - t1\n    print(result == expect, \'%6.2f \' * 3 % (te*1e3, tr*1e3, te/tr), expect)\n

\n

改进

\n

下面的代码似乎更快了约 20%。这确实给了其他小集合一个早期的机会，而不是首先将最小的集合与可能所有较大的集合进行比较，然后再给第二小的集合机会。

\n

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

\n

与我的旧解决方案比较（在线尝试！）：

\n

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

\n

还有一个想法

\n

一种捷径可能是首先收集所有单元素集的并集，然后检查它是否与任何其他集相交（要么不对它们进行排序，要么在排序后再次从最大到最小）。这可能就足够了。如果不是，则按之前的方式继续，但不使用单元素集。

\n