第 107 题：考虑到性能问题，如何快速从一个巨大的数组中随机获取部分元素

[yygmind]

比如有个数组有100K个元素，从中不重复随机选取10K个元素。

[momodiy]

每次抽奖过后将此次中奖对象从1000人的抽奖池中剔除:smile:

[chenyuwulu]

注意力放在两点： 1，一是针对结果，也就是最终结果，我只要100个随机的不重复的结果。那就只随机一个数字然后剔除掉随机范围，1000，999，998······一直到900为止。 2，二是针对随机数，毕竟是数组，index对应的就是0-999。我着重于随机出0-999内100个不同的随机数即可，随机一次，假设有十个重复，那就直接把90个没重复的剔除掉0-999范围，然后继续随机筛选，一直到有100个随机不同的数，也就是100个不同的index值，去1000个人员里面对应找出即可

[caiyongmin]

抽到重复的，再重新抽一遍？

[weiyunpeng]

var arr =[1,2,3,4...,1000];
var result = [];
var randomNum = 100;
for(var i = 0,i < randomNum,i++) {
   var luckyDog = Math.floor(Math.random() * (arr.length - i));
   result.push(arr[luckyDog]);
   arr[luckyDog] = arr[arr.length - i - 1];
}

[Yxiuchao]

由于随机从100K个数据中随机选取10k个数据，可采用统计学中随机采样点的选取进行随机选取，如在0-50之间生成五个随机数，然后依次将每个随机数进行加50进行取值，性能应该是最好的。

[KejieLiu]

取出来的从原数组删除

[syydsn3233]

取出来的从原数组删除

是我理解错了 不好意思

[ypf0088]

1. 用散列表实现快速读取新构建的数集合；
2. 使用一个计数变量记录成功取得的数个数；
3. 每次随机一个大数组的下标，根据下标访问大数组数据；
4. 如果数据存在于散列表当中，计数变量不变，继续3；
5. 如果数据不存在于散列表当中，计数变量加一，继续3；
6. 直到计数变量符合取数上限，终止程序；

散列表的键，我们可以使用使用大数组中取出的元素作为参数，值可以任意定义

比如

1. 使用计数值，当重复的时候计数值加一，这样可以很容易在程序结束的时候计算总共访问了多少个元素或者访问了多少个该元素的重复值
2. 使用1作为标志，可以判断是否重复
3. 等等等等

---

看了一下下面老哥们的答案，感觉自己题目理解有点问题，如果不需要保证新数组当中的元素相同的话，比较推荐洗牌算法

学到老，活到老啊

[sf-cake]

我倾向于扔到集合(Set)里面做，有就跳过，没有就add

const MAXIMUM = 10000;
const UID_COUNT = 100000

function random_with_set(){
    let set = new Set();

    while(true){
        if(set.size > MAXIMUM -1) break;

        let tmp = parseInt(Math.random()*UID_COUNT, 10);

        if(set.has(tmp)) continue;
        set.add(tmp);
    }

    return Array.from(set);
}

测试结果：

test for  [Function: random_with_set]
[
  67706, 44861, 99554, 39288, 84140, 96304, 36443,  7705,
  52521, 78064, 54533,  5780, 42397, 39978, 89235, 82979,
  61324, 85385,  2297, 77786, 94046,   779, 37874, 58484,
  78709, 12509, 34348, 41950, 14549, 35973, 32204, 83441,
  38018, 42602, 95219, 56953, 96524, 77563, 81911, 75977,
  79601, 32599, 15321, 21740, 14215, 82193,  5610,    67,
  56171, 14379,  9708, 66686, 68372, 69496, 47130, 81869,
  55936, 18510, 28982,  7162, 10714, 46688,  1225, 81495,
  77837, 26808, 93455, 14558, 90419, 56714, 87992,   934,
   4570, 80434,  9382, 44222, 88374, 91077, 28818, 98856,
  10863, 15012, 36221, 91611,  1542,  1686, 91814, 63263,
  15015, 47757, 55263, 22752, 20299, 64439, 51584, 18759,
  98067, 50649, 88712, 19375,
  ... 9900 more items
]
time used: : 17.830ms

我真是该死，忘记Array.form了……Orz……只会for for for.... 感谢 @habc0807 大佬的答案

[wingmeng]

const bigArr = new Array(1e5);  // 假设这就是那个 100K 的数组
const rdmIndex = new Set();  // 随机索引值
const sampleLen = 10e3;  // 抽样样本长度（10K 个）
const sampleArr = [];  // 抽样样本数组

while(rdmIndex.size < sampleLen) {
  rdmIndex.add(Math.random() * sampleLen >>> 0);
}

for (const index of rdmIndex){
  sampleArr.push(bigArr[index]);
}

console.log(sampleArr);

[630268501]

function(a,k){//a原数组，k取出多少个 var h = a.length;//a的个数 var l = Math.floor(Math.random()*h);//开始截取的位置 var n = a.concat(a).slice(l,l+k);//连接两个a防止越界 return n; } 随机连续截取一大段。 或者！！！！ 100k/10k=10; 第一个数随机1~10，第二个数随机11~20。。。。这样一个for就能轮遍所有 感觉这两个都不够随机。不过来活了，不能继续happy了

[habc0807]

1. 快速生成一个巨大数组 使用Array.from()
2. 通过Set特性，存放随机数，这里需要注意的是，没有就add，有就递归，总之要保证遍历的每一项都要找到一个唯一随机值，如果有就跳过就不能保证最后能获取到10k个值。

const randomNumHandle = (len, randomNum) => {
  // 快速生成一个有len个元素的巨大数组
  let originArr = Array.from({length: len}, (v, i) => i);
  let resultSet = new Set()

  // 快速选取randomNum个元素
  for(let i = 0; i < randomNum; i++) {
    addNum(resultSet, originArr)
  }

  function addNum () {
    let luckDog = Math.floor(Math.random() * (len - 1))

    if(!resultSet.has(originArr[luckDog])) {
      resultSet.add(originArr[luckDog])
    } else {
      addNum()
    }
  }

  return Array.from(resultSet)
}

// 比如有个数组有100K个元素，从中不重复随机选取10K个元素
console.log(randomNumHandle(100000, 10000))

运行结果

(10000) [27784, 66572, 27315, 40156, 96729, 58756, 30823, 23521, 29948, 30964, 93575, 8250, 84128, 56055, 50914, 22715, 51331, 76186, 9374, 62607, 69400, 56221, 88673, 58384, 75880, 15955, 83055, 80018, 58629, 87050, 58973, 27608, 10643, 3032, 46829, 54258, 60324, 23041, 86465, 34973, 97064, 99430, 66246, 4608, 29317, 2035, 97926, 31838, 98485, 24692, 66996, 91420, 12390, 27324, 44748, 45744, 76575, 12494, 75592, 70476, 24683, 74219, 14897, 83863, 88356, 35288, 38732, 1875, 50741, 39930, 11173, 23535, 45221, 96828, 42283, 41511, 81011, 63434, 4375, 40234, 16998, 37468, 68825, 7407, 27391, 47692, 21628, 42445, 43379, 10218, 55863, 91489, 34772, 64601, 77545, 4481, 91932, 65603, 69958, 81040, …]

default: 30.98388671875ms

[xiaokeqi]

        function random(n, data) {
		if (!Array.isArray(data)) return;
		let set = new Set();
		let result = [];
		while(set.size < n) {
			let index  = Math.floor(Math.random() * data.length);
			set.add(index);
		}
		for(let i of set.values()) {
			result.push(data[i]);
		}
		return result;
	}
	console.log(random(5, [1,2,3,4,5,6,66,7,7,4,4]));

通过set，保证键唯一

[McCarthey]

/* 洗牌算法：
    1.生成一个0 - arr.length 的随机数
    2.交换该随机数位置元素和数组的最后一个元素，并把该随机位置的元素放入结果数组
    3.生成一个0 - arr.length - 1 的随机数
    4.交换该随机数位置元素和数组的倒数第二个元素，并把该随机位置的元素放入结果数组
    依次类推，直至取完所需的10k个元素
*/

function shuffle(arr, size) {
    let result = []
    for (let i = 0; i < size; i++) {
        const randomIndex = Math.floor(Math.random() * (arr.length - i))
        const item = arr[randomIndex]
        result.push(item)
        arr[randomIndex] = arr[arr.length - 1 - i]
        arr[arr.length - 1 - i] = item
    }
    return result
}

[qieqie7]

const SOURCE_LEN = 100000
const source = Array.from({ length: SOURCE_LEN }).map((item, i) => i)

function getRadomList(source, length) {
  // 随机取 不重复 可以利用 Set 的唯一性
  const keys = new Set(); 
  while(keys.size < length) {
    const key = Math.floor(Math.random() * SOURCE_LEN)
    keys.add(key);
  } 
  
  const result = []
  keys.forEach(key => {
    result.push(source[key])
  })
  return result;
}

console.time('test')
const result = getRadomList(source, 10000)
console.timeEnd('test')

// 测试是否有重复的, 没有重复说明答案正确
console.log(result.length)
console.log(new Set(result).size)

测试结果:

node - v10.6.0
test: 5.655ms
10000
10000

test: 5.687ms
10000
10000

test: 5.486ms
10000
10000

test: 5.684ms
10000
10000

[sf-cake]

实测证明，洗牌快于Set~ =_,=|||

test for function::suffer with arguments ... [ 3252, 26151, 62862, 41576, 78027, 49667, 72554, 28920, 3931, 5089, 42416, 6663, 57409, 43891, 37621, 76562, 68576, 82444, 14227, 60142, 58861, 45890, 89757, 41398, 79880, 47871, 15552, 23282, 12574, 78653, 45897, 46186, 57753, 47477, 37897, 12170, 12459, 37793, 67623, 85922, 32175, 52649, 67331, 57852, 66067, 45648, 69680, 62216, 98656, 65916, 41960, 11410, 855, 55724, 70190, 58577, 11805, 22140, 94488, 22235, 91404, 14929, 11544, 70727, 80926, 10141, 9967, 1023, 90504, 39576, 77320, 59345, 25583, 80984, 1723, 91761, 61251, 86451, 59430, 63235, 394, 53217, 29645, 83118, 58816, 23041, 66637, 48380, 18246, 56727, 94380, 55886, 45057, 11059, 28742, 21987, 27008, 59010, 67861, 43576, ... 9900 more items ] time used: : 13.926ms test for function::random_with_set with arguments ... [ 3826, 4228, 25798, 84453, 36868, 62678, 94255, 86536, 62136, 74660, 74359, 60823, 18144, 44643, 18386, 70658, 74627, 92052, 23422, 47798, 92235, 83446, 9863, 9470, 4804, 55639, 6688, 18011, 75256, 13045, 32754, 14101, 26269, 88511, 15273, 59622, 43881, 40692, 30441, 69420, 95303, 81826, 79582, 41997, 18790, 92999, 77588, 51484, 10670, 39779, 22221, 13032, 15027, 35398, 62932, 6590, 96670, 50339, 68946, 32143, 50928, 19280, 16247, 94234, 76841, 13783, 49332, 44710, 261, 75845, 96938, 97283, 99935, 54099, 22718, 1204, 26741, 93996, 91302, 94998, 61860, 7628, 2923, 76075, 28312, 62089, 75737, 76048, 60593, 66047, 57590, 26244, 18521, 1408, 50868, 26136, 52547, 39886, 83679, 61565, ... 9900 more items ] time used: : 16.942ms

[weiyunpeng]

采用分治法，由于每一组只抽中一个，所以不存在重复的情况。

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < size; x++) {
        var start = x * Math.floor(array.length/size);
        var end = start + Math.floor(array.length/size);
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

[sunstdot]

采用分治法，空间换时间

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < Math.ceil(array.length / size); x++) {
        var start = x * size;
        var end = start + size;
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

嗯，我也比较同意这种算法，分治法减少了遍历次数

[weiweixuan]

      考虑到性能问题，如何快速从一个巨大的数组中随机获取部分元素 
        比如有个数组有100K个元素，从中不重复随机选取10K个元素。
      */
      // let arr = Array.from({ length: 100000 }, () => Math.random().toString(16))
      let arr = Array.from({ length: 100000 }, (item, index) => `a${index}`)
      console.log(arr)
      function getRandom(arr, num) {
        // 浅拷贝
        let arr_ = [...arr],
          arr_res = []
        for (let i = 0; i < num; i++) {
          let key = Math.floor(Math.random() * arr_.length)
          arr_res.push(arr_[key])
          arr_.splice(key, 1)
        }
        return arr_res
      }
      let res = getRandom(arr, 10000)
      console.log(res)

[EnergySUD]

            function search(len,num){
		let arr = Array.from({length:len}, (v,x) => { return Math.floor(Math.random() * x * len)});
		let start,end,obj={},max=0,newArr=[];
		
		start = new Date().getTime();
		
		while(true){
			let j = Math.floor(Math.random() * arr.length );
			if(!obj[arr[j]]){ obj[arr[j]] = arr[j];max++; }
		    if(max==num){break}
		}
		
		for (let i in obj){
                    newArr.push(obj[i]);
                }
		
		end = new Date().getTime();
		console.log(end-start);//20ms 左右
		
		console.log(arr,newArr)
	}
	search(100000,10000);

[abshawn]

const SOURCE_LEN = 100000 const TARGET_LEN = 10000

// 洗牌算法比较合适 let x={ length: SOURCE_LEN } const source = Array.from(x).map((item,i)=>i);

function shuffle(arr, size) { let result = [] for (let i = 0; i < size; i++) { const randomIndex = Math.floor(Math.random() * (arr.length - i)) const item = arr[randomIndex] result.push(item) arr[randomIndex] = arr[arr.length - 1 - i] arr[arr.length - 1 - i] = item } return result; }

var X=shuffle(source, TARGET_LEN); console.log(X);

[lwwen]

var len=data.length/100*10

for(var i=0;i<data.length;i++){

    if(result.length==len){
        break;  
    }
    if(result.indexOf(data[i])==-1){
        result.push(data[i]);   
    }
}

[lwwen]

采用分治法，空间换时间

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < Math.ceil(array.length / size); x++) {
        var start = x * size;
        var end = start + size;
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

哈？可以问一下你这个评论样式是怎么生成的吗

[lwwen]

var arr =[1,2,3,4...,1000];
var result = [];
var randomNum = 100;
for(var i = 0,i < randomNum,i++) {
   var luckyDog = Math.floor(Math.random() * (arr.length - i));
   result.push(arr[luckyDog]);
   arr[luckyDog] = arr[arr.length - i - 1];
}

可以问一下这个的思路是咋样的吗

[ghost2113]

`

function getRandomArrayfromBigArray(newLength, sourceLength) {
    var sourceArr = Array.from({length: sourceLength}, (item, i) => i);
    var newArr = [];
    var temp;
    var randomIndex;
    for(var i = 0; i<newLength; i++) {
        randomIndex = Math.floor(Math.random()*(sourceLength-i));
        temp = sourceArr[randomIndex]
        sourceArr.splice(randomIndex, 1).push(temp);
        newArr.push(temp)
    }
    return newArr;
}
getRandomArrayfromBigArray(100, 100000);

`

[WunGCQ]

单纯一个算法题目的话，根据 n = 100k 和 m = 10k 的大小，有可能会提前计算出所有答案，运算完之后重新shuffle的方式来减少每次调用的开销。比如同样的n，m=10 或 m=10k，对应反复调用 10000次和10次，可能m=10的情况下我可能倾向于提前计算结果（第一次调用时间稍长，后面直接返回结果，类似打表），m = 10k的情况下 也许就直接shuffle了；至于什么是最优解看测试结果吧。

如果放到真实环境中考虑（抽奖、游戏等），n和m的大小有可能是动态的，预计算的话会影响计算结果，导致实际概率与理论概率有偏差。另外还要考虑 arr n,和arr m存放在哪里（持久化、IO等），会有不同的思路吧。

[wingmeng]

 if(!resultSet.has(originArr[luckDog])) {
      resultSet.add(originArr[luckDog])
    }

@habc0807 Set 不需要判断是否存在重复元素，因为它本身就不会产生重复的元素，所以直接一直 add 操作就行了。

[weiyunpeng]

var arr =[1,2,3,4...,1000];
var result = [];
var randomNum = 100;
for(var i = 0,i < randomNum,i++) {
   var luckyDog = Math.floor(Math.random() * (arr.length - i));
   result.push(arr[luckyDog]);
   arr[luckyDog] = arr[arr.length - i - 1];
}

可以问一下这个的思路是咋样的吗

将抽中的放入结果数组里，并用原数组最后一个数替换这个被抽中的数

[lonycc]

蓄水池算法， 可保准随机性

[JKjing]

function GetNewArr(oldArr, newArrLength) { let newArr = []; let oldArrLength = arr.length; for (let i = 0; i < newArrLength; i++) { newArr.push(Math.floor(Math.random() * (oldArrLength - i))) } newArr.sort(); let previous = 0; for (let i = 0; i < newArrLength; i++) { if (newArr[i] <= previous) previous++; else previous = newArr[i] newArr[i] = oldArr[previous]; } return newArr; } 没测试，第一个for获取指定数量的随机数作为新数组的下标，sort和第二个for是处理获取到随机数会有重复的情况，当有重复时将当前下标进行++操作 在数据上，没有改变原数组，如果原数组中有重复数据，这里去到的数据页可能会有重复数据

[niexia]

采用分治法，由于每一组只抽中一个，所以不存在重复的情况

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < Math.ceil(array.length / size); x++) {
        var start = x * size;
        var end = start + size;
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

sliceArray 写反了？size是分组的数量，不是每组元素的数量。是不是改成这样调用

var newArray = sliceArray(arr, Math.floor(arr.length/randomNum));

但是这样如果不整除，就会导致最后一组元素数量和前面不一致，概率也就不一样。

[lishu97]

const bigArr = Array.from({length: 1e5}, (v, i) => i)
const resultArr = []; 
const keySet = new Set();
let count = 0;

console.time('耗时')
const index = 1e5 - 1;
do {
    const key = Math.floor(Math.random() * index);
    
    if(keySet[key] === undefined) {
        resultArr.push(bigArr[key]);
        keySet[key] = 1;
    }
    count++
} while(resultArr.length < 1e4)
console.timeEnd('耗时');
console.log(`次数：${count}`);

耗时：8ms 次数：10508 @ykst615 膜拜大佬

[qieqie7]

const bigArr = Array.from({length: 1e5}, (v, i) => i)
const resultArr = []; 
const keySet = new Set();
let count = 0;

console.time('耗时')
const index = 1e5 - 1;
do {
    const key = Math.floor(Math.random() * index);
    
    if(keySet[key] === undefined) {
        resultArr.push(bigArr[key]);
        keySet[key] = 1;
    }
    count++
} while(resultArr.length < 1e4)
console.timeEnd('耗时');
console.log(`次数：${count}`);

耗时：8ms 次数：10508 @ykst615 膜拜大佬

啊? 我觉得你的比我的好一点诶

[lishu97]

const bigArr = Array.from({length: 1e5}, (v, i) => i)
const resultArr = []; 
const keySet = new Set();
let count = 0;

console.time('耗时')
const index = 1e5 - 1;
do {
    const key = Math.floor(Math.random() * index);
    
    if(keySet[key] === undefined) {
        resultArr.push(bigArr[key]);
        keySet[key] = 1;
    }
    count++
} while(resultArr.length < 1e4)
console.timeEnd('耗时');
console.log(`次数：${count}`);

耗时：8ms 次数：10508 @ykst615 膜拜大佬

啊? 我觉得你的比我的好一点诶

你的性能比我的高

[weiyunpeng]

采用分治法，由于每一组只抽中一个，所以不存在重复的情况

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < size); x++) {
        var start = x * Math.floor(array.length/size);
        var end = start + Math.floor(array.length/size);
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

sliceArray 写反了？size是分组的数量，不是每组元素的数量。是不是改成这样调用

var newArray = sliceArray(arr, Math.floor(arr.length/randomNum));

但是这样如果不整除，就会导致最后一组元素数量和前面不一致，概率也就不一样。

需要抽randomNum个奖，所以size就是randomNum，这样能保证每组只抽中一个。 每组的数量是element.length。 至于

采用分治法，由于每一组只抽中一个，所以不存在重复的情况

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < Math.ceil(array.length / size); x++) {
        var start = x * size;
        var end = start + size;
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

sliceArray 写反了？size是分组的数量，不是每组元素的数量。是不是改成这样调用

var newArray = sliceArray(arr, Math.floor(arr.length/randomNum));

但是这样如果不整除，就会导致最后一组元素数量和前面不一致，概率也就不一样。

只适合整除并且抽中的数量少于等于总数量一般的情况。其他情况还是走全局抽奖那种方式。

[xiaojiexiaojie123]

var getRandomSingleNums = function (arr) { var n = arr.length / 10, randomSingleNums = []; while (n) { var ran = parseInt(Math.random() * n * 10); if (randomSingleNums.indexOf(ran) == -1) { randomSingleNums.push(ran); n--; } } return randomSingleNums.map(function (index) { return arr[index] }) } 本题的思路： 1、计算部分元素的数量n 2、取巨大数组中n个随机下标 3、返回n个随机元素

[luhaifeng666]

如果直接把这个数组new Set去重，然后再取随机的个数呢

[J-DuYa]

/**
* @param { Array } arr 原数组
* @param { Number } len 随机获取的数组长度
*/
export function arrRandom (arr = [], len = 0) {

  if (len > arr.length) throw new Error("参数有误，请核实参数")

  let result = new Set()

  while (true) {
    if (result.size > len - 1) break

    let num = arr[Math.floor(Math.random() * arr.length)]
    result.has(num) ? () => {} : result.add(num)
  }

  return [...result]
}

[HduSy]

利用Math.random() Array.sort() 原地随机打散原数组,然后线性取

const origin_count = 100 ** 3 //100k
const goal_count = 10 ** 3
const origin_arr = new Array(origin_count)
const goal_arr = new Array(goal_count)
for (let i = 0; i < origin_count; i++) {
    origin_arr[i] = i
}
origin_arr.sort(() => {
    return 0.5 - Math.random()
})
for (let i = 0; i < goal_count; i++) {
    goal_arr[i] = origin_arr[i]
}

[francecil]

按题意，应该是用洗牌算法 O(n)， 做下改动，当n足够大时，需要用蓄水池算法

function reservoir(n,m){
  // 假设数据为0~n-1,抽 m 个元素
  // 初始化池中数据为 0~m-1
  let ret = Array.from({length: m}, (v, i) => i);
  for(let i=m;i<n;i++){
    // 第i个元素有 m/i 概率替换ret中任一元素
   // 即 Math.random()*(i+1) <=m 表示命中
    if(Math.random()*(i+1)<=m){
      // 命中，选择ret一个元素进行替换
      let index = Math.floor(Math.random()*m)
      ret[index] = i
    }
  }
  return ret
}

[qiannianchong25]

这里假设100K个元素都不重复，因此，这种题实际考的就是洗牌算法。否则，可以考虑先用个Set，转化一下，在用洗牌算法来解决。

function shuffle(data,num){
  let result=[];
  while(num-->0){
    let length=data.length,
        // random=Math.random()*data.length|0;
        random=(Math.random()*1e6|0)%length;

    swap(data,random,length-1)
    result.push(data.pop())
  }
  return result
}
function swap(arr,i,j){
  [arr[i],arr[j]]=[arr[j],arr[i]]
}
data=Array.from({length:1e3},(v,i)=>i);
shuffle(data,1e2)

只是数据演示，我就只从1000个数据里面取了100个。

[qiannianchong25]

上面的代码会修改原始数据。所以改进了下

function shuffle(data,num){
  let result=[],
      length=data.length;
  while(length--,num-->0){
        // random=Math.random()*data.length|0;
    let random=(Math.random()*1e6|0)%length;
    swap(data,random,length-1)
    result.push(data[length-1])
  }
  return result
}
function swap(arr,i,j){
  [arr[i],arr[j]]=[arr[j],arr[i]]
}
data=Array.from({length:1e3},(v,i)=>i);
shuffle(data,1e2)

[0w0k]

Array(1000000).fill().map((v, i) => i).sort((a,b) => Math.random() - 0.5).splice(-100000)

[tongchuan]

let arr = Array.from({length:10000},(v,i)=>i+1) //创建一个数组 let arr2 = Array.from({length:100}) // 要获取的随机数组 arr2 = arr2.map((i)=>{ return arr.splice(parseInt(Math.random()*arr.length),1) //返回随机数,并去除已经放到随机数中的数 }) console.log(arr2) //打印结构

[zhiweiweii]

var arr =[1,2,3,4...,1000];
var result = [];
var randomNum = 100;
for(var i = 0,i < randomNum,i++) {
   var luckyDog = Math.floor(Math.random() * (arr.length - i));
   result.push(arr[luckyDog]);
   arr[luckyDog] = arr[arr.length - i - 1];
}

我认为对于100k的数据最好先把 arr.length用一个变量存起来，免得每一次去查找一次数组的长度，很浪费性能

[haixuxu]

对比了一下生成数组的速度。Array.from很慢

const size = 10000;
var arr = null;

console.time('testArray1');
for (var i = 0; i < 1000; i++) {
  arr = [...Array(size).keys()];
}
console.timeEnd('testArray1');
console.time('testArray11');
for (var i = 0; i < 1000; i++) {
  arr = [...new Uint8Array(size).keys()];
}
console.timeEnd('testArray11');

console.time('testArray2');
for (var i = 0; i < 1000; i++) {
  arr = Array.from({ length: size }, (v, i) => i);
}
console.timeEnd('testArray2');

console.time('testArray3');
for (var i = 0; i < 1000; i++) {
  arr = Array(size).map((v, i) => i);
}
console.timeEnd('testArray3');

console.time('testArray4');
for (var i = 0; i < 1000; i++) {
  arr = [...Array.from({ length: size }).keys()];
}
console.timeEnd('testArray4');

nodejs v10.16.3 output

testArray1: 66.075ms
testArray11: 62.283ms
testArray2: 1184.594ms
testArray3: 114.503ms
testArray4: 1147.381ms

chrome

VM143:8 testArray1: 422.568115234375ms
VM143:13 testArray11: 397.53076171875ms
VM143:19 testArray2: 1406.287841796875ms
VM143:25 testArray3: 58.39794921875ms
VM143:31 testArray4: 1707.709228515625ms

[haixuxu]

console.time('testArrayFrom'); var len = 10000; let abc = null; for (var i = 0; i < 1000; i++) { abc = Array.from({ length: len }); } console.timeEnd('testArrayFrom');

testArrayFrom: 1300.651123046875ms

[a82448186]

采用分治法，由于每一组只抽中一个，所以不存在重复的情况。

/*
* 用于将巨大的数组平均分成多个数组
* 比如：100k个数中抽取10k，每个被抽中的概率为1/10。那么可以均分成10k个数组，每组10个数抽中1 
* 个。以次类推，如果抽取1k个的话，每组100个抽中1个。
*/
function sliceArray(array, size) {
    var result = [];
    for (var x = 0; x < size; x++) {
        var start = x * Math.floor(array.length/size);
        var end = start + Math.floor(array.length/size);
        result.push(array.slice(start, end));
    }
    return result;
}

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
var newArr = sliceArray(arr,randomNum);
for (var i = 0; i<newArr.length;i++) {
  var element = newArr[i];
  var luckyDog = Math.floor(Math.random() * (element.length - 1));
  result.push(element[luckyDog]);
}

slice 也会 影响性能 直接取值不就好了

var arr =[1,2,3,4...,100k];
var result = [];
var randomNum = 10k;
for (var i = 0; i<randomNum;i++) {
   var luckyDog = Math.floor(Math.random() * (element.length - 1)+randomNum*10);
   result.push(element[luckyDog]);
}

[whosesmile]

我翻开尘封的书箱，找到编程珠玑(居然没当二手书卖掉)， 又复习了一遍 第12章 取样问题...

[lujin123]

将随机出来的数和数组末尾的值交换

[hanzc0106]

用洗牌算法, 比如从10个中取5个, [1,1,1,1,1,0,0,0,0,0], 洗牌后[1,1,0,0,1,0,1,1,0,0], 取1所在位置元素就可以

[alan1111]

[523451928]

function shuffle(arr, selectLength) {
  const copyArr = [...arr]
  let length = copyArr.length
  while (length) {
    const j = Math.ceil(Math.random() * length--);
    [copyArr[j], copyArr[length]] = [copyArr[length], copyArr[j]]
  }
  return copyArr.slice(0, selectLength)
}
const arr = []
for (let i = 0; i < 1000000; i++) {
  arr.push(i)
}
shuffle(arr, 10000)

[wabRul]

function getRandomK(n, k) {
  let arr = Array.from({ length: n }).map((v, i) => i)
  for (let i = n - 1; i >= n - k; i--) {
    let j = Math.floor(Math.random() * i)
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
  return arr.slice(n - k)
}

[DarthVaderrr]

//从N个连续数中随机取M个数
function getRandomArr(n, m) {
    const queque = [];
    const res = [];
    queque.push([0, n]);
    while (res.length < m) {
        let [start, end] = queque.shift();
        let randomNum = getRandomNumber(start, end);
        let splitor = randomNum;
        if (randomNum === start) {
            start = randomNum + 1;
            splitor = (start + end) >> 1;
        }
        if (randomNum === end) {
            end = randomNum - 1;
            splitor = (start + end) >> 1;
        }
        res.push(randomNum);
        // 下一个取数区间,将不再包含本轮产生的随机数
        if (start < splitor) queque.push([start, splitor - 1])
        if (end > splitor) queque.push([splitor + 1, end])
    }
    return res;
}

function getRandomNumber(start, end) {
    return Math.floor(Math.random() * (end - start + 1)) + start;
}

console.log(getRandomArr(1000, 10))

[Tobiasll]

内存计算可以使用洗牌算法，时间复杂度为 O (n)，n 为 limit 的抽取个数的大小，先随机获取索引，然后不断的和最后一个交换，然后缩短的范围，然后最后一个数的下标减去递增的 i，最后在截取最后一个数到数组的长度，拷贝出新的结果数组 `

List<Integer> list = new ArrayList<>();

for (int i = 0; i < 100000; i++) {
  list.add(i);
}
Random random = new Random();
int limit = 10000;
int count = 0;
for (int i = 0 ; i < list.size() - 1; i++) {
  int index = random.nextInt(list.size() - 1 - i);
  if (count++ == limit) {
    break;
  }
  Integer temp = list.get(index);
  list.set(index, list.get(list.size() - 1 - i));
  list.set(list.size() - 1 - i, temp);
}
List<Integer> result = list.subList(list.size() - limit, list.size());`

实际业务场景可以对数据库进行大数据量随机获取的时，可以先根据或者这张表的所有主键 id，然后在内存中坐 shuffle，在根据 shuffle 后的主键去根据主键索引获取对应的数据，或者使用 redis 去维护该表的主键，然后要随机获取的时候直接从 redis 中的 set 随机获取，再去根据主键索引去查库

[tbapman]

@Yxiuchao 按照该老哥的思路，0-50生成5个随机数，然后依次50向上累加

function solution() {
    console.time('solution')
    let hashSet = new Set();
    while (true) {

        if (hashSet.size > 4) {
            break;
        }
        const randomNum = Math.floor(Math.random() * 50);
        if (hashSet.has(randomNum)) {
            continue
        }
        hashSet.add(randomNum)
    }

    const res = []
    for (let i of hashSet) {
        for (let j = 0; j < 2000; j++) {
            i += 50
            res.push(i)
        }
    }
    console.timeEnd('solution')
    // console.log(res)
    // console.log(JSON.stringify(res))
    // console.log(Array.from(new Set(res)).length)
    // console.log(res.length)
}

solution()

ps:这种方法会有一个问题，就是假定要选取的数据都是连续的，因为直接加50，这个累加的数可能在原数组中不存在，这种方法更像是生成10000唯一的数 @Bedivere-Sun 参考这位老哥的方法

function solution() {
  const targetLength = 1e5;
  const originArr = Array.from({ length: targetLength }, (_, i) => i);
  const res = []
  const hashSet = new Set();
  while (true) {
    if (hashSet.size > 9999) {
      break;
    }
    const randomNum = Math.floor(Math.random() * targetLength);
    if (hashSet.has(randomNum)) {
      continue
    }
    hashSet.add(randomNum)
    res.push(originArr[randomNum])
  }
  
  console.log(res.length)
  console.log(Array.from(new Set(res)).length)
  // return res;
}

solution()

ps:这个方法不用考虑数据是否连续的问题

[sionnigjt]

//洗牌算法
function shuffle(arr, size) {
    let length = arr.length;
    for (let index = 0; index < size; index++) {
        //在0到arr.length-index中随机取值
        let randomIndex = Math.floor(Math.random() * (length - index))
        //交换1
        let temp = arr[randomIndex]
        arr[randomIndex] = arr[length - index - 1]
        arr[length - index - 1] = temp
        //交换2
        // arr[randomIndex] = arr[randomIndex] ^ arr[length - index - 1]
        // arr[length - index - 1] = arr[randomIndex] ^ arr[length - index - 1]
        // arr[randomIndex] = arr[randomIndex] ^ arr[length - index - 1]
    }
    //切片交换顺序后的数组
    return arr.slice(-size)
}
console.log(shuffle(Array.from({ length: 1000 }, (v, i) => i), 100));

[fenglizhu]

// 在data长度的数组中，随机取出num个不重复的数据
let randomResult = (data, num) => {
  console.time()
  let res = [];
  for (let i = 0; i < data.length; i++) {
    // 获取数组的下标
    let index = Math.floor(Math.random() * (data.length));
    if(res.length >= num) {
      break
    }
    res.push(data[index]);
    data.splice(index, 1); // 删除下标为index的数据
    i--
  }
  console.timeEnd() // 时间大概在34-37ms
  console.log(res);
}

let data = [], arr = new Array(100000);
for (let i = 0; i < arr.length; i++) {
  data.push(i)
}

randomResult(data, 10000);

[JKjing]

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。

[Lingdeqing]

将选中的元素和最后的元素进行交换，时间复杂度O(中奖人数)

function choujiang(all, n) {
    const result = []
    for (let i = 0; i < n; i++) {
        const random = Math.floor(Math.random() * (all.length - i))
        result.push(all[random])
        [all[random], all[all.length - 1 - i]] =
            [all[all.length - 1 - i], all[random]]
    }
    return result
}

[JKjing]

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。