Hatena::Groupjavascript

JavaScriptで遊ぶよ

 | 

2009-10-17

min,maxは一回でやるのがいいか

16:13

javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=new Date;
var min=null;
var max=null;
for(var i=0,l=a.length;i<l;i++){
  p=a[i];
  min=(min===null||p<min)?p:min;
  max=(max===null||p>max)?p:max;
}
alert(new Date-t);
Opera 250ms
Chromium 7ms
Firefox 10ms
Safari 7ms
javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=new Date;
var ns=[];
for(var i=0,l=a.length;i<l;i++){
  ns.push(a[i]);
}
var min=Math.min.apply(null,ns);
var max=Math.max.apply(null,ns);
alert(new Date-t);
Opera 219ms
Chromium 20ms
Firefox 16ms
Safari 7ms

JIT だと誤差みたいなもんなので、Opera にあわせて後者を使うとしよう。


Opera で遅いのは push

javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=new Date;
var ns=[];
for(var i=0,l=a.length;i<l;i++){
  ns[i]=a[i];
}
var min=Math.min.apply(null,ns);
var max=Math.max.apply(null,ns);
alert(new Date-t);

だと Opera で 166ms ぐらい。JIT なブラウザではやっぱり誤差みたいなもん。


こっちもいいかも

javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=new Date;
for(var i=1,l=a.length,min=a[0],max=a[0];i<l;i++){
  p=a[i];
  if(p<min)min=p;
  if(p>max)max=p;
}
alert(new Date-t);

170ms ぐらい。


コメントいただきました

javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=+new Date;
var i = a.length, min = a[0], max = a[0], p;
while(--i){
  p = a[i];
  if (p < min){
    min = p;
  } else if (p > max){
    max = p;
  }
}
alert(new Date-t);

140ms ぐらい。

while (--i) が速いってのは知識としては知っていてもなかなか使いませんね。

Math.random() がゼロにならないと仮定するなら (今やってる計算では p は数値ではなくて配列なので)

javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=+new Date;
var i = a.length, min = a[0], max = a[0], p;
while(p=a[--i]){
  if (p < min) min = p;
  else if (p > max) max = p;
}
alert(new Date-t);

みたいにすると 126ms ぐらいでした。

os0xos0x2009/10/18 17:47この条件で最適化するなら、forではなくwhile、minとmaxは同時には成立しないってあたりでしょうか。
javascript:
var a=[];
for(var i=0;i<100000;i++)a.push(Math.random());
var t=+new Date;
var i = a.length, min = a[0], max = a[0], p;
while(--i){
p = a[i];
if (p < min){
min = p;
} else if (p > max){
max = p;
}
}
alert(new Date-t);

配列に抜けがない前提で、while((p = a[i++])) とかも考えたんですが、Math,random()は0になりえるので、undef=void 0;while((p = a[i++]) !== undef)とかってしないと行けなくて上のと誤差レベルっぽい感じでした。

トラックバック - http://javascript.g.hatena.ne.jp/edvakf/20091017
 |