我有一个包含n个元素的外部集合,我想随机选择它们中的一些数字(k),将这些元素的索引输出到某个序列化数据文件.我希望索引以严格的升序输出,并且没有重复. n和k都可能非常大,并且将整个数组简单地存储在该大小的存储器中通常是不可行的.
我想出的第一个算法是从1到nk中选择一个随机数r [0] …然后从r [i-1] 1到nk i中选择一个连续的随机数r [i],只需要在任何时候都存储’r’的两个条目.然而,一个相当简单的分析表明,选择小数的概率与整个集合均匀分布时的概率不一致.例如,如果n是十亿,k是五亿,那么用我刚刚描述的方法选择第一个条目的概率非常小(五分之一十亿),实际上,因为一半条目是被选中,第一个应该在50％的时间被选中.即使我使用外部排序来对k个随机数进行排序,我也不得不丢弃任何重复项,然后再试一次.当k接近n时,重试次数将继续增加,但不保证终止.
如果可能的话,我想找到一个O(k)或O(k log k)算法来做到这一点.我将使用的实现语言是C 11,但伪代码中的描述可能仍然有用.
解决方法
如果在范围的中间进行分区,则可以在O(k log k)中递归求解,并从
hypergeometric probability distribution中随机采样以选择中间点上方和下方有多少值(即每个子序列的k值),然后递归每个：
int sample_hypergeometric(int n,int K,int N) // samples hypergeometric distribution and
// returns number of "successes" where there are n draws without replacement from
// a population of N with K possible successes.
// Something similar to scipy.stats.hypergeom.rvs in Python.
// In this case,"success" means the selected value lying below the midpoint.
{
std::default_random_engine generator;
std::uniform_real_distribution<double> distribution(0.0,1.0);
int successes = 0;
for(int trial = 0; trial < n; trial++)
{
if((int)(distribution(generator) * N) < K)
{
successes++;
K--;
}
N--;
}
return successes;
}
select_k_from_n(int start,int k,int n)
{
if(k == 0)
return;
if(k == 1)
{
output start + random(1 to n);
return;
}
// find the number of results below the mid-point:
int k1 = sample_hypergeometric(k,n >> 1,n);
select_k_from_n(start,k1,n >> 1);
select_k_from_n(start + (n >> 1),k - k1,n - (n >> 1));
}
来自binomial distribution的采样也可用于近似超几何分布,其中p =(n> 1)/ n,拒绝其中k1> 1的样本. (n>> 1).
