mysql带权重的随机算法_随机选取算法 (有权重的记录中选取)~转

三类随机问题

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对应上？ 其实也比较简单，用二分法查找即可。

下面附上实现代码：

1 三类随机问题2 1. 已有n条记录，从中选取m条记录，选取出来的记录前后顺序不管。3 实现思路：按行遍历所有记录，约隔n/m条取一个数据即可4

5 2. 在1类情况下，还要求选取出来的m条记录是随机排序的6 实现思路： 给n条记录，分别增加一列标记，值为随机选取的1至n之间的不重复数据，7 实现参考博文 将文件内容按行随机排列8

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

11

12 这第三类问题是本文重点，下面开始解决。13 实现思路： 以 A:10， B:5， C:1三条记录上随机选取4条为例，(是否以权重排序这个无所谓)14 对于15 A 10

16 B 5

17 C 1

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

20 B 15

21 C 16

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

24

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