Tag Archives: 随机

蓄水池算法

问题描述

要求从N个元素中随机的抽取k个元素,其中N无法确定(N是个流,可能无穷大)。

这种应用的场景一般是数据流的情况下,由于数据只能被读取一次,而且数据量很大,并不能全部保存,因此数据量N是无法在抽样开始时确定的;但又要保持随机性,于是有了这个问题。所以搜索网站有时候会问这样的问题。

这里的核心问题就是“随机”,怎么才能是随机的抽取元素呢?我们设想,买彩票的时候,由于所有彩票的中奖概率都是一样的,所以我们才是“随机的”买彩票。那么要使抽取数据也随机,必须使每一个数据被抽样出[……]

继续阅读

MySQL中随机select记录

我有这个需求:

数据库中的uid离散分布不连续,需要随机select某一条记录。

1、最懒做法
select uid, uname from user order by RAND() limit 1
这个非常慢,因为几乎要遍历整个表。

2、用id随机范围。

其实如果我们能得到min(uid)和max(uid),然后随机这之间的某一个ID,再where >= 就可以了。

首先是获取min和max的uid:
select min(uid), max(uid)[……]

继续阅读