6

给定一个输入列表（假设它们只是整数）和一个函数列表（这些函数接受一个整数，并返回 True 或 False）。

我必须获取这个输入列表，看看列表中的任何函数是否会为列表中的任何值返回 True。

有什么方法可以比 O(n^2) 更快地做到这一点

现在我所拥有的是

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

有更快的方法吗？

4

5 回答 5

10

如果没有关于函数的任何进一步信息，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)

请参阅评论进行讨论。

于 2012-05-24T13:03:05.397 回答
3

不，没有更快的方法。O(m*n) 是极限。如果你有更多关于函数的信息，你可能会打败它，但在一般情况下，没有。

于 2012-05-24T13:03:19.897 回答
2

如果您对函数或值有更多了解，您可以做常规搜索引擎所做的事情——对值列表应用某种索引，只需要一次通过。

编辑：

这是一种any()适用于此用例的方法。

for v in values:
    if any(f(v) for f in functions):
        #do something to v
于 2012-05-24T13:07:34.060 回答
2

O(nm)仅查询它们并且不对手头的功能进行一些简化假设，您不能做得更好。

这是因为不存在任何此类函数的证明要求您证明，对于任何整数和任何函数，查询的结果都是False.

为了证明这一点，您只能执行所有查询，因为您的状态空间是O(2^nm)并且查询只是将状态空间减半，因此您需要O(log_2(2^nm)) = O(nm)查询以将您的状态空间减少到解决方案“每个函数对每个整数都返回 false”。

于 2012-05-24T13:12:39.980 回答
1

这实际上不是 O(n)，但它使您不必每次都迭代函数：

#combine all funcs into one with `or`
newFunc = reduce(lambda f,g: (lambda x: f(x) or g(x)), funcs)

#cleaner than for, i think
satisfied = any(map(newFunc, values))

讨论嵌套 lambdas 是否是 pythonic 是一个完全不同的故事，但在处理函数列表时，我倾向于从函数的角度思考。

于 2012-05-24T13:15:28.027 回答