如何正确的显示随机消息(3)--随机排序算法

前言：本公众号将推出系列性的知识分享，以专题或者模块的方式，向读者分享学习体会和心得。所以想要学习的朋友可以点击关注，一起学习。

今天首先我们把问题简化，如果只是随机的选取一个word，可以怎么做呢？思路基本就是这样的：

1.取得一张表的id的最大值和最小值，分别为M和N。

2.使用随机函数计算得到一个最大值和最小值之间的一个数X=(M-N)*rand()+N;

3.取不小于X的id的值的行数据。

我们暂时把这个算法称为随机算法1。执行的语句如下：

mysql> select max(id),min(id) into @M,@N from t ;
set @X= floor((@M-@N+1)*rand() + @N);
select * from t where id >= @X limit 1;

这个方法地效率很高，因为max(id)和min(id)是不需要扫描索引的。而第三行的select可以使用索引快速定位，可以认为值扫描了3行。但是，仔细想想就会发现，这样的随机并不是题目中要求的正真的那种随机，因为表中的数据的id可能存在有漏缺，这样取到每一个id所对应的数据的概率就会不一样了。所以以上的算法并不是正真意义上的随机算法。

举个栗子：

比如有一张表的id是1,2,4,5，那么按照上面的算法，id=4这个出现的概率就会是其他的两倍，显然以上的算法是有问题的。

为了得到更加符合我们要求的算法我们调整一下我们的思路：

1.首先去得整张表的行数，并且记为C。

2.去得Y=floor(C*rand())。floor函数的作用是取整数的部分。

3.再利用limit Y,1来取得这一行。

我们暂时把这个算法称为随机算法2。语句如下：

mysql> select count(*) into @C from t;
set @Y = floor(@C * rand());
set @sql = concat("select * from t limit ", @Y, ",1");
prepare stmt from @sql;
execute stmt;
DEALLOCATE prepare stmt;

随机算法2显然解决了算法1出现的概率分布不均匀的问题。MySQL处理limit Y,1 的做法就是按顺序一个一个地读出来，丢掉前Y个，然后把下一个记录作为返回结果，因此这一步需要扫描Y+1行。再加上，第一步扫描的C行，总共需要扫描C+Y+1行，执行代价比随机算法1的代价要高。

当然，随机算法2跟直接order by rand()比起来，执行代价还是小很多的。虽然，在取得一个很大的Y值的时候，所扫描到的行数基本和order by rand()差不多，但是总体来说，代价要小的多。

现在我们来分析一下，如果利用随机算法2，来实现随机获取三个word的实现流程吧。

1. 取得整个表的行数，记为C；

2. 根据相同的随机方法得到Y1、Y2、Y3；

3. 再执行三个limit Y, 1语句得到三行数据。

我们把这个算法，称作随机算法3。语句如下：

mysql> select count(*) into @C from t;
set @Y1 = floor(@C * rand());
set @Y2 = floor(@C * rand());
set @Y3 = floor(@C * rand());
select * from t limit @Y1，1；//在应用代码里面取Y1、Y2、Y3值，拼出SQL后执行
select * from t limit @Y2，1；
select * from t limit @Y3，1；

以上的三篇文章只要解释了MySQL中对临时表排序的问题的解释。如果你直接使用order by rand()，这个语句需要Using temporary 和 Using filesort，查询的执行代价往往是比较大的。所以，在设计的时候你要量避开这种写法。

好了，今天的介绍到这里就结束了，大家有问题了可以私信我，大家共同学习，一起进步哈！

喜欢的同学可以点击“在看”，并且关注ITwords微信公众号，第一时间获取更新内容。您的转发和点赞将是我原创的动力，感谢您的支持。

扫描二维码

获取更多精彩

ITwords

往期回顾：

如何正确的显示随机消息(2)--磁盘临时表