15

この質問には制約が追加されています。

偏りがない限り、不均一な選択を許可します。

「セットは通常、二分探索木として実装されており、バランスをとるためにある種の深さまたはサイズの情報が含まれていると予想されるため、木の重み付きランダムウォークを実行できると思います。ただし、それを行うためのリモートで移植可能な方法は知りません。

編集: 制約は、償却された時間に対するものではありません。

4

5 に答える 5

6

セットに等しいサイズの配列を導入します。配列要素にセット内のすべての要素のアドレスを保持させます。配列/セットのサイズによって境界付けられたランダムな整数を生成Rし、配列の要素でインデックス付けされたアドレスを選択し、Rそれを逆参照してセットの要素を取得します。

于 2011-11-28T21:10:09.540 に答える
3

だけでそれを行う方法がわからないstd::setので、おそらく別のデータ構造が必要です。ビクター・ソロキンが言ったように、セットをベクトルと組み合わせることができます。の代わりに、プラスset<T>を使用します。各キーの値はベクトルへのインデックスであり、ベクトルの各要素はマップ要素を指しています。ベクトル要素には特定の順序はありません。要素を追加するときは、ベクターの最後に配置します。要素を削除し、それがベクター内の最後の要素ではない場合、最後の要素を削除された要素の位置に移動します。map<T, size_t>vector< map<T, size_t>::iterator >

于 2011-11-29T00:00:04.217 に答える
1

セット内の要素の分布がわかっている場合は、（同じ分布の）キーをランダムに選択して、を使用できますstd::set::lower_bound。とはいえ、それは多くのことです。

int main() {
    std::set<float> container;
    for(float i=0; i<100; i += .01)  
        container.insert(i);
    //evenish distribution of 10000 floats between 0 and 100.
    float key = std::rand() *10000f / RAND_MAX; //not random, sue me
    std::set<float>::iterator iter = container.lower_bound(key); //log(n)
    std::cout << *iter;
    return 0;
}
于 2011-11-28T22:01:39.157 に答える
0

の場合std::unordered_set<int> s:

1) ランダムRに取り込むmin(s)..max(s)

2)Rの場合: R をs返す

3)

newIter = s.insert(R).first;
newIter++;
if (newIter == s.end()) {
    newIter = s.begin();
}
auto result = *newIter;
s.erase(R);
return result;

順序付きセット (std::set) の場合、確率は要素間の距離に依存します。unordered_set はハッシュによってランダム化されます。

これが役立つことを願っています。

PSstd::set<V>をstd::set<std::pair<int, V>>(ペアの最初の要素が 2 番目の要素のハッシュである) に変換すると、このメソッドは任意のハッシュ可能な V に適しています。

于 2014-02-11T13:24:00.987 に答える
0

このコンストラクターを使用して、マップのランダムな順序のコピーを作成できる場合があります

template <class InputIterator>
set(InputIterator f, InputIterator l,
    const key_compare& comp)

..そして、キーのハッシュを比較するコンパレータ (またはその他の決定論的拡散関数) を渡します。次に、この新しいマップに従って「最小の」キーを取得します。

マップを 1 回作成し、「ランダムな」要素に対する複数のリクエストにわたってコストを償却できます。

于 2011-11-28T21:05:40.143 に答える