golang 中无替换的示例

Question

从 golang 中的切片进行无替换采样的最佳方法是什么？

a := make([]int, 100)
for i := range a {
    a[i] = i
}

# TODO sample 5 elements from a without replacement.

Answer 1

如果集合大小总体上相对较小，或者您正在对集合的大部分进行采样，最简单的方法是打乱元素并选择第一个 n:

rand.Shuffle(len(a), func(i, j int) { a[i], a[j] = a[j], a[i] })
fmt.Println(a[:5])

https://play.golang.org/p/lQx44Mn9RQL

如果您不想打乱整个集合，但可以改变集合的顺序（或复制整个集合），您可以 "record" 通过删除使用的值来更有效地使用它们来自切片。

// create a copy of the slice header
c := a
samples := make([]int, n)

for i := 0; i < n; i++ {
    r := int(rand.Int63n(int64(len(c))))
    samples[i] = c[r]

    // remove the sample from the copy slice
    c[r], c[len(c)-1] = c[len(c)-1], c[r]
    c = c[:len(c)-1]
}

如果集合大小很大，而你只抽取了一小部分，你可以通过记录样本索引而不重复它来从原始集合中不加修改地采样。显然，随着样本大小与集合大小之比的增加，碰撞次数也会增加，从而降低效率。

例如：

// record indexes here to prevent duplicates
indexes := make(map[int]bool)

// create n random indexes
for i := 0; i < n; i++ {
    var r int
    for {
        r = int(rand.Int63n(int64(len(a))))
        if indexes[r] {
            continue
        }
        break
    }

    indexes[r] = true
}

samples := make([]int, 0, n)
for i := range indexes {
    samples = append(samples, a[i])
}

Answer 2

根据样本需要的随机性，我可能会将元素复制到 map[T]struct{}（其中 T 是结果类型）并在其上复制 range我的结果。

// assume input is []int
res := make([]int, len(input))
desorted := make(map[int]struct{})

for _, v := range input {
        desorted[v] = struct{}
}

i := 0
for k, _ := range desorted {
        res[i] = k
        i++
}

golang 中无替换的示例

Sample without replacement in golang

random

go

slice

sampling