フィルタリングのための効率的なアルゴリズム

Question

私はサービスであるアプリケーションで作業しています。リクエストオブジェクトを受け取りました。このオブジェクトをフィルタのセットに渡してレスポンスを返す必要があります。オブジェクトを渡す必要がある約10のフィルターがあります。次のように現在のアプリケーションは、すべてのフィルタで順次検索をやっている

：

public List<Element) FilterA(Request request){ 
    for(Element element in items) 
    { 
    // compare element to request object elements 
    // there are different field checking per object 
    } 
} 

のでFilterBがあり、FilterCなど彼らはすべての異なるフィールドが比較されているforループの中に、同様の方法で行われます。

ハッシュセットでこれを行うことはできますか？またはバイナリ検索？

また、効率的なアルゴリズムがあります。本質的には、O（n）をもっと改善したいと思っています。あなたはNリストと Fフィルターを持っている場合は

Answer 1

はbasciallyのみ2つの方法があります：リストを反復処理し、個々の要素に各フィルタを適用します（それはそれらのすべてに合格した場合、それ以外の場合を削除し、それを維持）。あなたが今やっていることをして、各フィルタがリスト全体を反復するようにしてください。 O（1）要素の削除を想定して、どちらもO（n * f）の最悪ケースの複雑さを持っています（これを達成するためにLinkedListを使用することを推奨します。

入力のプロパティを利用することで、この複雑さを改善できます。おそらく、複数のフィルタを1つに組み合わせることができます（たとえば、範囲チェックの場合）。あるいは、リストから1つの要素を取り除くと、他の要素も削除されます。また、どのフィルタがおそらくより多くの要素を削除するかを推測できれば、最初にこれらの要素を実行するのに恩恵を受けるでしょう。

だから、本当にどのようなものをフィルタリングしているのか、どのようなフィルタが表示されているのかによって異なります。最も一般的なケースでは、（O（1）時間に要素を削除できるリストを既に使用している限り）多くの場合勝つことはできませんが、入力の知識があれば何かを得るかもしれません。