2

私はサービスであるアプリケーションに取り組んでいます。リクエストオブジェクトを受け取っています。このオブジェクトを一連のフィルタに通して、レスポンスを返す必要があります。オブジェクトを通過させるために必要なフィルターは約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）をもっと少ないものに改善したいと思います。

4

1 に答える 1

3

n個のリストとf個のフィルターがある場合、基本的に2つのアプローチしかありません。リストを反復処理し、各フィルターを個々の要素に適用します（すべてを通過する場合は保持し、そうでない場合は削除します）。または、現在行っていることを実行して、各フィルターにリスト全体を反復処理させます。O（1）要素の削除を想定すると、どちらもO（n * f）の最悪の場合の複雑さを持ちます（これを実現するにはLinkedListを使用することをお勧めします。必要に応じて、内容を1つにコピーします）。

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

そうですね、それは実際にフィルタリングしているものの種類とフィルタがどのように見えるかに依存します。最も一般的なケースでは（O（1）時間で要素を削除できるリストをすでに使用している限り）多くを獲得することはできませんが、入力の知識を考慮に入れると何かを得ることができます。

于 2012-05-27T20:34:09.037 に答える