database - メモリ内の m 個の順序セットと交差する効率的なアルゴリズム?

Question

m 個の 順序集合があり、それらの共通部分を見つけたいとします。

順序集合にはどのデータ構造を使用する必要があり、どのアルゴリズムが最も効率的でしょうか?

同じ質問: N-way マージのアルゴリズム

文学は膨大なようです。したがって、より良い質問は次のとおりです。どの優れた実装がありますか?

Answer 1

これは単なるスケッチです。改善にご協力ください。

このソリューションは、バイナリ検索を使用して検索を各セットの要素数 n/2^i に制限することに基づいており、効率的なデータ構造を使用して次の数の比較を記憶します。

最初に注意すべきことは、平衡二分木は二分探索の実行に適しているということです。これは、検索の間隔が (部分) 木の間隔とほぼ一致する場合に限られます。

二分探索を受け入れる他の2つの構造は、配列とスキップ リストです。配列は挿入と削除には非効率的であるため、スキップ リストが最良の選択と思われます。

二分探索で比較された配列ごとの各セットの要素を含み、比較の実行順に挿入される、サイズ 64 の m 配列が必要になります。

また、バイナリ検索で使用されたすべてのセットのすべての要素が挿入される二重リンク リストも必要です。 ここでスキップ リストを使用すると、必要な比較の数をさらに最小限に抑えることができます。

基本的な考え方はこれです。

1. 二分探索で各セットの最小要素を検索します。
2. 各二分探索ステップで、集合の配列と二重連結リストに新しい要素を追加します。
3. 共通の最小要素があるかどうか。
4. 二重連結リストの最小要素を削除します。新しい検索は、セットのバイナリ検索配列の前の要素から開始され、以前より半分の距離を使用します。配列内の以前のバイナリ検索要素を使用して、新しい検索を最小の既知の間隔に制限します。
5. 1に続く。