我有一個包含 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)
顯然，我的代碼在每次迭代中檢查包容性時都沒有利用以前的資訊。誰能建議最快的方法來做到這一點？
uj5u.com熱心網友回復：
按長度排序似乎更快，然后首先嘗試將小集作為子集（對于每個集，首先嘗試將大集作為超集）。從十個案例中以毫秒為單位的時間，像您一樣生成資料但沒有播種：
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
還有一個想法
一個捷徑可能是首先收集所有單元素集合的并集，然后檢查它是否與任何其他集合相交（或者不對它們進行排序，或者在排序后再次從最大到最小）。這可能就足夠了。如果不是，則像以前一樣繼續，但沒有單元素集。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/481546.html
標籤：Python python-3.x 算法 表现 放