查看: 1817|回复: 12
|
数组最有效的乱数排列
[复制链接]
|
|
作者: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); |
|
|
|
|
|
|
|
楼主 |
发表于 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可大可小,决定混乱程度
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 编辑 ] |
|
|
|
|
|
|
|
发表于 1-6-2006 07:28 PM
|
显示全部楼层
原帖由 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 编辑 ] |
|
|
|
|
|
|
|
楼主 |
发表于 2-6-2006 12:45 PM
|
显示全部楼层
~_~" 你的部份也太複雜了吧﹐而且才開始測沒多久就當機。
這太耗計算量了~~~ |
|
|
|
|
|
|
|
发表于 2-6-2006 01:59 PM
|
显示全部楼层
原帖由 super-tomato 于 2-6-2006 12:45 PM 发表
~_~" 你的部份也太複雜了吧﹐而且才開始測沒多久就當機。
這太耗計算量了~~~
这是flash 8的保险装置所导致的。
程序执行,忙碌等待一段时间后,flash 8会判将这个程序判断为经陷入无穷循环的状态的程序,于是flash 8会要求用户,自行决定是否要中止这个程序。选择no跳过这些无聊的菜单。
当机 ?我使用p3 667 都没有事呢。不过,生产乱数是耗费很多系统资源的。耐性的等吧。 |
|
|
|
|
|
|
|
楼主 |
发表于 3-6-2006 03:55 AM
|
显示全部楼层
原帖由 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函數會來的快 |
|
|
|
|
|
|
|
发表于 3-6-2006 11:13 PM
|
显示全部楼层
原帖由 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 编辑 ] |
|
|
|
|
|
|
|
楼主 |
发表于 4-6-2006 08:09 AM
|
显示全部楼层
抱歉,沒去注意你sort_ins_arr這點。
sort函數中的執行就像陣列交換法一樣,是讓 a 和 b 兩個值前後交換或保持 |
|
|
|
|
|
|
|
发表于 4-6-2006 12:22 PM
|
显示全部楼层
原帖由 super-tomato 于 4-6-2006 08:09 AM 发表
抱歉,沒去注意你sort_ins_arr這點。
sort函數中的執行就像陣列交換法一樣,是讓 a 和 b 兩個值前後交換或保持
泡泡排序法(bubble sort),是一种比较缓慢的排序方法。 |
|
|
|
|
|
|
|
楼主 |
发表于 6-6-2006 01:38 PM
|
显示全部楼层
原帖由 donynam 于 4-6-2006 12:22 PM 发表
泡泡排序法(bubble sort),是一种比较缓慢的排序方法。
所以才貼在二樓﹐其實陣列對調的方式和bubble沒差太多﹐只是循環次數的關係 |
|
|
|
|
|
|
|
发表于 6-6-2006 03:36 PM
|
显示全部楼层
原帖由 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的用意是将之排序,不是制造混乱。而阵列交换的方法是相反,制造混乱。 |
|
|
|
|
|
|
|
楼主 |
发表于 7-6-2006 03:18 AM
|
显示全部楼层
原帖由 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; |
|
|
|
|
|
|
|
发表于 7-6-2006 10:46 AM
|
显示全部楼层
原帖由 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;
不同点在于效率。所以有必要讨论交换的次数。 |
|
|
|
|
|
|
| |
本周最热论坛帖子
|