検索アルゴリズムではあるが関数の場合

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

関数に関する詳細情報がない場合、可能な関数呼び出しの結果は互いに独立しているとみなされる必要があります。そのため、すべてをチェックするよりも速い方法はありません。

あなたは、もう少し簡潔にかかわらず、これを書くことができますちょうどあなたの元のコードのような

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

機能や値について詳しく知っていれば、通常の検索エンジンのように、単一のパスしか必要としない値リストに何らかのインデックスを適用することができます。

EDIT：

は、ここでは、このユースケースのために働くany()とアプローチです。

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

Answer 4

あなたはそれらだけを照会することにより、手の機能のいくつかの前提を単純化することなく、O(nm)より良いを行うことはできません。

このような関数がないという証明は、任意の整数と関数に対して、クエリの結果がFalseであることを証明する必要があるからです。

あなたstate spaceがO(2^nm)で、クエリはちょうどあなたが解決策にあなたの状態空間を減らすためにO(log_2(2^nm)) = O(nm)クエリーを必要とするので、「すべての関数がfalseを返し、状態空間を半分にするので、それを証明するために、あなたは、すべてのクエリを実行未満を行うことはできませんすべての整数に対して "。

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

は、ネストされたラムダはニシキヘビであるかどうかを議論することはまったく違う話ですが、私は機能的に考える傾向があります関数のリストを扱うときの用語。