搜索算法,但功能

Question

给定一个输入列表(假设它们只是整数)和一个函数列表(这些函数采用整数,并返回True或False).

我必须获取此输入列表,并查看列表中的任何函数是否会为列表中的任何值返回True.

有没有办法比O(n ^ 2)更快地做到这一点

现在我拥有的是什么

for v in values:
    for f in functions:
        if f(v):
            # do something to v
            break

有更快的方法吗？

Answer 1

如果没有关于函数的任何进一步信息,len(functions) * len(values)可能的函数调用的结果必须被认为是彼此独立的,因此没有比检查它们更快的方法.

不过,你可以更简洁地写一下:

any(f(v) for v in values for f in functions)

内置函数any()也会像原始代码一样短路.

编辑:事实证明,所需的等价物将是

all(any(f(v) for f in functions) for v in values)

请参阅评论以进行讨论.