4

O（mlog（n））の並べ替えまたはO（m + n）のハッシュと余分なスペースO（m）またはO（n）、またはO（m + n）のインデックス増分方法を使用して、この問題を解決する方法はいくつかあります。

しかし、メモリが限られていて、アレイのサイズが数百万の範囲にある場合は、もっと興味があります。

配列AまたはBをセグメントに分割してメモリにロードすることはできますが、もっと良い方法があるかどうか疑問に思いました。

4

3 に答える 3

2

要素の明確性の問題（少なくとも問題と同じくらい難しい）はO(nlogn)、余分なスペースを使用しません。

ただし、平均的なケースで実際に改善できるハッシュソリューションを使用します。

提案されたアプローチは、実際には、データベース システムに交差を実装する方法の 1 つです。

(ディスク上に) バケットを作成kし、リストを反復処理して、各要素eを に追加しbucket[hash(e)]ます。 完了したら、十分なスペースがあり、各バケットがメモリ1
にロードするのに十分小さいと仮定すると、リストごとにロードするだけで済み、バケットごとに (並べ替えと反復に基づいて) メモリの交差を行う必要があります。 結果は、一般的な要素である交差点の答えをもたらします。bucket[i]

データベース システムでそれ (交差) が行われるもう 1 つの方法は、外部ソート(通常はマージ ソートのバリエーション) を使用して反復するか、ディスク用に最適化されたインデックス ( B+ ツリーなど) を作成することです。

（1）そうでない場合は、通常はそうです。バケットが十分に小さくなるまで、（異なるハッシュ関数を使用して）各バケットに対してプロセスを繰り返します。

于 2012-12-20T06:06:35.607 に答える
1

外部マージソートを使用して、限られたRAMでソートできます。 http://en.wikipedia.org/wiki/External_sorting

于 2012-12-20T01:34:24.623 に答える
1

配列がソートされている場合は、配列を同時にウォークスルーし、共通の要素をコピーします。大きな配列の場合は、それらの一部をロードします。

于 2012-12-20T01:31:53.373 に答える