f# - 函数生成的长度不正确的序列

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的参数的类型:参数为 float option，而函数内的 a为 float。但它们属于“相同”类型-也就是说，“调用方可能已指定浮点值或未指定浮点值”与“现在我肯定有浮点值”之间在精神上几乎没有什么区别。 。但是，“ sample名称是一个带有三个参数的函数”与“ sample名称是浮点数的序列”之间存在很大的思维鸿沟。我强烈建议您使用诸如 result之类的名称作为要从函数返回的值，而不是重复使用函数名。

另外，这似乎不必要地冗长:

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 Code中，并添加了一些 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，它将仅打印出四个值，然后在省略号时打印省略号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; ...]

看看数字如何不断变化？那是我第一个提示出什么事了。看到， seq是 lazy 。他们不评估自己的内容，除非必须这样做。您不应该将 seq视为数字列表。取而代之的是，将其视为一种生成器，当要求输入数字时，它将根据某些规则生成数字。在您的情况下，规则是“选择0到 n -1之间的随机整数，然后采用这些数字的 m”。关于 seq的另一件事是它们不缓存其内容(尽管有一个 Seq.cache 函数可以缓存其内容)。因此，如果您有一个基于随机数生成器的 seq，则每次生成的结果都会不同，正如您在我的输出中看到的那样。当我打印出 newIdx时，它打印为[74; 76; 97; 78; 31]，但是当我将其附加到一个空序列时，结果打印为[68; 28; 65; 58; 82]。

为什么会有这种差异？因为 Seq.append会执行 而不是强制评估。它只是创建一个新的 seq，其规则是“从第一个序列中取出所有项目，然后在第二个序列中消耗完时，从第二个序列中取出所有项目。而当一个耗尽时，结束。 Seq.distinct也不强制评估；它只是创建一个新的 seq，其规则是“从递给您的 seq中取出项目，并在被询问时开始分发。但是请记住它们，如果您以前曾分发过其中一个，请不要再次分发。”因此，在调用 generateIdx之间传递的是一个对象，该对象在被求值时会选择一组介于0和n-1之间的随机数(在我的简单情况下，介于0和100之间)，然后将其减少为一组不同的数字。

现在，这是事情。每次您评估 seq时，它都会从头开始:首先调用 DiscreteUniform.Samples(0, n-1)生成无限的随机数流，然后从该流中选择 m数字，然后丢弃所有重复项。 (我现在暂时忽略了 Seq.append，因为它会造成不必要的心理复杂性，而且无论如何它实际上都不是错误的一部分)。现在，在每次执行功能时，您都要检查序列的长度，这确实会导致对其进行求值。这意味着(在我的示例代码中)它选择了0到99之间的5个随机数，然后确保它们都是不同的。如果它们都是不同的，则 m = 0且函数将退出，返回...不是数字列表，而是 和seq对象。并且当对该 seq对象求值时，它将从头开始，选择5个随机数的不同集合，然后丢弃所有重复项。因此，仍然有机会在这5个数字中至少有一个最终成为重复项，因为长度经过测试的序列(我们知道该序列不包含重复项，否则 m会大于0)不是返回的序列。返回的序列有1.0 * 0.99 * 0.98 * 0.97 * 0.96的机会不包含任何重复项，约为0.9035。因此，即使您检查了 Seq.length并将其设为5，也有不到10％的机会，毕竟返回的 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第一项。最好在函数开始时将数据存储在数组中( 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值，该错误将消失。您可以将整个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])

而已!简单，易于理解，并且(据我所知)没有错误。

编辑: ...但不是完全DRY，因为在该“最终”版本中仍然有一些重复的代码。 (在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])