如何使用F#从列表中选择随机值

Question

我是F#的新手,我正在试图弄清楚如何从列表/字符串数组中返回一个随机字符串值.

我有一个这样的列表:

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

如何从上面的列表中随机选择并返回一个项目？

这是我的第一次尝试:

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

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

Answer 1

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

使用Random的单参数函数

我经常定义一个shuffleR这样的函数,而不是直接让你选择一个元素:

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()不是提供随机数,但对于我的目的而言,它通常是随机的 - 随机的,在不可预测的意义上.

广义功能

既不是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]

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

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

FSI:

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

不幸的是,正如你从这段代码中看到的那样,它非常麻烦和脆弱.你必须预先知道序列的长度; RNGCryptoServiceProvider工具IDisposable,所以你应该确保rng在使用后处理; 并且物品将q在使用后被移除,这意味着它不可重复使用.

密码随机排序或选择

相反,如果你真的需要加密正确的排序或选择,那么这样做会更容易:

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|]

然而,这不是我曾经做过的事情,但我认为为了完整起见我会把它包含在这里.虽然我没有测量它,但它很可能不是最快的实现,但它应该是加密随机的.

Answer 2

你的问题是你混合Arrays和F#List(*type*[]是一种类型符号Array).您可以像这样修改它以使用列表:

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

话虽如此,索引为a List通常是一个坏主意,因为它具有O(n)性能,因为F#列表基本上是链表.combos如果可能的话,最好还是制作一个数组:

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

Answer 3

我刚刚写了一篇关于这个主题的博客文章: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

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