F# 中的采样：设置是否足够？

Question

我有一系列物品，我想从中取样。

我的印象是，集合是一个很好的采样结构，在折叠中，我会返回原始集合或修改后的集合，其中检索到的元素丢失，具体取决于我是否想要替换。 但是，似乎没有方法可以直接从 Set 中检索元素。

我有什么遗漏的吗？或者我应该使用索引集以及从某个随机

position < Set.count

开始并上升直到找到成员的代理函数？

也就是说，沿着这条线的东西

module Seq =
    let modulo (n:int) start = 
        let rec next i = seq { yield (i + 1)%n ; yield! next (i+1)}
        next start

module Array =
    let Sample (withReplacement:bool) seed (entries:'T array) = 
        let prng, indexes = new Random(seed), Set(Seq.init (entries |> Array.length) id)
        Seq.unfold (fun set  -> let N = set |> Set.count
                                let next = Seq.modulo N (prng.Next(N)) |> Seq.truncate N |> Seq.tryFind(fun i -> set |> Set.exists ((=) i))
                                if next.IsSome then
                                    Some(entries.[next.Value], if withReplacement then set else Set.remove next.Value set)
                                else
                                    None)

编辑：积极跟踪我所给予的，而不是跟踪我仍然可以给予的，会让事情变得更简单、更高效。

Answer 1

对于采样而不需要替换，您可以仅排列源序列并获取您想要采样的任意数量的元素

let sampleWithoutReplacement n s =
    let a = Array.ofSeq s
    seq { for i = a.Length downto 1 do
              let j = rnd.Next i
              yield a.[j]
              a.[j] <- a.[i - 1] }
    |> Seq.take n

要对和替换进行采样，只需从源序列中随机选择n次元素

let sampleWithReplacement n s =
    let a = Array.ofSeq s
    Seq.init n (fun _ -> a.[rnd.Next(a.Length)])

然而，对于庞大的数据集，这些可能不是最有效的方法

Answer 2

继续我们的评论......如果您想随机采样一个序列而不将整个事物放入内存中，您可以生成一组与您所需样本大小相同的随机索引（与您已有的没有太大不同）：

let rand count max = 
  System.Random() 
    |> Seq.unfold (fun r -> Some(r.Next(max), r))
    |> Seq.distinct
    |> Seq.take count
    |> set

let takeSample sampleSize inputSize input =
  let indices = rand sampleSize inputSize
  input
    |> Seq.mapi (fun idx x -> 
      if Set.contains idx indices then Some x else None)
    |> Seq.choose id

let inputSize = 100000
let input = Seq.init inputSize id
let sample = takeSample 50 inputSize input
printfn "%A" (Seq.toList sample)

Answer 3

与 @Patrick McDonald 的答案相同，2024 年使用 .NET 9 的答案：

let sampleWithoutReplacement n s =
    s
    |> Seq.ofSeq
    |> Seq.randomShuffleBy (fun () -> rnd.NextDouble()) 
    |> Seq.truncate n