关于生成随机顺序数列的思考

这篇文章源于群里某基佬的提问:如何生成不重复的随机顺序的N个数?

当时总结了一下有两个思路:

  1. 用for循环准备好有序数列 1,2,3 ... ,n-1,n。然后每次随机的从里面挑出来一个,塞到一个新的数列里面,重复N次。

  2. 用for循环准备好有序数列 1,2,3 ... ,n-1,n。然后每次随机地选择两个元素进行对调,重复N次。

那么这两种方案哪一种效率更高呢?

读者不妨考虑一下。

为了真实地考察这两种方案的运行效率,我编写了一段php脚本。

<?php
//思路1
$t1=getMillisecond(); //计时1
$n=1000;
$arr1=range(1,$n);
$arr2=[];
while(($len=count($arr1))>0){
    $ran=rand(1,$len); //随机下标
    
     //转移元素
    array_push($arr2,$arr1[$ran-1]);
    unset ($arr1[$ran-1]);
    
    //重新修正下标
    $arr1=array_values($arr1);
}
//dump($arr2);
$t2=getMillisecond(); //计时2

//思路2
$arr=range(1,$n);
for($i=0;$i<$n;$i++){
    $ran1=rand(0,$n-1); //随机下标1
    $ran2=rand(0,$n-1); //随机下标2
    
    //对换元素
    $tmp=$arr[$ran1];
    $arr[$ran1]=$arr[$ran2];
    $arr[$ran2]=$arr[$ran1];
}
//dump($arr);
$t3=getMillisecond(); //计时3

dump([$t2-$t1,$t3-$t2]);

我在两种随机数列生成代码之间加入了很简单的计时器来记录运行时间,运行结果(n=1000)如下:
第一种方案平均耗时:130ms
第一种方案平均耗时:40ms

在我的设想中,第二种方案省去了重新建立数组索引或者放置标记的时间,同时在逻辑上容易理解,实现起来比较容易,是应该快一点的,但是没想到快了近3倍!

看来以后生成随机数列就用对调大法啦~