函数生成的错误长度序列

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 -> %Anreturned -> %A" requested resultlen

生成的长度是错误的。

> 
requested -> 1000
returned -> 998
> 
requested -> 1000
returned -> 1001
> 
requested -> 1000
returned -> 997

知道我犯了什么错误吗？

Answer 1

首先，我想对编码风格发表评论。然后，我将解释为什么您的序列以不同的长度返回。

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

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

每当我发现自己在写"让结果=(某事);结果"在我的函数结束时，我通常只想用(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 时打印四个以上的项目(默认情况下，如果您尝试打印带有%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是懒惰的。他们不会评估他们的内容，直到他们不得不评估。您不应该将seq视为数字列表。相反，将其视为一个生成器，当被要求提供数字时，它会根据某些规则生成它们。在您的情况下，规则是"选择 0 到n-1 之间的随机整数，然后取m这些数字"。关于seq的另一件事是它们不缓存其内容(尽管有一个Seq.cache函数可用来缓存其内容)。因此，如果你有一个基于随机数生成器的seq，它的结果每次都会不同，正如你在我的输出中看到的那样。当我打印出newIdx时，它打印为[74;76;97;78;31]，但是当我将其附加到一个空的seq时，结果打印为[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，返回的seq的长度最终还是 4 的可能性不到 10% - 因为它选择了一组与您检查的随机数不同的随机数。

为了证明这一点，我再次运行了该函数，这次只选择了 4 个数字，以便结果将完全显示在 F# 交互式提示符下。我的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：在你从中获取m值之前使用Seq.distinct，错误就会消失。您只需将整个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])