4

私は機能的な世界に不慣れであり、これに関する助けに感謝します。

この単純な関数から醜い命令型コードをSUPERCEDEしたいのですが、その方法がわかりません。

私が欲しいのは、確率値に関してIEnumerable（F＃のseq）からランダムにいくつかの要素を選択することです-タプルの2番目の項目（したがって、「確率」0.7の項目は0.1よりも頻繁に選択されます）。

/// seq<string * float>
let probabilitySeq = seq [ ("a", 0.7); ("b", 0.6); ("c", 0.5); ("d", 0.1) ]

/// seq<'a * float> -> 'a
let randomPick probSeq =
    let sum = Seq.fold (fun s dir -> s + snd dir) 0.0 probSeq 
    let random = (new Random()).NextDouble() * sum
    // vvvvvv UGLY vvvvvv
    let mutable count = random
    let mutable ret = fst (Seq.hd probSeq )
    let mutable found = false
    for item in probSeq  do
        count <- count - snd item
        if (not found && (count < 0.0)) then
            ret <- fst item  //return ret;  //in C# 
            found <- true
    // ^^^^^^ UGLY ^^^^^^
    ret

////////// at FSI: //////////

> randomPick probabilitySeq;;
    val it : string = "a"
> randomPick probabilitySeq;;
    val it : string = "c"
> randomPick probabilitySeq;;
    val it : string = "a"
> randomPick probabilitySeq;;
    val it : string = "b"

randomPick必須ではありますが、機能的に実装するのは非常に簡単だと思いますか？

これは機能的ですが、seq（募集）ではなくリストを取得してください。

//('a * float) list -> 'a
let randomPick probList =
    let sum = Seq.fold (fun s dir -> s + snd dir) 0.0 probList
    let random = (new Random()).NextDouble() * sum
    let rec pick_aux p list = 
        match p, list with
        | gt, h::t when gt >= snd h -> pick_aux (p - snd h) t
        | lt, h::t when lt < snd h -> fst h 
        | _, _ -> failwith "Some error"
    pick_aux random probList
4

7 に答える 7

4

Matajonによって提案された原理を使用したF＃ソリューション：

let randomPick probList =
    let ps = Seq.skip 1 (Seq.scan (+) 0.0 (Seq.map snd probList))
    let random = (new Random()).NextDouble() * (Seq.fold (fun acc e -> e) 0.0 ps)
    Seq.find (fun (p, e) -> p >= random)
             (Seq.zip ps (Seq.map fst probList))
    |> snd

しかし、確率値の合計はとにかく事前に計算する必要があるため、この場合はおそらくリストベースのアプローチも使用します...

于 2009-10-19T08:10:26.197 に答える
2

ノートブックにF＃がないため、Haskellバージョンのみを提供します。同様のはずです。原則は、シーケンスを次のようなシーケンスに変換することです。

[(0.7,"a"),(1.3,"b"),(1.8,"c"),(1.9,"d")]

タプルの最初の各要素は、確率ではなく範囲のようなものを表しています。次に、簡単です。0から最後の数値（1.9）までの1つの乱数を選択し、それがどの範囲に属するかを確認します。たとえば、0.5を選択した場合、0.5は0.7よりも小さいため、「a」になります。

Haskellコード-

probabilitySeq = [("a", 0.7), ("b", 0.6), ("c", 0.5), ("d", 0.1)]

modifySeq :: [(String, Double)] -> [(Double, String)]
modifySeq seq = modifyFunction 0 seq where 
    modifyFunction (_) [] = []
    modifyFunction (acc) ((a, b):xs) = (acc + b, a) : modifyFunction (acc + b) xs

pickOne :: [(Double, String)] -> IO String
pickOne seq = let max = (fst . last) seq in
    do 
        random <- randomRIO (0, max)
        return $ snd $ head $ dropWhile (\(a, b) -> a < random) seq

result :: [(String, Double)] -> IO String
result = pickOne . modifySeq

例 -

*Main> result probabilitySeq
"b"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"d"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"b"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"c"
*Main> result probabilitySeq
"a"
*Main> result probabilitySeq
"c"
于 2009-10-19T00:07:23.027 に答える
2

私が理解しているように、あなたのロジックは次のように機能します。

すべての重みを合計してから、0とすべての重みの合計の間のどこかでランダムなdoubleを選択します。あなたの確率に対応するアイテムを見つけてください。

つまり、リストを次のようにマップする必要があります。

Item    Val    Offset    Max (Val + Offset)
----    ---    ------    ------------------
a       0.7    0.0       0.7
b       0.6    0.7       1.3
c       0.5    1.3       1.8
d       0.1    1.8       1.9

(item, probability)のリストをに変換するの(item, max)は簡単です。

let probabilityMapped prob =
    [
        let offset = ref 0.0
        for (item, probability) in prob do
            yield (item, probability + !offset)
            offset := !offset + probability
    ]

これは可変可能性にフォールバックしますが、その純粋で決定論的で、読み取り可能なコードの精神に基づいています。可変状態を回避することを主張する場合は、これを使用できます（末尾再帰ではありません）。

let probabilityMapped prob =
    let rec loop offset = function
        | [] -> []
        | (item, prob)::xs -> (item, prob + offset)::loop (prob + offset) xs
    loop 0.0 prob

状態をリストに通していますが、fold操作ではなくマップを実行しているため、Seq.foldまたはSeq.scanメソッドを使用しないでください。Seq.scanを使用してコードを書き始めましたが、ハッキーで奇妙に見えました。

どの方法を選択しても、リストをマッピングすると、線形時間でランダムに重み付けされたアイテムを非常に簡単に選択できます。

let rnd = new System.Random()
let randomPick probSeq =
    let probMap =
        [
            let offset = ref 0.0
            for (item, probability) in probSeq do
                yield (item, probability + !offset)
                offset := !offset + probability
        ]

    let max = Seq.maxBy snd probMap |> snd
    let rndNumber = rnd.NextDouble() * max    
    Seq.pick (fun (item, prob) -> if rndNumber <= prob then Some(item) else None) probMap
于 2009-10-19T14:38:04.243 に答える
1

Seq.to_list入力シーケンスをリストに変換してから、リストベースのアプローチを使用します。引用されたリストは十分に短いので、不当なオーバーヘッドであってはなりません。

于 2009-10-18T23:27:38.090 に答える
1

最も簡単な解決策は、refを使用して、Seqモジュールからの適切な関数のイテレーターの呼び出し間の状態を格納することです。

let probabilitySeq = seq [ ("a", 0.7); ("b", 0.6); ("c", 0.5); ("d", 0.1) ]

let randomPick probSeq =
    let sum = Seq.fold (fun s (_,v) -> s + v) 0.0 probSeq 
    let random = ref (System.Random().NextDouble() * sum)
    let aux = function
        | _,v when !random >= v ->
            random := !random - v
            None
        | s,_ -> Some s
    match Seq.first aux probSeq with
        | Some r -> r
        | _ -> fst (Seq.hd probSeq)
于 2009-10-19T05:27:51.220 に答える
0

機能的なリストベースのバージョンを使用しますLazyListが、F＃PowerPackから使用するように調整します。を使用LazyList.of_seqすると、道徳的にリストと同等になりますが、すべてを一度に評価する必要はありません。LazyListパターンとのパターンマッチングも可能LazyList.(|Cons|Nil|)です。

于 2009-10-19T20:15:18.013 に答える
0

cfernの提案は、実際にはこれに対する最も単純な（？=最良の）解決策だと思います。

入力全体を評価する必要があるため、seqのオンデマンド利回りの利点はとにかく失われます。最も簡単なのは、シーケンスを入力として受け取り、それをリストと合計に同時に変換するようです。次に、アルゴリズムのリストベースの部分にリストを使用します（リストは逆の順序になりますが、計算には関係ありません）。

let randomPick moveList =
    let sum, L = moveList
        |> Seq.fold (fun (sum, L) dir -> sum + snd dir, dir::L) (0.0, [])
    let rec pick_aux p list = 
        match p, list with
        | gt, h::t when gt >= snd h -> pick_aux (p - snd h) t
        | lt, h::t when lt < snd h -> fst h 
        | _, _ -> failwith "Some error"
    pick_aux (rand.NextDouble() * sum) L

あなたの解決策、特にジュリエットとヨハンに感謝します（実際にそれを手に入れるために私はそれを数回読んだことがあります）。
:-)

于 2009-10-19T22:34:15.263 に答える