函数生成的错误长度的顺序

Question

当repl变量设置为false时,为什么以下函数返回不正确长度的序列？

open MathNet.Numerics.Distributions
open MathNet.Numerics.LinearAlgebra
let sample (data : seq<float>) (size : int) (repl : bool) =

    let n = data |> Seq.length

    // without replacement
    let rec generateIndex idx =
        let m = size - Seq.length(idx)
        match m > 0 with
        | true ->
            let newIdx = DiscreteUniform.Samples(0, n-1) |> Seq.take m 
            let idx = (Seq.append idx newIdx) |> Seq.distinct
            generateIndex idx
        | false -> 
            idx

    let sample =
        match repl with
        | true ->
            DiscreteUniform.Samples(0, n-1) 
            |> Seq.take size 
            |> Seq.map (fun index -> Seq.item index data)
        | false ->
            generateIndex (seq []) 
            |> Seq.map (fun index -> Seq.item index data)

    sample

运行功能......

let requested = 1000
let dat = Normal.Samples(0., 1.) |> Seq.take 10000
let resultlen = sample dat requested false |> Seq.length 
printfn "requested -> %A\nreturned -> %A" requested resultlen

结果长度是错误的.

> 
requested -> 1000
returned -> 998

> 
requested -> 1000
returned -> 1001

> 
requested -> 1000
returned -> 997

知道我在做什么错吗？

Answer 1

首先,我想对编码风格做出评论.然后我将解释为什么你的序列会以不同的长度返回.

在评论中,我提到用match (bool) with true -> ... | false -> ...一个简单的if ... then ... else表达式替换,但是你正在使用的另一种编码风格我认为可以改进.你写了:

let sample (various_parameters) =  // This is a function
    // Other code ...
    let sample = some_calculation  // This is a variable
    sample  // Return the variable

虽然F#允许您重复使用这样的名称,并且函数内部的名称将"遮蔽"函数外部的名称,但重用名称与原始名称的类型完全不同通常是个坏主意.换句话说,这可能是一个好主意:

let f (a : float option) =
    let a = match a with
            | None -> 0.0
            | Some value -> value
    // Now proceed, knowing that `a` has a real value even if had been None before

或者,因为以上内容正是F#为您defaultArg提供的:

let f (a : float option) =
    let a = defaultArg a 0.0
    // This does exactly the same thing as the previous snippet

在这里,我们使a函数内部的名称引用与参数名称不同的类型a:参数是a float option,而a函数内部是a float.但它们有点"相同"类型 - 也就是说,"调用者可能指定了浮点值或者它们可能没有"和"现在我肯定有一个浮点值"之间的精神差异很小" .但是"名称是一个带三个参数的函数"和"名称是一系列浮点数" 之间存在着非常大的精神差距.我强烈建议使用类似于您将从函数返回的值的名称,而不是重新使用函数名称.samplesampleresult

此外,这似乎不必要地冗长:

let result =
    match repl with
    | true ->
        DiscreteUniform.Samples(0, n-1) 
        |> Seq.take size 
        |> Seq.map (fun index -> Seq.item index data)
    | false ->
        generateIndex (seq []) 
        |> Seq.map (fun index -> Seq.item index data)

result

任何时候我发现自己在我的函数结束时写了"let result =(something); result",我通常只想用整个代码块替换整个代码块(something).即,上面的代码片段可能会成为:

match repl with
| true ->
    DiscreteUniform.Samples(0, n-1) 
    |> Seq.take size 
    |> Seq.map (fun index -> Seq.item index data)
| false ->
    generateIndex (seq []) 
    |> Seq.map (fun index -> Seq.item index data)

反过来可以用if...then...else表达式替换:

if repl then
    DiscreteUniform.Samples(0, n-1) 
    |> Seq.take size 
    |> Seq.map (fun index -> Seq.item index data)
else
    generateIndex (seq []) 
    |> Seq.map (fun index -> Seq.item index data)

这是代码中的最后一个表达式.换句话说,我可能会按如下方式重写您的函数(仅更改样式,不更改逻辑):

open MathNet.Numerics.Distributions
open MathNet.Numerics.LinearAlgebra
let sample (data : seq<float>) (size : int) (repl : bool) =

    let n = data |> Seq.length

    // without replacement
    let rec generateIndex idx =
        let m = size - Seq.length(idx)
        if m > 0 then
            let newIdx = DiscreteUniform.Samples(0, n-1) |> Seq.take m 
            let idx = (Seq.append idx newIdx) |> Seq.distinct
            generateIndex idx
        else
            idx

    if repl then
        DiscreteUniform.Samples(0, n-1) 
        |> Seq.take size 
        |> Seq.map (fun index -> Seq.item index data)
    else
        generateIndex (seq []) 
        |> Seq.map (fun index -> Seq.item index data)

如果我能弄清楚为什么你的序列长度不对,我也会用这些信息更新这个答案.

更新:好的,我想我看到你的generateIndex功能正在发生什么,给你意想不到的结果.绊倒你有两件事:一件是序列懒惰,另一件是随机性.

我将你的generateIndex函数复制到VS代码中并添加了一些printfn语句来查看正在发生的事情.首先,我运行的代码,然后结果:

let rec generateIndex n size idx =
    let m = size - Seq.length(idx)
    printfn "m = %d" m
    match m > 0 with
    | true ->
        let newIdx = DiscreteUniform.Samples(0, n-1) |> Seq.take m
        printfn "Generating newIdx as %A" (List.ofSeq newIdx)
        let idx = (Seq.append idx newIdx) |> Seq.distinct
        printfn "Now idx is %A" (List.ofSeq idx)
        generateIndex n size idx
    | false -> 
        printfn "Done, returning %A" (List.ofSeq idx)
        idx

所有这些List.ofSeq idx调用都是这样的,当我打印出来时,F#Interactive将打印超过四个seq项(默认情况下,如果你尝试打印seq %A,它只打印出四个值,然后打印省略号,如果有的话seq中可用的更多值).另外,我转身n和size到参数(我不调用之间变化),这样我可以很容易地进行测试.然后我将其称为generateIndex 100 5 (seq [])并得到以下结果:

m = 5
Generating newIdx as [74; 76; 97; 78; 31]
Now idx is [68; 28; 65; 58; 82]
m = 0
Done, returning [37; 58; 24; 48; 49]
val it : seq<int> = seq [12; 69; 97; 38; ...]

看看数字如何变化？这是我的第一个线索,有些事情发生了.看,seqs 很懒.他们不必评估他们的内容.您不应该将a seq视为数字列表.相反,把它想象成一个发电机,当被问到数字时,会根据某些规则产生它们.在您的情况下,规则是"选择0和n-1 之间的随机整数,然后取m这些数字".关于seqs 的另一件事是它们不缓存它们的内容(尽管有一个Seq.cache可用的函数可以缓存它们的内容).因此,如果你有一个seq基于随机数生成器,它的结果每次都会有所不同,你可以在我的输出中看到.当我打印出来时newIdx,打印出[74; 76; 97; 78; 31],但当我将它附加到空seq时,结果打印为[68; 28; 65; 58; 82.

为何如此区别？因为Seq.append 它没有强制评估.它只是创建一个新seq的规则是"从第一个seq中取出所有物品,然后当那个物品耗尽时,从第二个seq中取出所有物品.当那个物品耗尽时,结束." 并且Seq.distinct不强制评估; 它只是创造了一个新seq的规则是"将物品从seq手中拿走给你,并在被问到时开始将它们分发出来.但是当你去的时候记住它们,如果你之前把它们中的一个交出去,不要交给它又出来了." 所以你在调用之间传递的generateIdx是一个对象,当被评估时,它会选择一组介于0和n-1之间的随机数(在我的简单情况下,介于0和100之间),然后将该组缩小为a不同的数字集.

现在,这就是事情.每次评估时seq,它都会从头开始:首先调用DiscreteUniform.Samples(0, n-1)生成无限的随机数m流,然后从该流中选择数字,然后丢弃任何重复数据.(我现在忽略了Seq.append它,因为它会产生不必要的心理复杂性,而且它实际上并不是bug的一部分).现在,在函数的每个循环开始时,检查序列的长度,这会导致它被评估.这意味着它选择(在我的示例代码的情况下)0到99之间的5个随机数,然后确保它们都是不同的.如果它们是完全不同的,那么m= 0和功能将退出,返回......数字的不在列表,但该seq对象.当seq评估该对象时,它将从头开始,选择一组不同的5个随机数,然后丢弃任何重复项.因此,仍然有可能该组5个数字中的至少一个最终会成为重复,因为测试其长度的序列(我们知道它不包含重复,否则m会大于0)不是序列那是归来的.返回的序列具有1.0*0.99*0.98*0.97*0.96的机会,不包含任何重复项,大约为0.9035.所以这是一个10刚刚下%的机会,即使你检查Seq.length,这是5时,返回的长度seq最终被终究4 -因为它选择一个不同的组随机数比您选中的.

为了证明这一点,我再次运行该函数,这次只挑选4个数字,以便在F#Interactive提示下完全显示结果.我的运行generateIndex 100 4 (seq [])产生了以下输出:

m = 4
Generating newIdx as [36; 63; 97; 31]
Now idx is [39; 93; 53; 94]
m = 0
Done, returning [47; 94; 34]
val it : seq<int> = seq [48; 24; 14; 68]

注意当我打印"完成,返回(值idx)"时,它只有3个值？即使它最终返回4个值(因为它为实际结果选择了不同的随机数选择,并且该选择没有重复),这证明了问题.

顺便说一句,有一个其他问题,您的功能,这是它的远远慢于它需要.Seq.item在某些情况下,该函数必须从头开始执行序列,以便选择n序列的第th项.在函数开始时将数据存储在数组中会更好let arrData = data |> Array.ofSeq,然后替换

        |> Seq.map (fun index -> Seq.item index data)

同

        |> Seq.map (fun index -> arrData.[index])

数组查找是在恒定时间内完成的,因此将样本函数从O(N ^ 2)降低到O(N).

TL; DR:Seq.distinct 在从中获取m值之前使用,bug将消失.您只需简单地替换整个generateIdx功能即可DiscreteUniform.Samples(0, n-1) |> Seq.distinct |> Seq.take size.(并使用数组进行数据查找,以便您的函数运行得更快).换句话说,这是最后 几乎是我将如何重写代码的最终版本:

let sample (data : seq<float>) (size : int) (repl : bool) =
    let arrData = data |> Array.ofSeq
    let n = arrData |> Array.length

    if repl then
        DiscreteUniform.Samples(0, n-1) 
        |> Seq.take size 
        |> Seq.map (fun index -> arrData.[index])
    else
        DiscreteUniform.Samples(0, n-1) 
        |> Seq.distinct
        |> Seq.take size 
        |> Seq.map (fun index -> arrData.[index])

而已!简单,易于理解,并且(据我所知)无错误.

编辑: ...但不完全干,因为在"最终"版本中仍然有一些重复的代码.(感谢CaringDev在下面的评论中指出它).将Seq.take size |> Seq.map重复在两个分支if的表达,所以有一种方法来简化表达.我们可以这样做:

let randomIndices =
    if repl then
        DiscreteUniform.Samples(0, n-1) 
    else
        DiscreteUniform.Samples(0, n-1) |> Seq.distinct

randomIndices
|> Seq.take size 
|> Seq.map (fun index -> arrData.[index])

所以这是我的建议的真正最终版本:

let sample (data : seq<float>) (size : int) (repl : bool) =
    let arrData = data |> Array.ofSeq
    let n = arrData |> Array.length
    let randomIndices =
        if repl then
            DiscreteUniform.Samples(0, n-1) 
        else
            DiscreteUniform.Samples(0, n-1) |> Seq.distinct
    randomIndices
    |> Seq.take size 
    |> Seq.map (fun index -> arrData.[index])