したがって、約 500 万の配列があります。
1) [1, 2, 3, 4, 5, 6]
2) [1, 4, 5]
3) [1, 4, 6, 9, 10]
4) ...
かなり。そして、各配列の交点を見つける必要があります。
1st array intersection with 2nd: [1, 4, 5]; with 3rd: [1, 4, 6]...
2nd array intersection with 1st: [1, 4, 5]; with 3rd: [1, 4]...
3rd array intersection with 1st: [1, 4, 6]; with 2nd: [1, 4]...
したがって、明らかなアルゴリズムは、複雑さ O(n*n) またはその周辺の何かを与える 2 つのネストされたループであるように見えます。計算済みの交点を保存しても (メモリの制限により不可能な場合があります)、~O(n*n/2) のような結果が得られます。これは非常に大まかな複雑さの計算ですが、とにかく 5 mlns * 5 mlns / 2 回の反復が必要です。すべてをRAMに入れても、それは多すぎます。
ただし、トリックがあります。すべての交差を知る必要はありません。最も大きなもので約 20,000 個あれば十分です。そのため、いくつかの交点を含む配列は省略できます (それらを「共有要素」と呼ぶこともあります)。
1st array intersection with Nth, Mth, Kth... (20,000 of the largest intersections).
約 1000 万の可能な要素があるため、配列のすべての要素は [1;10 mln] の範囲になります。
整数だけでなく文字列も保存する必要があります。しかし、はい、インデックスを整数として使用し、後で置換を実行することもできます。1,000 万の文字列は多すぎません。そのため、例では文字列ではなく整数を使用しています。しかし、実際の生データは文字列です: ['abcdef', 'abc', 'def', 'fghf'...] (私が書いたように、1000 万の一意の文字列があります)。
より速くする方法はありますか？特に、データがメモリに収まらない場合 (整数だけでなく、文字列を要素として格納することもできます)? たぶん、いくつかのトリッキーな map\reduce のもの...または GPU 計算でさえ。アイデア、アルゴリズム、リンク、コードの断片など、あらゆるソリューションを歓迎します。君たちありがとう！
アップデート。役に立つかもしれない興味深い投稿を見つけました：