4

整数 0..N-1 の分布関数を表す有限長 N の float (0 と 1 の間) の与えられたシーケンスがあります。この分布から乱数を抽出しようとしています。これを行う 1 つの方法は、[0, 1] (float) で一様確率変数を描画し、その数値の逆累積分布関数を計算することです。

分布が配列の場合、コードは次のようになります。

let matched distribution draw =
  let rec matchRest distribution draw start = 
    if start = Array.length distribution then start-1
    else
      let left = draw - distribution.[start]
      if left <= 0 then start
      else matchRest distribution left (start+1)
  matchRest distribution draw 0

ここdistributionで、 は分布関数でdrawあり、一様 [0,1] 数です。

配布が任意のシーケンスの場合に機能するようにこの関数を書き直すにはどうすればよいですか? 明らかに、一時的な配列を作成できますが、それはエレガントなソリューションではないようです...

4

1 に答える 1

6

あなたのmatched機能は検索手順です。適切なインデックスを検索するためにシーケンスを分解する必要はありません。Seq モジュールの高次関数は次のことに役立ちます。

/// Taken from http://missingfaktor.blogspot.in/2012/02/f-option-cheat-sheet.html
let getOrElse d = function
    | Some a -> a
    | None -> d

let matched distribution draw =
    distribution 
    |> Seq.scan (fun (s, d0) d -> (s+1, d0-d)) (0, draw)
    |> Seq.tryPick (fun (s, d) -> if d <= 0 then Some s else None)
    |> getOrElse (Seq.length distribution-1)

最悪の場合でも、 を介してシーケンス全体を列挙しますSeq.length。Seq.length distribution-1できれば既知の定数に変更した方がいいと思います。

于 2012-07-12T13:03:37.820 に答える