假设我有一个排序的值数组:
int n=4; // always lower or equal than number of unique values in array
int i[256] = {};
int v = {1 1 2 4 5 5 5 5 5 7 7 9 9 11 11 13}
// EX 1 ^ ^ ^ ^
// EX 2 ^ ^ ^ ^
// EX 3 ^ ^ ^ ^
我想生成n个随机索引值i[0] ... i[n-1]
,这样:
v[i[0]] ... v[i[n-1]]
指向一个唯一的数字(即不得指向5两次)到目前为止我尝试过的:
我在C中实现这一点,因此我可以依赖的标准C函数越多,代码越短越好。 (例如,shuffle
不是标准的C函数,但如果必须,我必须。)
创建最后一个索引值的数组
int last[] = { 1, 2, 3, 8, 10, 12, 14 };
从洗牌阵列中取出第一个n-1
元素。
将索引添加到最终编号。
如果需要,对结果数组进行排序。
该算法称为reservoir sampling,只要您知道需要多大的样本,就可以使用该算法,但不能使用您抽样的元素数量。 (这个名称来源于你总是保持一个正确数量的样本的储存器。当一个新值进入时,你将它混合到储存器中,移除一个随机元素,然后继续。)
sample
的返回值数组n
。sample
的末尾,直到有n
采样元素。r
,其中i
是到目前为止看到的唯一值的数量。
湾如果r
小于n
,则用新元素覆盖元素r
。sample
,假设你需要对它进行排序。要确保始终拥有样本中的最后一个元素,请运行上面的算法以选择大小为n-1
的样本。只有在找到更大的元素时才考虑新元素。
该算法在v
的大小是线性的(加上最后一步中排序的n log n
术语。)如果你已经有每个值的最后索引列表,那么算法更快(但是你会知道它的大小)在您开始采样之前的宇宙;如果您不知道,那么水库采样主要是有用的。)
事实上,它在概念上与收集所有指数然后找到Fisher-Yates shuffle的前缀没有区别。但它使用O(n)临时内存而不是足以存储整个索引列表,这可能被认为是一个加号。
这是一个未经测试的示例C实现(需要您编写函数randrange()
):
/* Produces (in `out`) a uniformly distributed sample of maximum size
* `outlen` of the indices of the last occurrences of each unique
* element in `in` with the requirement that the last element must
* be in the sample.
* Requires: `in` must be sorted.
* Returns: the size of the generated sample, while will be `outlen`
* unless there were not enough unique elements.
* Note: `out` is not sorted, except that the last element in the
* generated sample is the last valid index in `in`
*/
size_t sample(int* in, size_t inlen, size_t* out, size_t outlen) {
size_t found = 0;
if (inlen && outlen) {
// The last output is fixed so we need outlen-1 random indices
--outlen;
int prev = in[0];
for (size_t curr = 1; curr < inlen; ++curr) {
if (in[curr] == prev) continue;
// Add curr - 1 to the output
size_t r = randrange(0, ++found);
if (r < outlen) out[r] = curr - 1;
prev = in[curr];
}
// Add the last index to the output
if (found > outlen) found = outlen;
out[found] = inlen - 1;
}
return found;
}