10'000'000 +エンティティを互いに比較するプログラムを作成する必要があります。エンティティは、データベース/ csvファイルの基本的にフラットな行です。1000万のエンティティを比較する
比較アルゴリズムはかなり柔軟でなければなりません。エンドユーザーがルールを入力し、各エンティティが他のすべてのエンティティと照合されるルールエンジンに基づいています。
私はこのタスクを小さなワークロードに分割する方法について考えていますが、まだ何も見つかりませんでした。エンドユーザが事前にソートすることによってルールが入力されるため、DataSetは不可能に見えます。
私が今しようとしているのは、DataSet全体をメモリに収めて各アイテムを処理することです。しかし、それは非常に効率的ではないし、約が必要です。 20 GBのメモリ（圧縮済み）。
作業負荷をどのように分割したり、サイズを小さくすることができますか？
ありがとうございました
ルールが最高レベルの抽象化（たとえば、未知の比較機能など）にある場合、目標を達成することはできません。 10^14の比較演算は、何年も実行されます。比較が推移的であり、あなたがハッシュを（誰かがすでにこのことをお勧めします）を計算することができた場合にそれを行う、
：ルールは完全に一般的でない場合
は、私は別の例を最適化するために、3つのソリューションを参照してください。ハッシュは、あなたのルールだけでなく、複雑になることもあります）。良いハッシュ関数を見つけると、多くの場合役に立ちます。
エンティティがソート可能な場合は、を並べ替えます。この目的のために、インプレースをソートせず、アイテムのインデックス（またはID）の配列を作成することをお勧めします。あなたの比較をSQLに変換することができれば（あなたのデータがデータベースにあると分かります）、DBMS側でこれをより効率的に実行し、ソートされたインデックスを読み取ることができます（例えば、ID = 3のアイテムを意味する3,1,2 ID = 1が中央にあり、ID = 2が最大である）。次に、隣接する要素だけを比較する必要があります。
の価値がある場合は、ヒューリスティックソートやハッシングを使用してみます。私は必ずしも等しい要素を必ずしも一意に識別する必要のないハッシュを作成することを意味しますが、間違いなく1組の等しい要素が存在するグループ内でデータセットを分割することができます。次に、すべての等号ペアが内部グループになり、グループを1つずつ読み込み、10 000 000ではなく100エレメントのグループで手作業による複雑な関数計算を実行できます。他のサブアプローチは、同じ目的がデータセットの異なるエンディングにないことを保証する目的で、ヒューリスティックソートです。その後、要素を1つずつ読み込んで、1000の以前の要素と比較することができます（既に読み取られ、メモリに保持されています）。私は、新しい100が来るたびに、例1100の要素を記憶し、最も古い100を解放します。これはあなたのDB読み取りを最適化します。あなたのルールに（Attribute1 = Value1）AND（...）、（Attribute1 < Value2）AND（...）または他の単純ルールのようなルールが含まれている場合にも、この他の実装が可能です。次に、この基準によってクラスタ化を最初に行い、次に作成されたクラスタ内のアイテムを比較することができます。
ちなみに、あなたのルールで10 000 000要素がすべて等しいとみなされたらどうなりますか？ 10^14の結果ペアを取得しますか？このケースでは、一般的な場合にこのタスクを解決できないことがわかります。いくつかの制限と前提を立ててみてください。
私は各エンティティからハッシュコードを作成します。おそらく、ハッシュ生成からIDを除外し、等価性をテストする必要があります。ハッシュがあれば、すべてのハッシュコードをアルファベット順に並べ替えることができます。すべてのエンティティを順番に持つことは、2倍をチェックするのはかなり簡単だということを意味します。
もちろん、ルールセットには複雑なルールを含めることができます。あなたは単に行を比較することはできません。 （たとえば、文字列の正規化、文字列の距離の計算など） – senic
これに最適なソートアルゴリズムを探していますか？ 分割とコンクールは良いと思います。 アルゴリズムがうまくいくと思われる場合は、計算を行うための他の多くの方法があります。特にMPICHなどを使用した並列処理は、最終的な宛先を与える可能性があります。
しかし、実行方法を決める前に、アルゴリズムが最初に適合するかどうかを考える必要があります。
私はルールの階層について考えようとします。 たとえば、ルールAが「色」、ルールBが「シェイプ」であるとします。
最初にオブジェクトを色で分割する場合は、 より、赤い円と青い三角形を比較する必要はありません。
これにより、実行する必要のある比較回数が減ります。
データをクラスター化する必要がある以上にすべてのエンティティと各エンティティを比較する場合は、無関係なものを完全に比較する理由はほとんどありません（ヒューマンとの比較は意味がありません）。データをクラスター化する。
したがって、データをクラスタ化する必要がある場合は、K-Meansのようなクラスタリングアルゴリズムを試してみてください。
また、各エンティティは、*すべての*他のエンティティと比較する必要があり、Apache Mahout
を参照してください？本気ですか？それは〜5x10^13の組み合わせです...もしあなたが毎秒100万回の比較を行うことができれば、1年半以上かかるでしょう。 –
このルールエンジンはすでに書き込まれていますか？これはC＃よりもデータベースに適した作業のようです。 –
かなり。エンティティの比較方法を知っていれば、大幅に作業量を減らすことができます。しかし、私はどのように正確に一致ルールを定義しようとしているのかわかりません。 – senic