给定一个冻结的整数集列表，我如何找到出现在某个特定频率以上的第一个元素？
我正在实现的算法中有一个涉及超图二元化的条件。
给定两个超图 G(实现为元组 (G0，G1))，其中 G0 是顶点的集合，G1 是顶点的冻结集(超边)列表，H 也是如此(重要的是要注意 G0 = H0 总是)。
该算法的伪代码说在 G1 和 H1 中找到任何 x(由于某些理论而保证找到)(可能是你能找到的最快的一个)，使得 x 的频率为>= 1/log(|G1|+|H1|)。
我天真地做到了：
def logOrMore(v,edges,sum):
count = 0
for edge in edges:
if v in edge:
count+=1
if count >= (1/log(sum)):
return True
return False
在主算法中：
...code...
sum = len(G[1])+len(H[1])
x = 0
for v in G[0]:
if logOrMore(v,G[1],sum):
x = v
break
if x ==0:
for v in G[0]:
if logOrMore(v,H[1],sum):
x = v
break
...more code...
当超图很大时，这正成为一个大问题。如何以最快的方式执行此操作？
G1 的一个例子是
G1 = [frozenset({74, 76}), frozenset({73, 74, 29, 30}), frozenset({73, 74, 3, 4}), frozenset({74, 76, 29, 30}), frozenset({16, 73, 74}), frozenset({73, 74})]
但这是一个非常小的情况。它可以达到列表中有超过 1000 个冻结集的地步。
注意：大多数时候不会对冻结的整数集进行排序
这是在 Python 3.6.4 中，如果有帮助的话
因此，正如@martineau注释中所建议的那样，您只能在开始时执行一次阈值计算并存储为变量。
清理此问题的另一种可能方法是使用名为first的包。它旨在采用可迭代对象并找到与条件匹配的第一个值。在您的情况下，听起来您正在寻找一个值>= 您的阈值。
pip install first
文档中的示例，查找列表中的第一个偶数：
from first import first
first([1, 1, 3, 4, 5], key=lambda x: x % 2 == 0)
您可以使用它来迭代您的冻结集以查找您的状况。但是，尽管代码库的其余部分，您仍然可以一起zip()G 和 H 列表，并且只使用一个 for 循环来检查它们。