根据长度排序,然后先尝试小集合作为子集(对于每个子集,尝试将大集合作为超集)。以下是从十个测试案例中得出的毫秒计时数据,数据的生成方式与您类似,但没有进行种子处理:
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
另一个想法
一个快捷的方法是首先收集所有单元素集合的并集,并检查其是否与任何其他集合相交(无需对它们进行排序,或者在排序后再次从最大到最小进行)。这可能已经足够了。如果不行,则按照以前的方式继续,但不包括单元素集合。
[{1}, {1,2}]
和[{1,2}, {1}]
进行检查(这将得到不同的结果)。 - Jérôme Richarda < b and b < c
暗示着a < c
(尽管反过来并不成立)。然而,由于在找到任意一者即可终止,似乎没有下一个迭代可以使用它。 - MisterMiyagist
与其进行比较。 - Kelly Bundy