検索アルゴリズム階層と複数のフィルタ

Question

これは私の問題です。

私たちはいくつかのオブジェクトのリストAを持っており、各オブジェクトにはいくつかのフィールドがあります。フィールドの階層を のリストで検索する必要があります。私の質問は、これを行うための最善の最適化アルゴリズムは何ですか？

何を私が知っているをしていすることです：Aの検索で

ループトラフリスト、何もBの検索で

ループトラフリストを返さない場合は、何も検索に

ループトラフリストを返さない場合C.

の

等...

が言うCは検索から何かを返し、私はその後、他のフィルタを適用D場合、DとE、それを呼び出す必要があり

Eが一致する場合はCを返します。

一致しない場合（DまたはE）、Fを検索して同じDおよびEも一致する必要があります。

リストAはサイズを変更でき、各オブジェクトのフィルタはに変更できることを考慮してください。

私の問題は、2つのオブジェクトを一致させるためにこの検索を行い、リストBの各オブジェクトに対してこの検索をリストAで行います。 問題はBが何千ものエントリを持つ可能性があるという問題です。 アルゴリズムを完了するまでに数時間かかることがあります。

申し訳ありませんが抽象的なもののために、私はこれが適切な場所であるかどうかわかりませんが、どんな助けもありがたいです。

私はJAVAでプログラミングしています。

おかげ

Answer 1

問題あなたはそれが現時点では少し複雑で説明したように。 私はそれが間違っている場合は申し訳ありません。私は何を取ることです。

私の問題は、BIがリストA.問題で、この検索を行うリストで、私は2つのオブジェクトを一致させるために、この検索をやっているということで、各オブジェクトの 数千人を持つことができるB ですのエントリの。場合によっては アルゴリズムを完了するまでに数時間かかることがあります。

2つのリストがあり、オブジェクトのいくつかのフィールドに基づいてほぼ重複して検索したいと考えています。

最初に気になるのは、利用可能なjavaハッシュを使用してハッシュ関数を作成することです。各ハッシュは、比較するフィールドのみを含むハッシュを計算します。フィールドfield_aとfield_bを共有してfield_cを共有していないオブジェクトを探しているとしたら、私のハッシュ関数は(hash(field_a) * 8)^hash(field_b)などのように見えます。これを使用して、ハッシュマップまたはリストの配列を構築できます。

これで、リストを使い、オブジェクトをハッシュマップに追加します。次に、オブジェクトのハッシュを計算し、一致するかどうかを確認する2番目のリストを取得します。ハッシュが一致する場合は、オブジェクト自体を比較する必要があります。ハッシュ衝突による誤った一致の場合のみです（これらはまれですが、起こります）。だから今、このリストにあるものを探して

はほぼ一定O（1）、（あなたが得ることを期待するどのように多くの結果に依存し、どのように高価なハッシュ計算になる）です。

（すべての条件に対して）1回のパスですべてのハッシュを計算できるはずです（メモリキャッシュによりハッシュごとにpasを実行するよりも少し速くなります）。試合を探すことは非常に速くなければなりません。

注：多くのハッシュコリジョン（オブジェクトは同じハッシュを持っていますが、それらが望みどおりに一致しない）を見ると、ハッシュ関数が少し変更されます。

Answer 2

すべてのリストの繰り返しを一度に行います。リストbreakの操作と一致するものが見つかった場合は、 のループを別々に実行するように指示する必要はありません。これを書くための時間のための