以下の形式のテキスト ファイルの場合、各行は最大 50 個の名前のリストです。少なくとも 50 の異なるリストに一緒に現れる名前のペアのリストを作成するプログラムを作成します。
Tyra,Miranda,Naomi,Adriana,Kate,Elle,Heidi Daniela,Miranda,Irina,Alessandra,Gisele,Adriana上記のサンプルでは、ミランダとアドリアナが 2 回一緒に表示されますが、他のペアはすべて 1 回だけ表示されます。"Miranda,Adriana\n" が返されるはずです。高い確率で50回以上出現するリストで近似解が返されることがあります。
私は次の解決策を考えていました：
Map <Pair,Integer>ファイルを読み込んだ後、pairToCountMapを生成します。
マップを反復処理し、カウントが 50 以上のものを出力します
これを行うより良い方法はありますか？ファイルは非常に大きくなる可能性があり、おおよその解が何を意味するのかわかりません。リンクやリソースは大歓迎です。
最初に、名前の長さが制限されていると仮定しましょう。したがって、名前に対する操作は一定の時間です。
記憶に収まる場合、あなたの答えは受け入れられるはずです。それぞれに名前が付いNた行がある場合、ソリューションが完了するまでに時間がかかるはずです。mO(N*m*m)
そのデータ セットがメモリに収まらない場合は、ペアをファイルに書き込み、マージ ソートを使用してそのファイルを並べ替えてから、スキャンしてペアを数えることができます。これの実行時間は ですがO(N*m*log(N*m))、ディスク アクセスの速度に関する詳細により、実際にははるかに高速に実行されます。
分散クラスターがある場合は、MapReduce を使用できます。最後のソリューションと非常によく似た方法で実行されます。
統計的アプローチに関しては、ファイルのリストを調べて、各名前の頻度と、名前の数が異なる行の数を見つけることを意味していると思います。各行が名前のランダムな組み合わせであると仮定すると、統計を使用して、一般的な名前のペアの間にいくつの交差があるかを推定できます。これは、ファイルの長さにほぼ比例します。
名前ごとに、それが表示される行番号のリストを取得し (ハッシュテーブルを使用して名前を格納します)、名前のすべてのペアについて、対応する行インデックスの交点のサイズを取得します (2 つの増加するシーケンスの場合)。これは線形時間です)。名前の長さが定数によって制限されているとします。したがって、N名前とM行がある場合、リストの作成は次のようO(MN)になり、最終段階はO(N^2 M).