来自Sql数据库的简单随机样本

这里有一个关于此类问题的非常有趣的讨论： http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

我认为在没有任何假设的情况下，您的O（n lg n）解决方案是最好的。尽管实际上使用好的优化程序或稍有不同的技术，但您列出的查询可能会更好一些，O（m * n）其中m是所需的随机行数，因为它不必对整个大型数组进行排序，它可能只搜索最小的m次。但是对于您发布的那种数字，无论如何，m大于lg n。

我们可以尝试以下三种假设：

表中有一个唯一的，已索引的主键

您要选择的随机行数（m）比表中的行数（n）小得多

唯一主键是一个整数，范围是1到n，没有空格

仅假设1和2，我认为这可以在O（n）中完成，尽管您需要向表中写入一个完整的索引以匹配假设3，因此不一定需要快速的O（n）。如果我们可以另外假设该表有其他优点，则可以在O（m log m）中执行任务。假设3是一个易于使用的好属性。有了一个很好的随机数生成器，它可以保证在连续生成m个数时不会重复，因此O（m）解决方案是可能的。

给定这三个假设，基本思想是生成介于1和n之间的m个唯一的随机数，然后从表中选择具有这些键的行。我现在没有mysql或任何更新，所以在伪代码中看起来像这样：

create table RandomKeys (RandomKey int) create table RandomKeysAttempt (RandomKey int)

-- generate m random keys between 1 and n for i = 1 to m insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys, -- with luck (and m much less than n), this won't be necessary while count(RandomKeys) < m NextAttempt = rand()*n + 1 if not exists (select * from RandomKeys where RandomKey = NextAttempt) insert RandomKeys select NextAttempt

-- get our random rows select * from RandomKeys r join table t ON r.RandomKey = t.UniqueKey 如果您真的担心效率，则可以考虑使用某种过程语言来生成随机密钥，并将结果插入数据库中，因为除SQL以外，几乎任何其他方法都可能在所需的循环和随机数生成方面更好。