No.1
4
1
100pt
専門家でないので思いついたことを書いてみます。
（１）
平均の出現回数が少なければ、次のようなインデックスを作るのはどうでしょう。
例えば Aが2回、Bが3回、Cが1回の場合
インデックスを AABBBC と作って、その中から任意選択します。
これだと選択の速度は最速でしょう。追加更新削除も、当該インデックスのみを消したり末尾に増やしたりすればよく（例えばAを1回追加したければAABBBCAとなっても全く問題が無い）速いでしょうが、出現回数が多い場合、インデックスの記憶領域を多く取ります。
（２）
出現回数が多いなら、一番単純なのは
例えば Aが1234回、Bが3456回、Cが7890回の場合などは、0～(1234+3456+7890)の間の乱数xを求めて、Aから順に、x>それまでの要素の合計となる要素を求める方法だと思いますが、選択の計算量は多いですよね。但し追加更新削除は早く記憶域も少ないです（数字を変えるだけ）
（３）
厳密でなくて良いのであれば、（２）の例を例えば100で割って、A=12回、B=34回、C=78回として、（１）を適用してもいいかもしれません。
No.1
41
ここでベストアンサー
100pt
専門家でないので思いついたことを書いてみます。
（１）
平均の出現回数が少なければ、次のようなインデックスを作るのはどうでしょう。
例えば Aが2回、Bが3回、Cが1回の場合
インデックスを AABBBC と作って、その中から任意選択します。
これだと選択の速度は最速でしょう。追加更新削除も、当該インデックスのみを消したり末尾に増やしたりすればよく（例えばAを1回追加したければAABBBCAとなっても全く問題が無い）速いでしょうが、出現回数が多い場合、インデックスの記憶領域を多く取ります。
（２）
出現回数が多いなら、一番単純なのは
例えば Aが1234回、Bが3456回、Cが7890回の場合などは、0～(1234+3456+7890)の間の乱数xを求めて、Aから順に、x>それまでの要素の合計となる要素を求める方法だと思いますが、選択の計算量は多いですよね。但し追加更新削除は早く記憶域も少ないです（数字を変えるだけ）
（３）
厳密でなくて良いのであれば、（２）の例を例えば100で割って、A=12回、B=34回、C=78回として、（１）を適用してもいいかもしれません。
(1)は確かに速そうですね。出現回数が多いので、そのまま適用するのは難しいですけどね。
(2)は私の現在の実装に近いです。頻度が多いものから少ないものの順にソートするようにしたので選択回数が減っています。
(2)の方法に累積の出現回数によるインデックスを追加して2分検索すれば、だいぶ早くなるかなぁ。
追加更新削除は工夫しないと遅くなりますね。
No.2
472
100pt
私は学生です。思いつきですが、この問題興味深いので考えてみました。
一つは表を元に要素を取り出す方法です。
以下擬似コードです。
all_count = 全要素のカウント（重複含む）
size = 要素数
struct element{
K_ key;
unsigned count;
};
element elements[size];
table[size];
とすると
table[0] = elements[0].count;
for(i=1;i<size;i++){</p>
table[i] += elements[i].count + table[i-1];
}
このような感じでテーブルを用意しておき
取得する時に
value = rand() % size;
//rand()が0を返す場合･･･ インクリメントしておく
value++;
for(i=0;i<size;i++){</p>
if(value <= table[i]){
break;
}
}
return elements[i].key;
といった感じのアルゴリズムを思いつきました。
ですが、試していないので良く分かりません。
それからSTLの
random_shuffleのアルゴリズムを配列を使わないで上手く導き出すというのはどうでしょうか？
またこの方法は主旨からずれますが、一回取り出したら出現回数をデクリメントして０になったらその要素を取り出せないようにする方法というのも思いつきました。
出現回数をデクリメントする方法はとりだせる回数が有限になるのと確率がどんどん変化してしまいますよね。限定された条件だったら使えるかもしれません。
random_shuffleはRubyのメーリングリストでも話題に上がっていました。面白いですね。
http://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb/ruby/ruby-lis...
ukiya
2006/06/17 17:02:25
1
14
12
(1)は確かに速そうですね。出現回数が多いので、そのまま適用するのは難しいですけどね。
(2)は私の現在の実装に近いです。頻度が多いものから少ないものの順にソートするようにしたので選択回数が減っています。
(2)の方法に累積の出現回数によるインデックスを追加して2分検索すれば、だいぶ早くなるかなぁ。
追加更新削除は工夫しないと遅くなりますね。