12

からランダムな要素を効率的に選択するにはどうすればよいstd::setですか?

Astd::set::iteratorはランダム アクセス反復子ではありません。std::dequeそのため、またはの場合のように、ランダムに選択された要素に直接インデックスを付けることはできませんstd::vector

から返されたイテレータを取得して、 [ , )の範囲でランダムな回数インクリメントすることもできますが、それは多くの不必要な作業を行っているようです。セットのサイズに近い「インデックス」の場合、要素がそこに見つからないことがすでにわかっていても、内部ツリー構造の前半全体をトラバースすることになります。std::set::begin()0std::set::size()

より良いアプローチはありますか？

効率の名目で、「ランダム」を、ベクトル内のランダム インデックスを選択するために使用した可能性のあるアプローチよりもランダムでないと定義したいと思います。それを「合理的にランダム」と呼んでください。

編集...

以下の多くの洞察に満ちた回答。

短いバージョンでは、 log(n)時間で特定の要素を見つけることができても、インターフェイスを介してその時間で任意の要素を見つけることはできません。std::set

4

6 に答える 6

8

boost::container::flat_set代わりに使用してください:

boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();

挿入と削除はO（N）になりますが、それが問題かどうかはわかりません。O(log N) のルックアップがまだあり、コンテナが連続しているという事実は、O(log N) の挿入と削除の損失を上回ることが多い全体的な改善をもたらします。

于 2012-09-05T19:50:59.127 に答える
4

ランダム ツリー トラバーサルを引き起こすfind(または)の述語はどうですか? lower_boundツリーの高さを推定し、時には葉ノードの前で終了できるように、セットのサイズを伝える必要があります。

編集:これに関する問題std::lower_boundは、述語を使用しますが、ツリーのような動作を持たないことに気付きました(内部的にはstd::advance、別の回答のコメントで説明されているものを使用しています)。 std::set<>::lower_boundセットの述語を使用します。これはランダムにすることはできず、セットのような動作をします。

あはは、別の述語を使用することはできませんが、変更可能な述語を使用することはできます。std::set述語オブジェクトを値で渡すため、述語として a を使用してpredicate &、到達して変更できるようにする必要があります (「ランダム化」モードに設定します)。

これは準実用的な例です。残念ながら、正しいランダムな述語に頭を悩ませることはできないため、ランダム性は優れていませんが、誰かがそれを理解できると確信しています:

#include <iostream>
#include <set>
#include <stdlib.h>
#include <time.h>

using namespace std;

template <typename T>
struct RandomPredicate {
    RandomPredicate() : size(0), randomize(false) { }
    bool operator () (const T& a, const T& b) {
        if (!randomize)
            return a < b;

        int r = rand();
        if (size == 0)
            return false;
        else if (r % size == 0) {
            size = 0;
            return false;
        } else {
            size /= 2;
            return r & 1;
        }
    }

    size_t size;
    bool randomize;
};

int main()
{
    srand(time(0));

    RandomPredicate<int> pred;
    set<int, RandomPredicate<int> & > s(pred);
    for (int i = 0; i < 100; ++i)
        s.insert(i);

    pred.randomize = true;
    for (int i = 0; i < 100; ++i) {
        pred.size = s.size();
        set<int, RandomPredicate<int> >::iterator it = s.lower_bound(0);
        cout << *it << endl;
    }
}

私の中途半端なランダム性テストは./demo | sort -u | wc -l、一意の整数がいくつ得られるかを確認することです。より大きなサンプル セットを使用./demo | sort | uniq -c | sort -nして、不要なパターンを探してみてください。

于 2012-09-05T19:41:21.177 に答える
2

基になる赤黒木にアクセスできる場合(存在すると仮定)、O(log n) のランダム ノードにアクセスして、L/R をceil(log2(n))-bit ランダム整数の連続ビットとして選択できます。ただし、基になるデータ構造が標準によって公開されていないため、できません。

イテレータをベクトルに配置する Xeo のソリューションは、O(n) の時間とスペースを設定することですが、全体的に償却定数です。std::nextこれは、O(n) 時間である に比べて有利です。

于 2012-09-05T19:50:11.990 に答える
1

これを行うには、通常の値の配列を維持します。セットに挿入するときは、配列の最後に要素を追加し（O（1））、乱数を生成する場合は、O（1）の配列からも取得できます。

この問題は、配列から要素を削除するときに発生します。最も単純な方法はO（n）を使用しますが、これはニーズに対して十分に効率的である可能性があります。ただし、これは次の方法を使用してO（log n）に改善できます。

i配列内のインデックスごとに、配列prfx[i]内の範囲内の削除されていない要素の数を表す、を保持0...iします。prfx[i]各範囲に含まれる最大値を保持するセグメントツリーを保持します。

セグメントツリーの更新は、削除ごとにO（log n）で実行できます。ここで、乱数にアクセスする場合は、セグメントツリーにクエリを実行して、数値の「実際の」インデックスを見つけます（最大値prfxが乱数に等しい最も早い範囲を見つけることによって）。これにより、乱数の生成が複雑になりますO（log n）。

于 2012-09-05T20:10:42.853 に答える
1

std::advance次の方法を使用できます。

set <int> myset;
//insert some elements into myset
int rnd = rand() % myset.size();
set <int> :: const_iterator it(myset.begin());
advance(it, rnd);
//now 'it' points to your random element

これを行う別の方法は、おそらくあまりランダムではありません:

int mini = *myset().begin(), maxi = *myset().rbegin();
int rnd = rand() % (maxi - mini + 1) + mini;
int rndresult = *myset.lower_bound(rnd);
于 2012-09-05T19:44:56.107 に答える
1

セットが頻繁に更新されない場合、またはこのアルゴリズムを頻繁に実行する必要がない場合は、データのミラーリングされたコピーを保持しvector(または必要に応じてセットをベクターにコピーするだけ)、そこからランダムに選択します。

コメントに見られるように、別のアプローチは、イテレータのベクトルをセットに保持し ( sets の要素削除でのみ無効になります)、イテレータをランダムに選択することです。

最後に、ツリーベースのセットが必要ない場合は、vectorまたはdequeを基になるコンテナーとして使用し、必要に応じて並べ替え/一意化することができます。

于 2012-09-05T19:52:06.273 に答える