2

私は自分のアプリの 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

4

3 に答える 3

3

STL は特定のアルゴリズムを必要としません。特定の操作のアルゴリズムの複雑さに制約を設定するだけです。すべてテンプレート ベースであるため、特定の実装のソースを簡単に表示して、それがどのように機能するかを確認できます。

于 2010-10-27T04:56:31.423 に答える
2

少なくとも私が見た実装では、実装はかなり単純化されています。一般的な順序は次のとおりです。

template <class inIt, class outIt>
outIt set_intersection(inIt start1, inIt end1, inIt start2, inIt end2, outIt out) {
    while (start1 != end1 && start2 != end2) {
       if (*start1 < *start2)
           ++start1;
       else if (*start2 < *start1)
           ++start2;
       else {                 // equal elements.
           *out++ = *start1;
           ++start1;
           ++start2;
       }
    }
    return out;
}

もちろん、私はこれを頭のてっぺんに打ち込んでいるだけです -- おそらくコンパイルすらできないでしょうし、確かに厳密には正しくありません (たとえば、operator<直接使用する代わりにコンパレータ関数を使用するべきであり、別の関数を使用する必要があります)。 start1/end1 を start2/end2 とは異なるタイプにできるようにするためのテンプレート パラメーター)。

ただし、アルゴリズムの観点からは、ほとんどの実際の実装は上記のようになると思います。

于 2010-10-27T05:23:46.777 に答える
0

面白い。したがって、アルゴリズムの比較の数は、両方のセットの要素の数に比例して増減します。Baeza-Yates アルゴリズムは次のようになります (両方の入力セットがソートされていると仮定していることに注意してください)。

1) セット A の中央値を見つけます (ここでは A はより小さいセットです) 2) B で A の中央値を検索します。見つかった場合は、結果に追加します。そうでない場合は、B の中央値の挿入ランクがわかります。3) 中央値に関するセット A を 2 つの部分に分割し、挿入ランクに関するセット B を 2 つの部分に分割し、両方の部分で手順を再帰的に繰り返します。このステップが機能するのは、A の中央値よりも小さいすべての要素が、B の A の中央値の挿入ランクの前にある要素とのみ交差するためです。

二分探索を使用して B の A の中央値を見つけることができるため、明らかに、このアルゴリズムの比較の数は、あなたが言及したものよりも少なくなっています。実際、「最良」の場合、比較の数は O(log(m) * log(n)) です。ここで、m と n はセットのサイズであり、最悪の場合、比較の数は次のようになります。 O(m + n)。いったいどうやって実装をここまで台無しにしてしまったのでしょうか。:(

于 2010-10-28T18:22:29.350 に答える