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。

それを証明するには、すべてのクエリを実行するよりも少ないことはできません。これは、状態空間があり、クエリが状態空間を半分にするだけなので、状態空間を「すべての関数がすべての整数に対して false を返す」というソリューションに減らすクエリO(2^nm)が必要です。O(log_2(2^nm)) = O(nm)

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

ネストされたラムダがpythonicであるかどうかを議論することはまったく別の話ですが、関数のリストを扱うときは関数の観点から考える傾向があります。

于 2012-05-24T13:15:28.027 に答える