网络期权造就多少富翁
夜景拍摄
（如承蒙转载，请保留本站链接 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内部构造，同时比较一下冒泡法，也没啥特别的，测试一下就完事：
先看看冒泡法：
（最小的泡泡出现在最后）
845,784,568,545,154,45,21,15
下面看看array.sort
排序标准是：两个数一直交换，也就是返回1，看看有什么规律：
模仿一下，我们也来一样的做法，用冒泡法排序20次，看看有什么规律：
看见规律了没？
比较两个就知道了，就是冒泡法排序的痕迹，只是它的算法是倒着的，具体冒泡法是怎么的就不说了，形象来说就是一个泡泡一直浮上去，重的泡泡就沉下来 o(∩_∩)o...哈哈。
所以，array.sort就是一个冒泡法，hack86就不需要猜测了。
同时，冒泡法排序的算法也是最经典的了，效率不用怀疑。
所以，为什么要怀疑它的内部呢？更加不需要用N^2次的排序算法来代替array.sort
hack86说：“这几天看到网络上在讨论关于随机打乱数组的问题!发现很多朋友的都有自己的方法,但是否真正的随机了呢?这个问题的争议一直很大,我在总结后,以及对Array.sort()内部构造的猜测后发现,还是有很多不是太完美的地方,所以我经过思考还是写了一套关于自己的数组随机打乱的函数”
我觉得随机排序是很简单的事情，不必要想的那么复杂，也没有什么争议的，只有算法的优劣。
你的思路算是普通的也把问题复杂化，效率并不高，何不使用高效的算法？
对于“真正的随机”，我觉得真正的随机的含义并不是你随机1k次，必须每次都不一样。
realbobon说“这样产生的随机数不会有重复吗？要是重复了怎么办？”
既然随机，那就有这个可能性是两个数一样，只是几率很小，但并不影响使用。
下面看看算法上简便的例子：
很简单的原理，让array.sort进行操作，每次返回一个随机数，大于0.5就调换两个数。
我们比较一下效率看看：
我电脑的结果是：
1157
281
我的结论是：
1 array.sort效率是很高的，没有必要怀疑它，我建议使用它
2 随机是有一样的可能性，如果你觉得随机有问题，那就是Math.random的问题，要怀疑的本质也是它，相信它，那就相信随机的结果
原创内容如转载请注明：来自 阿权的书房
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);
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);
}
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
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);
}
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
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);
}
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);
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 
2007/11/12 18:40
分页： 1/1 
1 
1
