数组最有效的乱数排列

super-tomato

作者：Super-Tomato

那么目前您会怎么写出乱数且不重复的排列呢？

如果是以一直循环函数的话，虽然是可以达到效果，但如果你要排列乱数很多就会造成计算量很大且花上很多时间。如果是在一个游戏上，应该有很多人会抱怨吧。

以数组的splice功能把数组乱数提取后储存在另外一个数组当中，这个还不错。在应付1000位的乱数排列中，本人的电脑测试只需要1979毫秒，代码如：

var myArray:Array = new Array();
for(var i=0; i<1000; i++) myArray.push(i);

var newArray:Array = new Array();
var timer = getTimer();  //开始计时

while(myArray.length > 0) {
newArray.push(myArray.splice(random(myArray.length), 1));  //使用splice把数组一个个的删除
}

trace(getTimer()-timer);  //计时结束并显示计算花费时间
trace(newArray);  //显示乱数排列

那么重点来了，在这里我来创个以数组中的sort函数来乱数排列。同样的以1000位的乱数排列只用了242毫秒，这也是我个人推荐使用的方法，好啦。。那么就看看是什么神奇代码吧

Array.prototype.randomize = function() {
this.sort(function(a, b) { return (random(2)) ? 1 : -1;});
}
var myArray:Array = new Array("我", "是", "超", "级", "番", "茄" );
myArray.randomize();
trace(myArray);

超乎意料的短吧，而重点是在 function(a, b) { return (random(2)) ? 1 : -1;}

看看flash提供的帮助文档中有提到在sort函数中增加函数，所带参数a和b是什么呢？ 那就是sort中会取得数组中两个数值，如：function(我, 是)。而我所回传的 1和 -1代表什么呢？

在文档中有说到

-1, if A should appear before B in the sorted sequence
0, if A equals B
1, if A should appear after B in the sorted sequence
-1代表A会排列在B前面，0代表A和B平等，1代表A排列在B后面。有了这样的一个解释，就可以联想到以这个方法调乱sort排列的次序而达到乱数排列的效果了

以下可以得到的测试时间以证明

Array.prototype.randomize = function() {
this.sort(function(a, b) { return (random(2)) ? 1 : -1;});
}
var myArray:Array = new Array();
for(var i=0; i<1000; i++) myArray.push(i);
var timer = getTimer();
myArray.randomize();
trace(getTimer()-timer);

super-tomato

另外一種更好的數組交換值的寫法

var myArray:Array = new Array();
for(var i=0; i<1000; i++) myArray.push(i);
var timer = getTimer();

for (var i=0;i<1000;i++) { //这里1000可大可小,决定混乱程度
    var x = random(1000);
    var y = random(1000);
    var t = myArray[x];
    myArray[x] = myArray[y];
    myArray[y] = t;
}

for(var a=0;a<1000;a++)
    trace(myArray[a]);

trace("所花时间："+(getTimer()-timer)+"ms");

[ 本帖最后由 super-tomato 于 27-5-2006 01:52 AM 编辑 ]

donynam

原帖由 super-tomato 于 27-5-2006 01:40 AM 发表
另外一種更好的數組交換值的寫法

var myArray:Array = new Array();
for(var i=0; i<1000; i++) myArray.push(i);
var timer = getTimer();

for (var i=0;i<1000;i++) { //这里1000可大可小,决定 ...

我也做了一个,作为测试用途，我使用了混合式的模式。请参考执行后的数据。

我的结论是：使用非交换、乱数生成的不重复阵列，其乱数范围(max-min)/阵列长度:最好小于5.88。因为只有小于这个数值才会有比较特出的表现。

var a = new Array();
trace ("测试 二种乱数生成性能: 乱数范围：0 ～ 9999, 阵列长度范围=50 ～ 5000");
trace ("/*********************************************/");
times=50;
for (i=0;i<100;i++){
        trace ("测试 " + (i+1) + " 乱数数量比：" + (5000/times) + " 乱数范围/阵列长度:" + 10000/times);       
        trace ("/*****************************************/");
    var timer = getTimer();
    a = _root.Get_unique_randomize(0, 9999, times,0);
    trace ("使用非阵列乱数生成 "+ "所花时间："+(getTimer()-timer)+"ms");

    timer = getTimer();
    a = _root.Get_unique_randomize(0, 9999, times,50000);       
    trace ("使用阵列乱数生成  "+ "所花时间："+(getTimer()-timer)+"ms");
    timer = getTimer();
    a = _root.Get_unique_randomize(0, 9999, times);       
    trace ("使用混合式数生成  "+ "所花时间："+(getTimer()-timer)+"ms");
        trace ("/*****************************************/");       
        times +=50;
}

function Get_unique_randomize(min:Number, max:Number, length_ran:Number , limit:Number) {
        // 返回一个不重复乱数的阵列。min, max 分别为最小，最大值，leng_ran是指阵列长短。
        var range:Number = max-min+1;
        var randomNum:Number;
        var i:Number = 0;
        var j:Number =0;
        var random_array:Array = new Array();
        var bias:Number =  0 - min;
        limit=(limit==undefined)?5.88:limit;
        if ((max-min)<1){
                return;
        }
        if ((max-min)/length_ran>=limit){ //根据实验值最优化值limit，使用非阵列、乱数插入方法
            do {
                    randomNum = Math.floor(Math.random()*range)+min;
                    random_array = _root.sort_ins_arr(random_array, randomNum);
            } while (random_array.length<length_ran);
        }
        else{ //使用阵列式交换方法
                for (j=0,i=min;j<length_ran;i++,j++){
            random_array[j]=i+ bias;
                }
                j=0
                do {
                    randomNum = Math.floor(Math.random()*range)+min;
                        ranbias = randomNum + bias;
                        if (ranbias<length_ran){
                            swap = random_array[j];
                random_array[j] = random_array[ranbias];
                            random_array[ranbias]=swap;
                                j++;
                        }
                }
                while(j<length_ran);
        }
        return random_array;
}
function sort_ins_arr(arrayobj:Array, valno:Number) {
        // 排序和插入乱数
        var front_pos:Number = 0;
        var rear_pos:Number = (arrayobj.length>0) ? arrayobj.length-1 : 0;
        var mid:Number;
        var tp:Number;
        do {
                // 二元搜寻法，英文称为binary search吧
                tp = rear_pos-front_pos;
                mid = ((tp%2)>0) ? ((tp+1)/2)-1 : tp/2;
                mid += front_pos;
                if (arrayobj[mid] == valno) {
                        return arrayobj;
                }
                if (front_pos == rear_pos) {
                        break;
                }
                if (arrayobj[mid]<valno) {
                        front_pos = mid+1;
                } else {
                        rear_pos = mid;
                }
        } while (true);
        arrayobj.push(valno);

        // *********************Sorting **************************
        // 去除注解后，就能排序阵列（小到大）
        //
        // if (arrayobj[mid]>valno){
        // arrayobj.splice(mid,0, valno);
        // }
        // else{
        // if (arrayobj.lengt < 1){
        // arrayobj[0]=valno;
        // }
        // else{
        // arrayobj.splice(mid+1,0, valno);
        // }
        // }
        // /*********************************************************

        return arrayobj;
}

[ 本帖最后由 donynam 于 2-6-2006 01:17 AM 编辑 ]

super-tomato

~_~" 你的部份也太複雜了吧﹐而且才開始測沒多久就當機。
這太耗計算量了~~~

donynam

原帖由 super-tomato 于 2-6-2006 12:45 PM 发表
~_~" 你的部份也太複雜了吧﹐而且才開始測沒多久就當機。
這太耗計算量了~~~

这是flash 8的保险装置所导致的。

程序执行，忙碌等待一段时间后，flash 8会判将这个程序判断为经陷入无穷循环的状态的程序，于是flash 8会要求用户，自行决定是否要中止这个程序。选择no跳过这些无聊的菜单。

当机 ？我使用p3 667 都没有事呢。不过，生产乱数是耗费很多系统资源的。耐性的等吧。

super-tomato

原帖由 donynam 于 2-6-2006 01:59 PM 发表


这是flash 8的保险装置所导致的。

程序执行，忙碌等待一段时间后，flash 8会判将这个程序判断为经陷入无穷循环的状态的程序，于是flash 8会要求用户，自行决定是否要中止这个程序。选择no跳过这些无聊的菜 ...

很可惜的是我公司只是舊款的celeron 1GB處理器和128mb的pc133記憶体。所以這樣的要求下頂多只能安裝Flash 7.2版本，


其實你的代碼並不難看，只是太長了，對這裡學習的人沒什麽耐性看完。

主體上分爲範圍性亂數及數組亂數兩種。範圍性的是控制 random 的亂數範圍，數組性的就和我2樓貼的方法一樣。

對於你的 sort_ins_arr 我覺得沒啥必要，既然都是屬於亂數抽取的數字，就沒什麽意義再進行多一次的排列。
如果是從小到大排列，直接在do..while後使用sort函數會來的快

donynam

原帖由 super-tomato 于 3-6-2006 03:55 AM 发表
很可惜的是我公司只是舊款的celeron 1GB處理器和128mb的pc133記憶体。所以這樣的要求下頂多只能安裝Flash 7.2版本，

其實你的代碼並不難看，只是太長了，對這裡學習的人沒什麽耐性看完。

主體上分爲 ...

根据这个贴的主题是《数组最有效的排序》，我给的答案是不一定，根据不同情况，有不同的结果。为此，必须有数据作证明。所以，目的我已经将说过了，这只是作为测试用途的程序而已。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

如果要直接调用，请使用Get_unique_randomize(var min:Number,var max:Number, var arrayLength:Number);

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

sort_ins_arr(random_array, randomNum)，在上述那个程序主要是作为搜寻，然后插入不重复的乱数。

如果单独使用，则可以根据大小排序乱数（关闭注解）。

例如： 制造50个 1～100不重复的乱数，然后进行顺序排列。乱数的范围建议适用范围：(max - min)/制造个数 >2。则可以将50个 1～100的乱数根据顺序排序好。

没有了sort_ins_arr 在使用非阵列交换方法的时候根本就不能知道某个乱数是否有重复。

为何要自己写sort_ins_arr ? 主要是为了优化排序。我不清楚sort函数的内部运算方法，所以不敢使用。另外，根据比较的对象，排序是没有必要的。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
根据你的《數組交換值》，我也得出一个结论，那就是当用户要制造的乱数范围（min，max）远远大于乱数的数目，如果要最有效的混乱程度（每个阵列单位都要进行交换），则会造成数据交换量大增，减低运算速度。

[ 本帖最后由 donynam 于 4-6-2006 12:18 PM 编辑 ]

super-tomato

抱歉，沒去注意你sort_ins_arr這點。
sort函數中的執行就像陣列交換法一樣，是讓 a 和 b 兩個值前後交換或保持

donynam

原帖由 super-tomato 于 4-6-2006 08:09 AM 发表
抱歉，沒去注意你sort_ins_arr這點。
sort函數中的執行就像陣列交換法一樣，是讓 a 和 b 兩個值前後交換或保持

泡泡排序法（bubble sort），是一种比较缓慢的排序方法。

super-tomato

原帖由 donynam 于 4-6-2006 12:22 PM 发表


泡泡排序法（bubble sort），是一种比较缓慢的排序方法。

所以才貼在二樓﹐其實陣列對調的方式和bubble沒差太多﹐只是循環次數的關係

donynam

原帖由 super-tomato 于 6-6-2006 01:38 PM 发表

所以才貼在二樓﹐其實陣列對調的方式和bubble沒差太多﹐只是循環次數的關係

bubble sort 与阵列交换方式有根本的差别，不能一概而论。

bubble sort 的最坏的循环交换次数是 （n/2）*(min + max) 其中，min ~ max 一共有n项。所以平均是 （n/2*(min + max)）/2 = n/4*(min + max) <==最好的循环交换次数是0次。

而 阵列交换方式平均是n项 n 次（完整的交换）。

所以 n/4*(min + max) : n ==  （1/4 ）*（min + max） : 1

除了 min + max =4 的情况，否则有很大的差别。

另外，bubble sort的用意是将之排序，不是制造混乱。而阵列交换的方法是相反，制造混乱。

super-tomato

原帖由 donynam 于 6-6-2006 03:36 PM 发表


bubble sort 与阵列交换方式有根本的差别，不能一概而论。

bubble sort 的最坏的循环交换次数是 （n/2）*(min + max) 其中，min ~ max 一共有n项。所以平均是 （n/2*(min + max)）/2 = n/4*(min + max) &l ...

你還挺機車的，呵呵~~~ 不過我喜歡。

雖然意義上不相同，但在前後互換的邏輯還是需要
b = a+b;
a = b-a;
b = b-a;

donynam

原帖由 super-tomato 于 7-6-2006 03:18 AM 发表



你還挺機車的，呵呵~~~ 不過我喜歡。

雖然意義上不相同，但在前後互換的邏輯還是需要
b = a+b;
a = b-a;
b = b-a;

基于相互交换对于二者，也就是bubble sort 和 阵列交换是类似。所以没有比较的必要。二者其中一种共同点是交换数据。

方法如下：

x = x ^ y;  
y = x ^ y;
x = x ^ y;

不同点在于效率。所以有必要讨论交换的次数。