■
今日の結論: あんまり役に立たない。
某所で「特定範囲内の乱数を重複せずにn個取得する」のに、「重複したらもう一回乱数を取得する」以外にスマートな方法は無いのか、という話が出てたので、なんとなくGaucheでやってみた。
(尚、「結果の乱数リストの順番もランダム」という条件を勝手に追加した)
;; 乱数取得手続きを用意 (use srfi-1) (use math.mt-random) (define m (make <mersenne-twister> :seed (sys-time))) (define (get-random max-num) (mt-random-integer m max-num)) ;; 重複しない、最大値がmax-numの乱数をlist-num個取得する (define (get-uniq-random-int-list list-num max-num) ;; まず、基本となる乱数listを生成する (let1 rand-list (map (lambda (adjust) (get-random (- max-num adjust))) (iota list-num)) ;; 一つずつ補正していく (let next ((result '()) (rest rand-list)) (if (null? rest) result (next (cons (increment-check (car rest) (sort result)) result) (cdr rest)))))) ;; TODO: ここはfoldを使った方が素直に書ける気がする (define (increment-check num checklist) ;; (※ソート済の)checklistを先頭からチェックしていき、 ;; numがchecklistと同じかそれ以上なら1ずつ増やす ;; (事で、結果としてunique性を確保する) (if (null? checklist) num (let1 true-num (if (<= (car checklist) num) (+ 1 num) num) ;; 順番に、checklist全部に対して繰り返す ;; (この為に、checklistは事前にソート済である必要がある) (increment-check true-num (cdr checklist))))) ;; 実行してみる (get-uniq-random-int-list 8 10) ;; => (5 1 7 6 8 2 9 3)
(今回は副作用無し風味で書いたが、これに限っては、副作用バリバリで書いた方が効率は良くなると思う。)
要は、高校の確率統計とかでよくある、「数値の書かれた玉」の入った袋から一個ずつ取り出すような感じのアルゴリズム(ここでは仮に玉アルゴリズムと呼ぶ事にする)。
rand-listの要素の各数値は、「玉に書かれた数値そのもの」ではなく、「袋に残ってる玉に便宜上割り振ったインデクス値」という扱い。
この数値を「玉に書かれた数値そのもの」に戻すのがincrement-check手続き(名前はそれっぽくないが)。
問題は、これが「重複したらもう一回乱数取得しなおす」アルゴリズムよりも効率が良いのかどうかという点。
書いた当初は「いちいち一個ずつsortかけてるし、1ずつ足してるし、これ無茶苦茶遅いんじゃないか？役に立たないな」と思った。
しかし、よく考えると、
- 「特定範囲内の乱数を重複せずにn個取得する」のnが3とか5なら、sortや1ずつ足すのにかかるコストはたかが知れているので、「もう一回取得」アルゴリズムよりは遅いが、致命的に遅いという程ではない。
- 「特定範囲内の乱数を重複せずにn個取得する」のnが1000とかになると、sortや1ずつ足すコストは莫迦にならないが、「もう一回取得」アルゴリズムの場合、「今乱数取得した数値が、既に拾った乱数の中にあるかどうか」のチェックは線形検索せざるをえないので、どっちもどっち。
- ……と言いたいが、実際のところは謎。ベンチ取るのは面倒なのでパス。
- 尚、一応、線形検索を避けるようにも出来る筈。
- 例えば、「特定範囲内の乱数を重複せずにn個取得する」のnが1000で、更に「特定範囲」が0〜1200とかの場合、「もう一回取得」アルゴリズムでは重複率が高くなり、rand()実行回数が異様に多くなってしまう為、玉アルゴリズムの方が効率が良くなる。
と、状況によってどっちが良いかは変わってくるようなので、とりあえず、メモとして残しておく事にする。
尚、「結果の乱数リストの順番はソート済でよい」という条件なら、もう少しスマートな方法がありそうな気はする。
が、面倒なので今日はこれだけ。
