对于程序员来说，“随机”一词再熟悉不过了。一听到“随机”，我们脑海中便会出现一个单词“random”，和一系列的算法实现。而这，已经成为了程序员的条件反射！今天博主就跟大家聊一聊随机这件事。
想必很多朋友都考过驾照，在科目一中有一套交规题库，考试的时候系统会从这些题库中随机抽取100道题目作为考题（考过的人都知道这些题库又分成几大类，真正考试是从每一类中随机出N道题目，最后加在一起凑成100道，为了方便理解，我们姑且忽略这个分类），下面就来看看如何实现随机抽取考题这一算法。
二逼青年这样写：
function getRandomArray(list, total) {
var startIndex = Math.floor(Math.random() * (list.length - total));
return list.slice(startIndex, total);
}
直接从原数组中截取指定长度的数组，而截取的起始位置随机获得。代码只有2行，简洁明了，一气呵成。BUT，很明显这种写法有个致命缺陷——每次取出的数组都是固定顺序的，而不是完全自由组合的，所以这种写法是“伪随机”，不可取。
文艺青年这样写：
function getRandomArray(list, total) {
if (!list || !list.slice) return [];
if (list.length <= total) return list;
var result = [];
function rand() {
var index = Math.floor(Math.random() * list.length);
if (result.indexOf(list[index]) == -1) {
result.push(list[index]);
}
if (result.length < total) {
rand();
}
}
rand();
return result;
}
首先做了容错处理，避免非法调用时抛出异常。然后写了递归函数，每次从原数组随机获取不重复的一项，直到满足结果集长度。看上去已经完美实现了随机的需求，但总感觉有点别扭——靠递归排除重复可能性，感觉把希望寄托给了计算机，何时结束，它决定！如果遇到高并发的请求，CPU必定不堪重负！那么作为一名久经沙场的老司机，到底该如何优化这个算法呢？
分析最优解
要优化算法，首先就要找到可优化点在哪里。上面代码的痛点是靠递归排除重复项，以达到“不信找不到不重复项”的目的。如果我们在获取数据的时候就排除已经获取过的，是不是就不可能重复了呢？说到这里，相信很多人已经想到一个方案：每次获取之后，都把该项从原数组中移除，这样下次获取时就不可能得到重复的项了。但是做过性能测试的文艺青年又怎能不知道，更新原数组的代价比递归获取还要高！我擦，那还说个毛线！别急，既然不能移除，那我们就不移除就是了。我们的目的并不是移除已有数据，而是不获取已有数据。而“不获取”就有两种做法了，一种是移除，一种是替换掉。于是推出了以下做法：每次获取之后，把数组的最后一项放到被获取的这一项的位置上，然后下次随机的时候忽略最后一位。见下图：
第一次取值
替换之后，再次随机取值的时候只考虑a到f也就是random(0,5)就行了，再一次取值以次类推。
第二次取值
憋出大招
理清了这个思路，再回过头来优化这个函数，可以得出如下代码：
function getRandomArray(list, total) {
if (!list || !list.slice) return [];
if (list.length <= total) return list;
// 为了不改变原始数据，这里复制一份数组进行操作
var arr = list.slice(), result = [], len = list.length;
while (result.length < total) {
var index = Math.floor(Math.random() * (len - result.length));
result.push(arr[index]);
arr[index] = arr[len - result.length];
}
return result;
}
现在看起来是不是优雅多了？在实现需求的同时，没有浪费一丁点CPU资源。
作者：朱会震
网友评论