読者です 読者をやめる 読者になる 読者になる

Google Summer of Code 2016: Ruby処理系の文字列実装の改良

Google Summer of Code2016のRubyコミュニティーへの提案"Automatic-selection mechanism for data structures in MRI"についての成果報告ページを作成しました。

主な内容としては、文字列の内部実装のためのデータ構造の改良を行いました。 Ropeという木構造の文字列表現を実装し、処理系の内部でユーザーからは透過的に効率的なデータ処理を行うようにしました。(他にもRubyに提案された新機能を実装したパッチを書いて投稿したり、ハッシュテーブルの新実装の評価のためのベンチマークを実装したりもしました。)

詳細はhttp://www.spinute.org/ruby/gsoc2016/japaneseを参照してください。

n要素の集合からのk要素のランダム抽出

まとまった情報が見つからなかったのでメモ

問題: [1,n]の中の整数からk個の異なる要素をランダムに選出したい ただし、get_rand_from_range(from, to)で[from, to]の範囲から整数を一つランダムに選出する操作はΘ(1)で行えるものと仮定する。

素朴な手法としては

手法1 * get_rand_from_range(1, n)を繰り返し用いる * ただし、この際に既に引いた数を再度引いた場合にはリトライする * このために選出済みの要素をハッシュテーブルに登録する * これはCoupon collector's problem - Wikipedia, the free encyclopediaであり、nに対してkが小さくないとき、後半の選出が失敗しまくるため、失敗回数の和の期待値がわりと大きくなるのが問題である * (成功確率p=(n-i)/nの幾何分布 - Wikipediaに従う確率変数の和(i=0..n-1)となり、調和級数 - Wikipediaの性質を使って期待計算時間、分散の解析が可能である

手法2 * Fisher–Yates shuffle - Wikipedia, the free encyclopediaを使ってn要素をシャッフルし、この先頭k要素を採用する * Fisher Yatesシャッフルでは全ての並び替えが当確率で発生するため、この方法で得られる先頭k要素はn要素からk要素の選出の集合の中から一様確率で得られる * ただしシャッフルを全て実行するとこの計算量はΘ(n)であり、kがnに対して小さい時に手法1と比べて劣る

余談: 手法2の変種として、Reservoir sampling - Wikipedia, the free encyclopediaというのもあるらしく、これはnがメモリに乗らないくらい大きい時にk要素をランダム選出するためのFisher Yatesのオンライン版アルゴリズムである。結局はクヌース先生の例の本http://www-cs-faculty.stanford.edu/~uno/taocp.htmlをちゃんと読め、ということらしい。

一つ触れておくこととして、この問題設定の特徴としては、入力が配列で与えられている"わけではない"ことがある。

もし入力が配列として与えられているならば、以下の手法を採用できる。

手法3 * 入力の配列に対してFisher Yatesのアルゴリズムをk回目で中断すれば、出力配列をΘ(k)で得ることが出来る * 配列の生成に前処理Θ(n)の時間がかかるものの、k要素のランダム抽出はΘ(k)で行うことができる * この方法は実装が簡単なため、固定されたのnについてのランダム抽出を繰り返し行う場合には選択肢のうちの一つであろう


上の3つの手法をコネコネしてΘ(k)の手法を構成することができる。(間違え探し随時受け付けています。)

  • ハッシュテーブルに値が未登録の場合にはindexが入っているものと見なすことで初期化処理を避ける
  • R[0..k-1]は抽出されたk要素を格納するための配列
  • Hashはハッシュテーブル
  • Hash[i].exist?はキーiに対して値が登録されているかどうかを返す
for i in 0..k-1
  r = get_rand_range_from(i, n)
  R[i] = Hash[r].exist ? Hash[r] : r
  Hash[r] = i

k要素の選出が一様確率で行われることの証明は、Fisher Yatesのアルゴリズム置換群からの一様抽出になっていることとほぼ同じ。(はず)

swap操作を使い、まだ引かれていないものの集合が[i, n]に残る状態を保つことで、get_rand_range_fromでランダムアクセス可能なサンプルを行っている。

ある値がj回目より前に選ばれない確率はΠ^{j-1}_{l=0}{(n-l-1)/(n-l)} = (n-j-1)/nであり、その時j回目で選ばれる確率は1/(n-j-1)なので、ある値がj回目に選ばれる確率は1/nである。

Hash[key]に値が入っていない状態をkeyが入っていると見なすことで配列の初期化Θ(n)を避けている。 実行時間はハッシュの読み書きが定数時間で行えるならばΘ(k)である。

でもハッシュテーブル索くの結構遅そうなので、長さn配列全体の0初期化とどっちが早いのって話は要検討である。


ググっていると他に、Coupon collector問題の期待計算時間がn > 2kの時にはΘ(k)であることに注目して左の不等式が成り立たない時には補集合を作るアイデアも挙がっていたが、本当にそれでうまくいくのかは未検討(正しくはありそうだけど、全体集合を作らずに補集合上手く作れるんだろうか)

p.s. どこかのなんかにsemialgeblaic setを使うと空間計算量をΘ(k)で出来るぜ、とコメント欄にサラッと書いてあったのを見かけたのだが、これはなんの話なんだろう...