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(函数) * len(价值) 可能的函数调用结果必须被视为相互独立,因此没有比检查所有功能更快的方法。



你可以写得更简洁一点,但:

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


内建函数 any ()  也包含短路, 就像原代码一样 。

< 强力 > 编辑  :事实证明,所希望的等值本来是

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


讨论情况见评论。

Answer 2

不,没有更快的方法。 O( m*n) 是极限。如果您掌握更多关于函数的信息, 您也许可以战胜它, 但在一般情况下, 没有。

Answer 3

如果您对函数或值了解更多,您可以做一个常规搜索引擎的工作 -- 对数值列表应用某种索引,只需一次通过。

编辑:

在此使用 any() 的处理方法, 用于此使用选项。

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

Answer 4

您无法比 O(nm) 做得更好, 只需询问这些函数, 而不简化手头函数的假设。

s 因为证明不存在任何这种函数需要您证明,对于任何整数和任何函数,查询的结果为False 。

要证明这一点,您不能只完成所有查询,因为您的st State space 是 O(2nm) 和查询仅将国家空间减半,所以您需要 O(log_2(2nm)=O(nm) 查询来将您的国家空间缩小到“每整数每个函数返回错误”的解决方案。

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))

讨论筑巢的羊羔是不是脉搏是一个完全不同的故事, 但我在处理功能列表时往往会用功能来思考。

友情链接