(如承蒙转载,请保留本站链接 http://www.aslibra.com )

hack86在文章《关于随机打乱数组的深入研究》里面写了一个随机数组的方法。

我不太赞同,同时我希望我可以说明我的论证(学校教给我们要用数据说话 ^_^)
阿权在这里仅发表一个看法,希望有不同意见的可以给出你的论证,大家交流一下。
可以PM给我,或者到我网站留言也好啊 http://www.aslibra.com/

其实随机数组应该不需要这么麻烦,先简单说一下hack86文章里面的方法:
对于N个元素的数组A,先建立同样N个随机数的临时数组B,然后比较每个数字大小,排序索引数组C,再根据索引C重新编排A

首先,这个做法是可以的,可总感觉是在做重复的工作。
其二,你的排序对数字比较就运行了N^2次,实际上用冒泡法来做效率更高些,大概是1~(N-1)的加和次。
其三,我没看到hack86关于“对Array.sort()内部构造的猜测”是怎么样的猜测。我觉得Array.sort就是一个类似你对数组B的排序,估计是冒泡法排序,你是疑问它内部工作不正常?


下面,我们来看看Array.sort内部构造,同时比较一下冒泡法,也没啥特别的,测试一下就完事:

先看看冒泡法:
(最小的泡泡出现在最后)

var a_array = Array(21, 545, 154, 15, 845, 45, 568, 784);
function swap(i, j) {
a = a_array[i];
a_array[i] = a_array[j];
a_array[j] = a;
}
var len:Number = a_array.length;
for (var i:Number = 0; i<len-1; i++) {
for (var j:Number = 0; j<len-1; j++) {
if (a_array[j]<a_array[j+1]) {
swap(j, j+1);
}
}
}
trace(a_array);


845,784,568,545,154,45,21,15

下面看看array.sort
排序标准是:两个数一直交换,也就是返回1,看看有什么规律:


function random_me(a, b) {
return 1;
}
var a_array = Array(21, 545, 154, 15, 845, 45, 568, 784);
for (var i = 0; i<20; i++) {
a_array.sort(random_me);
trace(a_array);
}


引用
545,154,15,845,45,568,784,21
154,15,845,45,568,784,21,545
15,845,45,568,784,21,545,154
845,45,568,784,21,545,154,15
45,568,784,21,545,154,15,845
568,784,21,545,154,15,845,45
784,21,545,154,15,845,45,568
21,545,154,15,845,45,568,784
545,154,15,845,45,568,784,21
154,15,845,45,568,784,21,545
15,845,45,568,784,21,545,154
845,45,568,784,21,545,154,15
45,568,784,21,545,154,15,845
568,784,21,545,154,15,845,45
784,21,545,154,15,845,45,568
21,545,154,15,845,45,568,784
545,154,15,845,45,568,784,21
154,15,845,45,568,784,21,545
15,845,45,568,784,21,545,154
845,45,568,784,21,545,154,15


模仿一下,我们也来一样的做法,用冒泡法排序20次,看看有什么规律:

var a_array = Array(21, 545, 154, 15, 845, 45, 568, 784);
function swap(i, j) {
a = a_array[i];
a_array[i] = a_array[j];
a_array[j] = a;
}
var len:Number = a_array.length;
for (var m:Number = 0; m<20; m++) {
for (var i:Number = 0; i<len-1; i++) {
for (var j:Number = 0; j<len-1; j++) {
//直接换
if (true || a_array[j]<a_array[j+1]) {
swap(j, j+1);
}
}
}
trace(a_array);
}


引用
784,21,545,154,15,845,45,568
568,784,21,545,154,15,845,45
45,568,784,21,545,154,15,845
845,45,568,784,21,545,154,15
15,845,45,568,784,21,545,154
154,15,845,45,568,784,21,545
545,154,15,845,45,568,784,21
21,545,154,15,845,45,568,784
784,21,545,154,15,845,45,568
568,784,21,545,154,15,845,45
45,568,784,21,545,154,15,845
845,45,568,784,21,545,154,15
15,845,45,568,784,21,545,154
154,15,845,45,568,784,21,545
545,154,15,845,45,568,784,21
21,545,154,15,845,45,568,784
784,21,545,154,15,845,45,568
568,784,21,545,154,15,845,45
45,568,784,21,545,154,15,845
845,45,568,784,21,545,154,15


看见规律了没?

比较两个就知道了,就是冒泡法排序的痕迹,只是它的算法是倒着的,具体冒泡法是怎么的就不说了,形象来说就是一个泡泡一直浮上去,重的泡泡就沉下来 o(∩_∩)o...哈哈。
所以,array.sort就是一个冒泡法,hack86就不需要猜测了。
同时,冒泡法排序的算法也是最经典的了,效率不用怀疑。
所以,为什么要怀疑它的内部呢?更加不需要用N^2次的排序算法来代替array.sort

hack86说:“这几天看到网络上在讨论关于随机打乱数组的问题!发现很多朋友的都有自己的方法,但是否真正的随机了呢?这个问题的争议一直很大,我在总结后,以及对Array.sort()内部构造的猜测后发现,还是有很多不是太完美的地方,所以我经过思考还是写了一套关于自己的数组随机打乱的函数”

我觉得随机排序是很简单的事情,不必要想的那么复杂,也没有什么争议的,只有算法的优劣。
你的思路算是普通的也把问题复杂化,效率并不高,何不使用高效的算法?

对于“真正的随机”,我觉得真正的随机的含义并不是你随机1k次,必须每次都不一样。
realbobon说“这样产生的随机数不会有重复吗?要是重复了怎么办?”
既然随机,那就有这个可能性是两个数一样,只是几率很小,但并不影响使用。

下面看看算法上简便的例子:

function random_me(a, b) {
if (Math.random()>0.5) {
return 1;
} else {
return 0;
}
}
var a_array = Array(21, 545, 154, 15, 845, 45, 568, 784);
for (var i = 0; i<20; i++) {
a_array.sort(random_me);
trace(a_array);
}


很简单的原理,让array.sort进行操作,每次返回一个随机数,大于0.5就调换两个数。

我们比较一下效率看看:

function randomArray(arrLen) {
var rArr:Array = new Array(arrLen);
for (var i = 0; i<arrLen; i++) {
rArr[i] = Math.random();
}
return rArr;
}
function randomIndex(arrLen) {
var iArr:Array = new Array(arrLen);
var rArr = randomArray(arrLen);
for (var i = 0; i<arrLen; i++) {
iArr[i] = i;
var t = rArr[i];
for (var j = 0; j<arrLen; j++) {
if (rArr[j]<t) {
iArr[i] = j;
t = rArr[j];
}
}
delete t;
rArr[iArr[i]] = 1;
}
return iArr;
}
function randomSort(arr) {
arrLen = arr.length;
var tArr = new Array(arrLen);
var iArr = randomIndex(arrLen);
for (var i = 0; i<arrLen; i++) {
tArr[i] = arr[iArr[i]];
}
return tArr;
}
function random_me(a, b) {
if (Math.random()>0.5) {
return 1;
} else {
return 0;
}
}
//产生随机的数组,填充1000个随机数
var a_array:Array = new Array();
for (var i:Number = 0; i<1000; i++) {
a_array.push(Math.random());
}
//
//开始前一个算法
var my_date:Date = new Date();
var time1:Number = my_date.getTime();
randomSort(a_array);
var my_date:Date = new Date();
var time2:Number = my_date.getTime();
trace(time2-time1);
//
//开始后一个算法
var my_date:Date = new Date();
var time1:Number = my_date.getTime();
a_array.sort(random_me);
var my_date:Date = new Date();
var time2:Number = my_date.getTime();
trace(time2-time1);


我电脑的结果是:
1157
281


我的结论是:
1 array.sort效率是很高的,没有必要怀疑它,我建议使用它
2 随机是有一样的可能性,如果你觉得随机有问题,那就是Math.random的问题,要怀疑的本质也是它,相信它,那就相信随机的结果



原创内容如转载请注明:来自 阿权的书房
收藏本文到网摘
tyy Homepage Email
2007/11/12 18:40
angry
分页: 1/1 第一页 1 最后页
发表评论
AD
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML 打开UBB 打开表情 隐藏
昵称   密码   游客无需密码
网址   电邮   [注册]
               

 

阅读推荐

服务器相关推荐

开发相关推荐

应用软件推荐