如何使用 F# select 列表中的随机值

Question

我是 F# 的新手，我正在尝试弄清楚如何从 list/array 个字符串中 return 一个随机字符串值。

我有一个这样的列表：

["win8FF40", "win10Chrome45", "win7IE11"]

如何从上面的列表中随机 select 和 return 一项？

这是我的第一次尝试：

let combos = ["win8FF40";"win10Chrome45";"win7IE11"]  

let getrandomitem () =  
  let rnd = System.Random()  
  fun (combos : string[]) -> combos.[rnd.Next(combos.Length)]

Answer 1

您的问题是您混合使用了 Arrays 和 F# Lists（*type*[] 是 Array 的类型表示法）。您可以像这样修改它以使用列表：

let getrandomitem () =  
  let rnd = System.Random()  
  fun (combos : string list) -> List.nth combos (rnd.Next(combos.Length))

也就是说，索引到 List 通常不是一个好主意，因为它具有 O(n) 性能，因为 F# 列表基本上是一个链表。如果可能的话，你最好把 combos 变成一个数组：

let combos = [|"win8FF40";"win10Chrome45";"win7IE11"|]

Answer 2

我刚才写了一篇关于这个主题的博客 post：http://latkin.org/blog/2013/11/16/selecting-a-random-element-from-a-linked-list-3-approaches-in-f/

那里给出了 3 种方法，并讨论了每种方法的性能和权衡。

总结一下：

// pro: simple, fast in practice
// con: 2-pass (once to get length, once to select nth element)
let method1 lst (rng : Random)  =
    List.nth lst (rng.Next(List.length lst))

// pro: ~1 pass, list length is not bound by int32
// con: more complex, slower in practice
let method2 lst (rng : Random) =
    let rec step remaining picks top =
        match (remaining, picks) with
        | ([], []) -> failwith "Don't pass empty list"
        //  if only 1 element is picked, this is the result
        | ([], [p]) -> p
        // if multiple elements are picked, select randomly from them
        | ([], ps) -> step ps [] -1
        | (h :: t, ps) ->
            match rng.Next() with
            // if RNG makes new top number, picks list is reset
            | n when n > top -> step t [h] n
            // if RNG ties top number, add current element to picks list
            | n when n = top -> step t (h::ps) top
            // otherwise ignore and move to next element
            | _ -> step t ps top
    step lst [] -1

// pro: exactly 1 pass
// con: more complex, slowest in practice due to tuple allocations
let method3 lst (rng : Random) =
    snd <| List.fold (fun (i, pick) elem ->
               if rng.Next(i) = 0 then (i + 1, elem)
               else (i + 1, pick)
           ) (0, List.head lst) lst

编辑： 我应该澄清一下，上面显示了几种从列表中获取随机元素的方法，假设您必须使用列表。如果它适合你程序的其余部分设计，从数组中随机取一个元素肯定更有效。

Answer 3

这里 latkin 和 mydogisbox 给出的答案都很好，但我仍然想添加我有时使用的第三种方法.这种方法并不更快，但它更灵活、更可组合，并且对于小序列来说足够快。根据您的需要，您可以使用此处提供的更高性能选项之一，也可以使用以下选项。

使用 Random 的单参数函数

我通常定义一个 shuffleR 函数，而不是直接让您 select 单个元素：

open System

let shuffleR (r : Random) xs = xs |> Seq.sortBy (fun _ -> r.Next())

此函数的类型为 System.Random -> seq<'a> -> seq<'a>，因此它适用于任何类型的序列：列表、数组、集合和惰性求值序列（尽管不适用于无限序列）。

如果您想要列表中的单个随机元素，您仍然可以这样做：

> [1..100] |> shuffleR (Random ()) |> Seq.head;;
val it : int = 85

但您也可以取三个随机选择的元素：

> [1..100] |> shuffleR (Random ()) |> Seq.take 3;;
val it : seq<int> = seq [95; 92; 12]

无参函数

有时，我不关心必须传递那个 Random 值，所以我改为定义这个替代版本：

let shuffleG xs = xs |> Seq.sortBy (fun _ -> Guid.NewGuid())

它的工作原理是一样的：

> [1..100] |> shuffleG |> Seq.head;;
val it : int = 11
> [1..100] |> shuffleG |> Seq.take 3;;
val it : seq<int> = seq [69; 61; 42]

虽然 Guid.NewGuid() 的目的不是提供随机数，但对于我的目的来说它通常足够随机 - 随机，在 不可预测的 的意义上。 =36=]

广义函数

shuffleR 和 shuffleG 都不是真正随机的。由于 Random 和 Guid.NewGuid() 的工作方式，这两个函数可能会导致稍微偏斜的分布。如果这是一个问题，您可以定义一个更通用的 shuffle 函数：

let shuffle next xs = xs |> Seq.sortBy (fun _ -> next())

此函数的类型为 (unit -> 'a) -> seq<'b> -> seq<'b> when 'a : comparison。它仍然可以与 Random:

一起使用

> let r = Random();;    
val r : Random    
> [1..100] |> shuffle (fun _ -> r.Next()) |> Seq.take 3;;
val it : seq<int> = seq [68; 99; 54]
> [1..100] |> shuffle (fun _ -> r.Next()) |> Seq.take 3;;
val it : seq<int> = seq [99; 63; 11]

但您也可以将它与 Base Class 库提供的一些加密安全随机数生成器一起使用：

open System.Security.Cryptography
open System.Collections.Generic

let rng = new RNGCryptoServiceProvider ()
let bytes = Array.zeroCreate<byte> 100
rng.GetBytes bytes

let q = bytes |> Queue

金融服务机构：

> [1..100] |> shuffle (fun _ -> q.Dequeue()) |> Seq.take 3;;
val it : seq<int> = seq [74; 82; 61]

不幸的是，正如您从这段代码中看到的那样，它非常笨重和脆弱。您必须预先知道序列的长度； RNGCryptoServiceProvider 实现了 IDisposable，所以你应该确保在使用后处理掉 rng；并且项目将在使用后从 q 中删除，这意味着它不可重复使用。

加密随机排序或 selection

相反，如果您确实需要密码正确的排序或selection，这样做会更容易：

let shuffleCrypto xs =
    let a = xs |> Seq.toArray

    use rng = new RNGCryptoServiceProvider ()
    let bytes = Array.zeroCreate a.Length
    rng.GetBytes bytes

    Array.zip bytes a |> Array.sortBy fst |> Array.map snd

用法：

> [1..100] |> shuffleCrypto |> Array.head;;
val it : int = 37
> [1..100] |> shuffleCrypto |> Array.take 3;;
val it : int [] = [|35; 67; 36|]

虽然这不是我必须做的事情，但我认为为了完整起见我会把它包括在这里。虽然我没有对其进行测量，但它很可能不是最快的实现，但它应该是加密随机的。

如何使用 F# select 列表中的随机值

How can I select a random value from a list using F#

random

f#

f#-interactive

使用 Random 的单参数函数

无参函数

广义函数

加密随机排序或 selection