はてなブックマーク

An introduction to property based testing の途中までにだいたい沿った内容を書きます。雑な翻訳とも言います。 同僚プログラマとの戦い 2つの数を足し合わせる関数を実装してくれないか? ~~~~~~~~~~~ できたぜ! ~~~~~~~~~~~ よっしゃ。 テストもあるよな? ~~~~~~~~~~~ テストもほしいのかよ...待ってろ。 できたぜ! 「1と3を与えたら4が返る」 終わりでいいか? ~~~~~~~~~~~ ちょっと待て、1つしか検証してないじゃないか、 他の入力値だと失敗するかもしれない。 ~~~~~~~~~~~ わかった、別なのを書くわ。 できたぜ! 「2と2を与えたら4が返る」 いいだろ? ~~~~~~~~~~~ いいんだが、まだ特定のケースしかテストしてないだろう? お前が考えてない他の入力値で失敗するかもしれないじゃないか ~~~

なにこの記事 重み付きランダム復元抽出アルゴリズムである、Walker's Alias Methodについて 重み付きランダム復元抽出 要素ごとに抽選される確率が異なり、(重み付き) 選んだ要素を都度母集団に戻す抽出方法(復元抽出) のこと。 素直に実装すると 重みをつけてランダムに何か出したいや 重み付きランダム のようになります。 線形探索で実装すれば、計算量は抽選1回毎にO(n) バイナリサーチなら準備にO(n)、抽選1回毎にO(log n) Walker's Alias Method 準備にO(n)で、抽選1回毎になんとO(1)というアルゴリズム。 同じ大きい集団に対して何度も抽選しないといけない用途向け。 (GAとか粒子フィルタとか。) ググればわかりやすい説明が出てきます。 図の上のような重みリストでは、 乱数が3~4の時にどの要素を抽出するかを最高で2回判定する必要があります

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?