函数搜索算法

Question

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

我必须取出此输入列表，并查看是否有任何函数在列表中对列表中的任何值返回True。

有没有比O（n^2）更快的方法？

现在我所拥有的是：

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

有更快的方法吗？

- Pwnna

---

这些函数是纯函数吗？你还知道它们的其他信息吗？ - andrew cooke

“对于列表中的任何值返回True”这句话的意思是函数会为列表中的任何一个值返回True，而不是每个值都返回True。 - sukunrt

这种方式可能会更快，例如 any(f(v) for v in values for f in functions)，但时间复杂度不会低于 O(n_functions * n_values)。 - Fred Foo

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)

请查看评论以了解讨论。

- Sven Marnach

Answer 2

不，没有更快的方法。O(m*n)是极限。如果你有更多关于函数的信息，也许可以超越这个极限，但在一般情况下，不行。

- Kendall Frey

Answer 3

如果您更了解这些函数或值，您可以执行常规搜索引擎所做的操作- 对值列表应用某种索引，仅需要一次遍历。

编辑：

以下是使用any()的适用于此用例的方法。

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

- Matt Luongo

Answer 4

您只能通过查询并对手头的函数进行一些简化假设，才能达到O(nm)的最佳结果。这是因为证明不存在这样的函数需要证明，对于任何整数和任何函数，查询的结果都是False。要证明它，您不能少于执行所有查询，因为您的状态空间是O(2^nm)，而一个查询只能将状态空间减半，因此您需要O(log_2(2^nm)) = O(nm)个查询来将状态空间缩小到解决方案：“每个函数对于每个整数都返回false”。

- akappa

Answer 5

这实际上不是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))

讨论嵌套的lambda是否符合Pythonic风格是另一回事，但在处理函数列表时，我倾向于以函数式术语思考。

- phipsgabler

---

有趣的想法。请注意，在Python（2.7）中，any()是一个全局内置函数，而不是列表的类方法。 - Matt Luongo

@KarolyHorvath 不好意思，（该死的严格性...）如果我有更多时间，我会考虑一些延迟“or”的结构。但是你可能会再次面临更多的开销——也许几乎与列表一样。这是一个恶性循环。如果你能想到一个优雅的解决方案，我会非常感兴趣。 - phipsgabler