10'000'000 以上のエンティティを相互に比較するプログラムを作成する必要があります。エンティティは基本的に、データベース/csv ファイル内のフラットな行です。
比較アルゴリズムは非常に柔軟である必要があり、エンド ユーザーがルールを入力すると、各エンティティが他のすべてのエンティティと照合されるルール エンジンに基づいています。
このタスクをより小さなワークロードに分割する方法を考えていますが、まだ何も見つかりません。ルールはエンド ユーザーによって入力されるため、DataSet を事前にソートすることは不可能に思えます。
私が今やろうとしているのは、DataSet 全体をメモリに収め、各項目を処理することです。しかし、それは非常に効率的ではなく、約が必要です。20 GB のメモリ (圧縮)。
ワークロードを分割したり、サイズを縮小したりする方法を知っていますか?
ありがとう
ルールが最高レベルの抽象化 (未知の比較関数など) にある場合、目標を達成することはできません。10^14 の比較操作は何年にもわたって実行されます。
ルールが完全に一般的でない場合、さまざまなケースを最適化するための 3 つのソリューションが表示されます。
比較が推移的で、ハッシュを計算できる場合(誰かが既にこれを推奨しています)、実行してください。ルールだけでなく、ハッシュも複雑になる可能性があります =)。適切なハッシュ関数を見つけると、多くの場合に役立ちます。
エンティティが sortableの場合、それらを並べ替えます。この目的のために、その場でソートするのではなく、項目のインデックス (または ID) の配列を作成することをお勧めします。比較をSQLに変換できる場合（データがデータベースにあることを理解しているため）、DBMS側でこれをより効率的に実行し、ソートされたインデックスを読み取ることができます（たとえば、ID = 3のアイテムを意味する3,1,2が最も低く、ID=1 が中間、ID=2 が最も大きい)。次に、隣接する要素のみを比較する必要があります。
物事に価値がある場合、ヒューリスティックなソートまたはハッシュを使用しようとします。つまり、必ずしも等しい要素を一意に識別するとは限らないハッシュを作成しますが、データセットをグループに分割し、その間に等しい要素のペアがまったく存在しないことを意味します。次に、すべての等しいペアがグループ内にあり、グループを 1 つずつ読み取り、10 000 000 ではなく、たとえば 100 要素のグループで手動の複雑な関数計算を実行できます。もう 1 つのサブアプローチは、データセットの異なる末尾に等しい要素が存在しないことを保証するという同じ目的を持つヒューリスティック ソートです。その後、要素を 1 つずつ読み取り、たとえば前の 1000 個の要素と比較できます (既に読み取られ、メモリに保持されています)。たとえば、1100 要素をメモリに保持し、新しい 100 が来るたびに最も古い 100 を解放します。これにより、DB の読み取りが最適化されます。ルールに (Attribute1=Value1) AND (...) のようなルール、または (Attribute1 < Value2) AND (...) のようなルール、またはその他の単純なルールが含まれている場合、これの他の実装も可能です。次に、最初にこの基準でクラスタ化を行い、次に作成されたクラスタ内のアイテムを比較できます。
ところで、ルールで 10 000 000 個の要素がすべて等しいと見なされる場合はどうなるでしょうか。10^14 の結果ペアを取得しますか? このケースは、一般的なケースではこのタスクを解決できないことを証明しています。いくつかの制限と仮定を作成してみてください。
ルールの階層について考えてみます。たとえば、ルール A が「色」で、ルール B が「形状」であるとします。
最初にオブジェクトを色で分ければ、赤丸と青三角を比較する必要はありません。
これにより、実行する必要がある比較の数が減ります。
データを効果的にクラスター化する必要があるよりも、各エンティティーをすべてのエンティティーと比較したい場合、まったく無関係なものを比較する理由はほとんどありません (衣服と人間を比較するのは意味がありません)。ルールはデータをクラスター化しようとします。 .
データをクラスタ化する必要があるため、K-Meansなどのクラスタリング アルゴリズムを試してください。
Apache Mahoutも参照してください。
各エンティティからハッシュコードを作成します。おそらく、ハッシュ生成から id を除外してから、等しいかどうかをテストする必要があります。ハッシュがある場合は、すべてのハッシュコードをアルファベット順に並べることができます。すべてのエンティティが順番に並べられているということは、double をチェックするのが非常に簡単であることを意味します。
これに最適な並べ替えアルゴリズムを探していますか? Divide and Concur はいいと思います。アルゴリズムが良さそうであれば、計算を行う方法は他にもたくさんあります。MPICH などを使用した特別な並列処理により、最終的な目的地が得られる場合があります。
しかし、実行方法を決定する前に、まずアルゴリズムが適合するかどうかを考える必要があります。