取样(算法)

布满荆棘的人生 2022-03-17 13:18 119阅读 0赞

取样问题并不是随机产生一些一定范围的整数即可。取样问题要求在n个连续有序整数中等概率取出m项，且该m项样本有序。  
        关键是等概率的问题。考虑m=2，n=5的情况。  
        如果使用if(rand()%5)<2那么选出第一个整数0的概率为2/5，但是不能用这样的表达式选择1，因为这样的表达式选出的项数是不定的。  
        正确的形式应该是这样：

void select1(int m, int n)
    {
    	for(int i=0;i<n;i++)
    	{
    	/*这里是n-i，因为还剩下n-i个元素，这样配合m--就可以实现等概率。*/
    		if(rand()%(n-i)<m)           
    			cout << i<<endl;
    			m--;
    	}
    }

分析这个算法，时间复杂度为O(n)，我只要选择m个数，n的复杂度似乎有点高了。  有一种想法是只要将序列的前m个元素打乱就可以了。

void select2(int m, int n)
    {
    	int i,j;
    	int *x = new int[n]; 
    	for(i=0; i<n; i++)       //这里是劣势所在，初始化不仅耗费而来时间，
    				 //而且耗费了内存
    		x[i]= i ;
    	for (i=0; i<m; i++)      //这里的循环只用m次
    		j=randint(i,n-1);
    		swap(x[i],x[j]);
    	sort(x,x+m)
    	for(i=0; i<m; i++)
    		cout << x[i] << endl;
    }
    //这个算法m==n的时候就是洗牌算法了

另一种解决方案是在一个初始为空的集合中插入随机整数知道个数为m，但是要确保不重复。采用STL的set来实现。

void select2(int m, int n)
    {
    	set<int> S;
    	while(S.size() < m)
    		S.insert(rand()%n);//STL的set保证元素不重复，否则插入无效
    	for(set<int>::iterator i=S.begin();i!=S.end();++i)
    		cout <<*i<<endl;
    }

STL的set的底层结构是红黑树，对于红黑树的插入操作时间复杂度是O(lgm)，遍历集合的时间是O(m)，因此完整的程序需要O(mlgm)。但是使用红黑树必然会导致空间开销比较大。另外再插入的时候有一些重复的数据被丢弃了，并不是每一次运算都是成功的。所以虽然在时间复杂度上面有一定的提升，但是由于上述两点缺点还是有可优化的余地。

并且由于该算法的元素是按随机顺序插入的，这一点很重要，所以不用考虑复杂的平衡方案。所以如果自己构建一个二分搜索树，一般的情况下会比STL的set更加高效。（这里要理解STL考虑到了复用性和易维护性，所以其考虑平均效果，而针对特定问题自己编码一般是可以在效率上超过STL的。）并且这个二分搜索树还可以进行优化。比如：！！！对内存进行一次性分配，只分配一个较大内存块来替代通用的内存分配。这就消除了很多开销较大的调用，也是空间的利用率更加有效。！！！