Javascript数组,排序和分支预言
编辑在花了几个小时的时间和@pst工作后,事实证明这个问题完全不同。
在代码中,你可以看到我使用了“+ new Date()”的时间戳快捷键。 这会像标准的“new Date()。getTime()”一样返回一个时间戳。
但是,与数学运算(+, - ,/)一起使用时,+ new Date()表现得非常非常糟糕。 尽管'start'变量的typeof()表示'数字',但是发生了一些让它变得流血缓慢的事情。 当使用标准的getTime()方法时,执行定时减法时不会有性能损失。
看看这个jsperf详细说明了这个问题,http://jsperf.com/new-date-timing。
关于@ pst的非常详细的回答以及我为复制链接问题所做的努力,请将他的回答作为该问题的标准答案。
我将改变这个问题的标题,以准确反映@ pst的答案和我的原意,但会留下原题和问题供将来参考。
新问题
JavaScript数组是否利用随机排序和未排序数据数组上的分支预测?
请参阅下面的@ pst的答案。
下面的原始标题和问题
标题:数组迭代在相同数据上的时间长度为2x
我之前正在考虑这个问题,为什么处理排序数组比排序数组更快?并且想要尝试在javascript中设置相同的测试。
这导致我出乎意料。 在下面的小提琴中链接的测试中,只需使用相同的代码迭代随机生成的数字值的相同阵列就会导致响应时间大不相同。
我已经在Chrome,Safari,Firefox和node.js中对此进行了测试。
在Chrome&node中,第一次迭代比第二次迭代快。 在Safari和Firefox中,第一次迭代比第二次迭代慢。
这是小提琴,http://jsfiddle.net/9QbWB/6/
在关联的小提琴中,我禁用了排序(认为这本来就是问题,但事实并非如此)。 对数据进行排序使得循环更长。
我已经仔细阅读了代码,以确保删除了可能影响结果的任何内容。 我觉得自己就像是一组特别的科学家宣布FTL中微子,在我的实验中我找不到任何问题,数据也是意外的。
在下面的代码中,像setTimeout,jQuery DOM可视化等一些东西用于在jsfiddle.net中直观地显示数据。 核心功能是一样的。
//javascript test of https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
setTimeout(function(){
var unsorted_list = $('#unsorted'),
sorted_list = $('#sorted');
var length = 32768,
data = [];
for(var i=0; i<length; i++){
data[i] = Math.floor( Math.random()*256);
}
var test = function(){
var sum = 0,
start = +new Date();
for(var i=0; i<1000; i++){
for(var c=0; c<length; c++){
if( data[c] >= 128 ){
//sum += data[c];
}
}
}
return +new Date() - start;
}
//Unsorted
var results = 0;
for( var i=0; i<10; i++){
var x = test();
console.log(x);
unsorted_list.append('<div>'+x+'</div>');
results += x;
}
unsorted_list.append('<div>Final:'+(results/10)+'</div>');
console.log( 'Unsorted: ', results/10 );
//Sort array
//data.sort();
//Sorted
var results = 0;
for( var i=0; i<10; i++){
var x = test();
console.log(x);
sorted_list.append('<div>'+x+'</div>');
results += x;
}
sorted_list.append('<div>Final:'+(results/10)+'</div>');
console.log( 'Sorted: ', results/10 );
},5000);
(显然这个答案没有解答这个问题 - 由于相关原因留在这里。)
这里是我的jsperf案例 - http://jsperf.com/sorted-loop/2 - 也许足够的东西将显示更多的浏览器。 我还包含了一个仅使用逐位操作的测试用例,从链接的文章中获取(并且我没有验证JS中的有效性)。
结论:表现似乎与分支预测有关。
不使用条件的“+ bitwise”测试对在所有主要浏览器运行中的速度(对于同一浏览器而言)是相同的。 (Chrome比FF快,比按位操作的IE要快;请参阅其他SO帖子。)
使用条件的“+ cond”测试对会受到很大影响,排序后的数据非常受欢迎。 如果分支预测是一个因素,这是预期的结果。