問題タブ [set-intersection]

2 つのリスト (必ずしもソートされているとは限りません) が与えられた場合、これらのリストの集合の共通部分を見つけるための最も効率的な非再帰アルゴリズムは何ですか?
ハッシュアルゴリズムにアクセスできるとは思えません。

複数の属性を持つオブジェクトのリストが与えられた場合、交差するすべてのサブセットの結合によって作成されたセットのリストを見つける必要があります。

具体的には、これらは Person オブジェクトであり、それぞれに多くの属性があります。SSN、DLN などの一意の識別子に基づいて「マスター」セットのリストを作成する必要があります。

たとえば、人物 A と人物 B が同じ SSN を持っている場合、セット i を作成します。次に、人物 B と人物 C が同じ DLN を持っている場合、セットを作成します ii. 人物 D と E は同じ SSN を持っていますが、それ (および他のすべての識別子) は、人物 A、B、または C の識別子のいずれとも一致しません。すべての交差するサブセットをマージした後、人物 A、B、C の 1 つのセットになります。人物D、Eとの別のセット。

これが私のソリューションの疑似コードです。可能性のあるすべての交差セットをマージするより効率的な方法を誰かがすでに考え出していないかどうか、私は興味があります。セット間のリンクは X 人の長さになる可能性があることに注意してください (つまり、A は SSN で B に一致し、B は DLN で C に一致し、C は SSN で D に一致し、D は他の識別子で E に一致し、1 つのセットで人 AE になります)。また、これが実装される言語がセット操作をサポートしていると仮定します。

data1とがあると仮定しdata2ます。どうすればそれらを交差させることができstd::set_intersect()ますか？

セットのリストがあります：

s1 ∩ s2 ∩ s3 が欲しい ...

s1.intersection(s2)一連のペアワイズなどを実行することで、それを行う関数を書くことができます。

推奨される、より良い、または組み込みの方法はありますか?

以前は set_intersection を使用していませんでしたが、マップで機能すると思います。次のサンプル コードを書きましたが、期待どおりの結果が得られません。

(3) と (4) というラベルの付いたペアが両方のマップに表示されるため、交差点で 2 つの要素が得られると予想していましたが、そうではありません。

これは、マップ/ペアのコンパレーターと関係があると確信していますが、それを理解することはできません.

私の質問から

要素を昇順で重複要素なしでArrayListに挿入します

挿入方法を実行しました。

ここで、2 つの IntSet を操作するユニオン、インターセクション、および差分メソッドを作成する方法を見つけようとしています。

IntSet の要素数が多く、O(m+n)時間で実行する必要があることに注意してください。ここで、m と n は 2 つの IntSet の要素数です。

たとえば、IntSets

どうすればいいですか？

PSマージソートを使用できますか？

編集：

これが私のユニオンコードです

私は自分のアプリの 1 つで、Baeza-Yates の高速集合交差アルゴリズムのコーディングにかなりの時間を費やしました。私はSTL set_intersectをわずかに上回っていましたが、結果のセットをソートする必要があるという事実は、出力をソートした後に独自のアルゴリズムを実装することで得られたときはいつでも削除されました. STL set_intersect がこれをうまく実行することを考えると、実際に実装されているアルゴリズムを教えてもらえますか? それとも、同じ Baeza-Yates アルゴリズムを実装していますが、はるかに効率的な方法でのみ実装されていますか?

Baeza-Yates: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

現在、std::set_intersection を使用し、小さい方の入力のサイズが set_intersection によって埋められた要素の数と同じかどうかを確認するのが最善の方法だと思います。

より良い解決策はありますか？

このトピックのすべてを 1 か所で十分にカバーしているものを見つけることができなかったので、疑問に思っていました: 最速の集合交差、和集合、および分離アルゴリズムは何ですか?
ドメインが限定されている興味深いものはありますか?
交点の実際のサイズを Z とすると、O(Z) に勝てる人はいますか?

あなたのアプローチが並べ替えられたセットに依存している場合は、注意してください。ただし、それを不適格な要因とは見なさないでください。共有される微妙な最適化の真の貯蔵庫が存在するに違いないと私には思えます。

私が知っているいくつかのアルゴリズムは、バニラを超えたビット単位の操作に依存しているため、SSE4 の存在と popcount などの組み込み関数へのアクセスを想定している可能性があります。この仮定に注意してください。

興味深い: BY Intersect の実装

更新
いくつかの非常に優れた部分的な回答が得られましたが、問題に対するより完全な攻撃を期待しています。私は特に、この問題を解決するためにブルーム フィルターをより完全に明確に使用することに興味があります。

更新
ブルーム フィルターとカッコウ ハッシュ テーブルを組み合わせる準備作業を行いました。彼らは非常に似た要求を持っているので、それはほとんど不愉快なほど有望に見えます. 先に進んで回答を受け入れましたが、現時点ではあまり満足していません.

2 つのセットが与えられた場合に、それらの交差を線形時間で計算するアルゴリズムはありますか?

2 つのループを実行forして要素のすべてのペアをチェックし、両方のセットで見つかった要素を記録できます。ただし、実行時間は O(n ² ) になります。これを O(n) 時間で行うにはどうすればよいですか?