随机选取算法 (有权重的记录中选取)

60 阅读 0 评论 40 点赞

我是靠谱客的博主深情鸵鸟，这篇文章主要介绍随机选取算法 (有权重的记录中选取)，现在分享给大家，希望可以做个参考。

三类随机问题

1. 已有n条记录，从中选取m条记录，选取出来的记录前后顺序不管。

实现思路：按行遍历所有记录，约隔n/m条取一个数据即可

2. 在1类情况下，还要求选取出来的m条记录是随机排序的

实现思路：给n条记录，分别增加一列标记，值为随机选取的1至n之间的不重复数据，

实现参考博文将文件内容按行随机排列

3. 区别于1,2类问题，如果记录是有权重的，如何结合权重去随机选取。比如A的权重为10， B的权重股为5， C的权重为1，则随机选取4个时可能应该出现AABB。

这第三类问题是本文重点，下面开始解决。

实现思路： 以 A:10， B:5， C:1 三条记录上随机选取4条为例，（是否以权重排序这个无所谓）

对于

A 10

B 5

C 1

首先，将第n行的数值赋为第n行加第n-1行的，递归执行，如下：

A 10

B 15

C 16

然后每次从[1,16]随机选取一个数，如果落在[1,10]之间，则选取A，如果落在(10,15]之间则选B，如果落在(16,16]之间则选取C，图示如下，谁占的区间大（权重高），被选上的概率更大。

知道了思路，实现起来就比较方便了，需要考虑的一点可能就是我随即选了一个数值，比如12，我怎么跟B对应上？其实也比较简单，用二分法查找即可。

下面附上实现代码：

[cpp] 
view plain
copy

 #include <string>  
 #include <cstdlib>  
 #include <vector>  
   
 using namespace std;  
   
 const int LEN = 4098;   
 const int MAX_QUERY_LEN = 2048;  
   
 //返回属于[p,q)的随机数  
 int rand(int p, int q)  
 {  
      int size = q-p+1;  
      return  p+ rand()%size;   
 }  
   
 //删除行尾换行符  
 int chomp(char *str)  
 {  
     int len = strlen(str);  
     while(len > 0 && (str[len - 1] == 'n' || str[len - 1] == 'r'))  
     {  
         str[len - 1] = 0;  
         len--;  
     }  
     return len;  
 }  
   
 //获取一个随机数会落在哪个区间  
 int get_pos(vector<int> vec_freq, int begin, int end, int rand_num)  
 {  
     if(begin >= end)  
     {  
         return begin;  
     }  
       
     int mid = (begin + end)/2;  
     if( vec_freq[mid] >= rand_num )  
     {  
         return get_pos(vec_freq, begin, mid, rand_num );  
     }  
     else  
     {  
         return get_pos(vec_freq, mid+1, end, rand_num );  
     }  
 }  
   
 //主函数  
 int main(int argc, char *argv[])  
 {  
     //输入记录文件，两列，第一列为记录，第二列为热度值  
     FILE* infile = fopen(argv[1], "r");  
     if( infile == NULL )  
     {  
         printf("Cann't open file %s.", argv[1]);  
         return -1;  
     }  
   
     FILE* outfile = fopen(argv[2], "w");  
     if( outfile == NULL)  
     {  
         printf("Cann't open file %s to write.", argv[2]);  
         return -1;  
     }  
   
     //要获取的随机记录个数  
     int num = atoi(argv[3]);  
     if( num <= 0)  
     {  
         printf("num [%s] <= 0.");  
         return -1;  
     }  
   
     //这两个数组用下标关联  
     vector<string> vec_query;  
     vector<int> vec_freq;  
     vec_query.clear();  
     vec_freq.clear();  
     int freq = 0;  
     char line[MAX_QUERY_LEN]={0};  
       
         while( !feof(infile) )  
         {  
             if( !fgets(line, sizeof(line),infile))  
             {  
                 break;  
             }  
         line[sizeof(line)-1] = 0;  
             chomp(line);  
   
         char* p_tab = strchr(line, 't');  
         if( NULL == p_tab )  
         {  
             printf("line format error. [%s]n");  
             continue;  
         }  
         *p_tab = 0;  
   
         string query(line);  
         freq += atoi(p_tab+1);  
           
         vec_query.push_back(query);  
         vec_freq.push_back(freq);  
   
         //printf("%st%dn", line, freq);  
         }  
   
     for(int i=0; i < num; ++i)  
     {  
         int rand_num = rand(1, freq+1);  
         int pos = get_pos(vec_freq, 0, vec_freq.size(), rand_num);  
         fprintf(outfile, "%st%dt%dn", vec_query[pos].c_str(), vec_freq[pos], rand_num);  
     }  
       
     fclose(infile);  
     fclose(outfile);      
   
     return 0;  
 } 