スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

乱数が絡むプログラムを検証する

単純で正しそうなものが正しいとは限らない - Radium Software
http://d.hatena.ne.jp/KZR/20081203/p2
を以前見て気になってた。
検証するには、上の記事のリンク先のように、実際に実行した結果に偏りがないことを確認すればよい。
しかし、数千回、数万回実行するのは時間がかかる。無駄だ。
もしrand()が可能な値全てを返すことができれば、何万回も実行しなくても検証できるのではないだろうか?
例えば、乱数を使ったこんなコードがあるとする。
int a = rand(5); // 0から4までの値を一つ返す
int b = rand(5); // 同様
printf("(a,b)=(%d,%d)\n", a, b);// (0,0),(0,1),…,(4,4)が等確率で表示される。
次のように書き換える。
for(int a = 0; a < 5; ++a) { // 0から4までの値を全部
for(int b = 0; b < 5; ++b) { // 同様
printf("(a,b)=(%d,%d)\n", a, b); // (0,0),(0,1),…,(4,4)が同じ数(1つずつ)表示される
}
}
つまり、rand()を使う代わりにfor文を使う。rand()の代わりに使うために、for文を関数のように扱いたい。Schemeのファーストクラスの継続を使えばそれを実現できる。
例えば、上の記事の、配列の中身をシャッフルするコードは以下のようになる。
(define current-jmpsaki #f) ; いい名前募集中
(define-syntax converge
(syntax-rules ()
((_ expr ...)
(let ((prev-jmpsaki current-jmpsaki))
(call/cc (lambda (cont)
(set! current-jmpsaki cont)
(begin expr ...)
(current-jmpsaki current-jmpsaki)))
(set! current-jmpsaki prev-jmpsaki)))))
(define (rand n)
(let ((i 0) (prev-jmpsaki current-jmpsaki))
(set! current-jmpsaki (call/cc (lambda (c) c)))
(if (< i n)
(let ((j i)) (set! i (+ i 1)) j)
(begin
(set! current-jmpsaki prev-jmpsaki)
(prev-jmpsaki prev-jmpsaki)))))

(define (assoc-update alist key update default)
(if (null? alist)
(list (list key default))
(if (equal? (caar alist) key)
(cons (list key (update (cadar alist))) (cdr alist))
(cons (car alist) (assoc-update (cdr alist) key update default)))))
(define (vector-swap v i j)
(let ((v2 (make-vector (vector-length v))))
(let loop ((k 0))
(if (< k (vector-length v))
(begin
(vector-set! v2 k (vector-ref v (if (= k i) j (if (= k j) i k))))
(loop (+ k 1)))
v2))))

(define initial-cards (vector 1 2 3))

; 「単純」なコード(A)
(let ((result '()))
(converge
(let loop ((i 0) (cards initial-cards))
(let* ((n (rand (vector-length cards)))
(cards2 (vector-swap cards i n)))
(if (< (+ i 1) (vector-length cards2))
(loop (+ i 1) cards2)
(set! result (assoc-update result cards2 (lambda (n) (+ n 1)) 1))))))
(display "A:") (newline)
(for-each (lambda (a) (display (car a)) (display " : ") (display (cadr a)) (newline)) result))

; 正しいコード(B)
(let ((result '()))
(converge
(let loop ((i (- (vector-length initial-cards) 1)) (cards initial-cards))
(let* ((n (rand (+ i 1)))
(cards2 (vector-swap cards i n)))
(if (< 0 (- i 1))
(loop (- i 1) cards2)
(set! result (assoc-update result cards2 (lambda (n) (+ n 1)) 1))))))
(display "B:") (newline)
(for-each (lambda (a) (display (car a)) (display " : ") (display (cadr a)) (newline)) result))

結果:
A:
#(3 1 2) : 4
#(2 3 1) : 5
#(2 1 3) : 5
#(3 2 1) : 4
#(1 3 2) : 5
#(1 2 3) : 4
B:
#(2 3 1) : 1
#(3 2 1) : 1
#(3 1 2) : 1
#(1 3 2) : 1
#(2 1 3) : 1
#(1 2 3) : 1
Aの結果には偏りがあることが分かる。

追記
amb? ambで同じことできる? ambでおk?
スポンサーサイト

テーマ : プログラミング | ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

minoki

Author:minoki
好きなプログラミング言語:
Haskell,Lua
GitHubアカウント
Twitter

最新記事
月別アーカイブ
カテゴリ
検索フォーム
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。