人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

キーと出現回数の2要素の配列があります。乱数で出現頻度どおりに要素を取り出すアルゴリズムを教えてください。追加・更新・削除の計算量(オーダー)もあれば嬉しいです。

●質問者: MoonWolf
●カテゴリ:コンピュータ 学習・教育
✍キーワード:アルゴリズム 乱数 更新 計算 配列
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● ukiya
●100ポイント ベストアンサー

専門家でないので思いついたことを書いてみます。

(1)

平均の出現回数が少なければ、次のようなインデックスを作るのはどうでしょう。

例えば Aが2回、Bが3回、Cが1回の場合

インデックスを AABBBC と作って、その中から任意選択します。

これだと選択の速度は最速でしょう。追加更新削除も、当該インデックスのみを消したり末尾に増やしたりすればよく(例えばAを1回追加したければAABBBCAとなっても全く問題が無い)速いでしょうが、出現回数が多い場合、インデックスの記憶領域を多く取ります。

(2)

出現回数が多いなら、一番単純なのは

例えば Aが1234回、Bが3456回、Cが7890回の場合などは、0?(1234+3456+7890)の間の乱数xを求めて、Aから順に、x>それまでの要素の合計となる要素を求める方法だと思いますが、選択の計算量は多いですよね。但し追加更新削除は早く記憶域も少ないです(数字を変えるだけ)

(3)

厳密でなくて良いのであれば、(2)の例を例えば100で割って、A=12回、B=34回、C=78回として、(1)を適用してもいいかもしれません。

◎質問者からの返答

(1)は確かに速そうですね。出現回数が多いので、そのまま適用するのは難しいですけどね。

(2)は私の現在の実装に近いです。頻度が多いものから少ないものの順にソートするようにしたので選択回数が減っています。

(2)の方法に累積の出現回数によるインデックスを追加して2分検索すれば、だいぶ早くなるかなぁ。

追加更新削除は工夫しないと遅くなりますね。


2 ● d金魚
●100ポイント

私は学生です。思いつきですが、この問題興味深いので考えてみました。

一つは表を元に要素を取り出す方法です。

以下擬似コードです。

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のアルゴリズムを配列を使わないで上手く導き出すというのはどうでしょうか?

またこの方法は主旨からずれますが、一回取り出したら出現回数をデクリメントして0になったらその要素を取り出せないようにする方法というのも思いつきました。

◎質問者からの返答

出現回数をデクリメントする方法はとりだせる回数が有限になるのと確率がどんどん変化してしまいますよね。限定された条件だったら使えるかもしれません。

random_shuffleはRubyのメーリングリストでも話題に上がっていました。面白いですね。

http://blade.nagaokaut.ac.jp/cgi-bin/vframe.rb/ruby/ruby-lis...

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ