18

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

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

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

興味深い: BY Intersect の実装

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

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

4

6 に答える 6

4

セットのような構造を考慮したい場合は、ブルーム フィルターに自明な結合操作と交差操作があります。

于 2010-11-23T23:43:34.853 に答える
3

かなり密度の高いセットの場合、間隔リストは、指定した操作で O(n) を上回る可能性があります。ここで、n はセット内の要素の数です。

間隔リストは、基本的に数値 [a1、b1、a2、b2、...、an、bn] の厳密に増加するリストです。各ペア ai、bi は間隔 [ai、bi) を示します。厳密に増加する制約により、すべての記述可能なセットが一意の表現を持つことが保証されます。セットを間隔の順序付けられたコレクションとして表すと、セット操作で反復ごとに複数の連続する要素を処理できます。

于 2010-11-24T04:58:22.320 に答える
2

セットが実際にハッシュセットであり、両方のセットが同じハッシュ関数とテーブルサイズを持っている場合、1つのセットにのみ存在するすべてのバケットをスキップできます。それは検索を少し狭める可能性があります。

于 2010-11-23T22:52:48.997 に答える
2

次の論文は、交差が差よりも大きい場合 (Z > n/2)、O(Z) に勝る順序集合の和集合、交差、および差のアルゴリズムを示しています。

コンフルーエントに永続的なセットとマップ

于 2013-01-26T16:18:02.350 に答える
1

O(Z) よりも最適な解決策はありません。問題を論理的に考えると、交差、結合、分離アルゴリズムのそれぞれが少なくとも入力要素のすべてを 1 回読み取る必要があるため、Z 読み取りは必須です。また、セットはデフォルトでソートされていないため、これ以上の最適化は O(Z) に勝るものはありません

于 2010-11-23T22:37:48.757 に答える
0

抽象的には、セットは「Xはメンバーですか？」という操作をサポートするものです。交差点A n Bでのその操作は、Aとで定義できますB。実装は次のようになります。

interface Set { bool isMember(Object X); };

class Intersection {
    Set a, b;
    public Intersection(Set A, Set B) { this.a = A; this.b = B; }

    public isMember(Object X) {
        return a.isMember(X) and b.isMember(Y);
    }
}

AまたB、HashSetなどの明示的なセットタイプを使用して実装できます。それぞれの操作のコストはかなり安いので、O（1）で概算しましょう。したがって、交差点のコストは2 O（n）です。;-)

確かに、このような交差点の大きな階層を構築する場合、メンバーのチェックは、階層内のnセットに対して最大O（ n）まで、よりコストがかかる可能性があります。これに対する潜在的な最適化は、しきい値に対して階層の深さをチェックし、それを超える場合はそれをHashSetに具体化することです。これにより、メンバーの運用コストが削減され、多くの交差点が適用される場合は、おそらく建設コストが償却されます。

于 2010-11-24T00:01:53.610 に答える