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

回答の条件
  • 1人5回まで
  • 登録:2006/06/15 20:27:55
  • 終了:2006/06/16 20:42:54

ベストアンサー

id:ukiya No.1

ukiya回答回数4ベストアンサー獲得回数12006/06/16 10:29:02

ポイント100pt

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

(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)を適用してもいいかもしれません。

id:moonwolf

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

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

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

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

2006/06/16 12:41:33

その他の回答(1件)

id:ukiya No.1

ukiya回答回数4ベストアンサー獲得回数12006/06/16 10:29:02ここでベストアンサー

ポイント100pt

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

(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)を適用してもいいかもしれません。

id:moonwolf

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

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

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

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

2006/06/16 12:41:33
id:studiokingyo No.2

d金魚回答回数47ベストアンサー獲得回数22006/06/16 20:18:12

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

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

id:moonwolf

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

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

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

2006/06/16 20:41:46
  • id:ukiya
    100ポイントも頂いてしまいました。
    なんだか申し訳ないです。

    もう少し考えてみました。
    この問題は、「確率付きの2分木」が作れれば解決しそうな気がします。そして、「確率付きの2分木」と言えば、ハフマン木の生成方法そのものです。

    「ハフマン木」でぐぐると沢山参考文献が出てきますので、簡単に説明だけ。

    例えば A33% B21% C18% D15% E13%の頻度だとします。
    この時、以下のアルゴリズムで、確率付きの2分木を作ります。
    (1)ノードのうち一番小さいもの2つを子ノードとする親ノードを作る
    (2)(1)を再帰的に親ノードが1つになるまで繰り返す

    例の場合、まず D(15)とE(13)を子とするP1(28)ができ、
    B(21)とC(18)を子とするP2(39)ができ、
    A(33)とP1(28)を子とするP3(61)ができ、
    P2(39)とP3(61)を子とするP4(100)ができ、これでおしまい。

    ツリーは以下のようになります。
    (z(x,y)を、zを親、x,yを子とした木とします)

    100P4(39P2,61P3)
    39P2(18C,21B)
    61P3(28P1,33A)
    28P1(15D,13E)

    後は、子同士の確率どおりに2分木を辿ればいいです。
    例えばP2から子を辿るには、1~39の乱数を作って、18以下
    かどうか見てあげればいいです。
    計算してみると分かりますが、最終的な確率は元の
    頻度どおりになります。

    この方法のいいところは、多少項目の頻度が変わっても、
    親へ親へと数字の張替えをすればさほど効率が落ちないこと。

    ご参考になればいいのですが。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません