Hatena::Groupjavascript

JavaScriptで遊ぶよ

 | 

2009-01-27

pushとjoin

07:49

function concat_op(s, n) {
  var r = '';
  for (var i = n; --i >= 0;) {
    r += s;
  }
  return r;
}
function join(s, n) {
  var r = []; for (var i = n; --i >= 0;) {
    r.push(s);
  }
  return r.join('');
}

この違い。


まず、

function join(s, n) {
  var r = []; for (var i = n; --i >= 0;) {
    r[r.length] = s;
  }
  return r.join('');
}

こうすることによって Firefox 3.0.5 と Safari 3.2.1 では差が逆転する。Opera はちょっとだけ差が縮まる。

理由は、プリミティブの操作は関数呼び出しより速いため。

javascript:(function(s,n,a,t){t=new Date().getTime();
for(;--n>=0;)a.push(s);
alert(new Date().getTime()-t)})('0123456789',1000000,[])

Firefox 3.0.5 : 144ms

Safari 3.2.1 : 251ms

Opera 9.63 : 1035ms

javascript:(function(s,n,a,t){t=new Date().getTime();
for(;--n>=0;)a[a.length]=s;
alert(new Date().getTime()-t)})('0123456789',1000000,[])

Firefox 3.0.5 : 109ms

Safari 3.2.1 : 115ms

Opera 9.63 : 356ms

Opera 10 alpha でも同じ結果。

Opera の3倍は酷いけど、Safari と Firefox は100万回でこの差だから気にするほどでもなさそう。


javascript:(function(s,n,a,t){
for(;--n>=0;)a[a.length]=s;
t=new Date().getTime();
a.join('');
alert(new Date().getTime()-t)})('0123456789',1000000,[])

Firefox 3.0.5 : 254ms

Safari 3.2.1 : 503ms

Opera 9.63 : 905ms

配列を経由する方法がそこまで速くないのはむしろ join の遅さに起因しているらしい。


以下追記。

こういうの思いついた。

function recursive(s,n){
  var q = '';
  while(n){
    if(n%2) q += s;
    s += s;
    n >>= 1;
  }
  return q;
}

alert(recursive("0123456789",131071).length)
//-> 1310710

var t=new Date().getTime();
recursive("0123456789",131071);
alert(new Date().getTime()-t);

プリミティブ演算のみ。

Opera だと 20ms ぐらい。

使用できる n の最大値は 1073741823 かな?

さらに追記。

おもしろかったので Data URI 化。

data:text/html;charset=utf-8;base64,PGh0bWw%2BDQo8aGVhZD4NCiAgPG1ldGEgaHR0cC1lcXVpdj0iQ29udGVudC1UeXBlIiBjb250ZW50PSJ0ZXh0L2h0bWw7IGNoYXJzZXQ9VVRGLTgiIC8%2BDQogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4NCnZhciBfZXZhbCA9IGZ1bmN0aW9uKCkgeyB3aXRoKGFyZ3VtZW50c1swXSkgeyByZXR1cm4gZXZhbChhcmd1bWVudHNbMV0pOyB9IH07DQoNCnZhciBwcm9jZXNzX3RlbXBsYXRlID0gZnVuY3Rpb24odHBsLCBoZGxyKSB7DQogIHZhciBzID0gMCwgYnJhY2VfZGVwdGggPSAwLCBhbHRfYnVmID0gbnVsbDsNCiAgdmFyIGJ1ZiA9IFtdLCBidWZfc3RhY2sgPSBbXTsNCiAgdmFyIGlfZiA9IHsNCiAgICBzYXZlX2J1ZmZlcjogZnVuY3Rpb24oeCkgeyBidWZfc3RhY2sucHVzaChidWYsIHR5cGVvZiB4ID09IHVuZGVmaW5lZCA%2FIG51bGw6IHgpOyBidWYgPSBbXTsgfSwNCiAgICBnZXRfYnVmZmVyOiBmdW5jdGlvbigpIHsgcmV0dXJuIGJ1ZjsgfSwNCiAgICByZXN0b3JlX2J1ZmZlcjogZnVuY3Rpb24oKSB7IHZhciByID0gYnVmX3N0YWNrLnBvcCgpOyBidWYgPSBidWZfc3RhY2sucG9wKCk7IHJldHVybiByOyB9LA0KICAgIGFwcGVuZDogZnVuY3Rpb24oX2J1ZikgeyBidWYucHVzaChfYnVmLmpvaW4oJycpKTsgfQ0KICB9Ow0KICBmb3IgKHZhciBnLCByID0gLyg%2FOlteJXt9XXwlKD8hWyV7XSkpK3xbe31dfCVce3wlJShbX2EtekEtWl1bX2EtekEtWjAtOS1dKikoPzpccypcKFxzKihbXildKilccypcKSk%2FKD86WyBcdF0qKD86XHJ8XG58XHJcbikpPy9nOw0KICAgICAgIChnID0gci5leGVjKHRwbCkpOykgew0KICAgIHN3aXRjaCAocykgew0KICAgIGNhc2UgMDoNCiAgICAgIGlmIChnWzBdID09ICcleycpIHsNCiAgICAgICAgYnJlYWNlX2RlcHRoID0gMDsNCiAgICAgICAgYWx0X2J1ZiA9IFtdOw0KICAgICAgICBzID0gMTsNCiAgICAgIH0gZWxzZSBpZiAoZ1swXS5zdWJzdHIoMCwgMikgPT0gJyUlJykgew0KICAgICAgICBoZGxyLmhhbmRsZV90YWcoaV9mLCBnWzFdLCBnWzJdKTsNCiAgICAgIH0gZWxzZSB7DQogICAgICAgIGJ1Zi5wdXNoKGdbMF0pOw0KICAgICAgfQ0KICAgICAgYnJlYWs7DQogICAgY2FzZSAxOg0KICAgICAgaWYgKGdbMF0gPT0gJ30nKSB7DQogICAgICAgIC0tYnJhY2VfZGVwdGg7DQogICAgICAgIGlmIChicmFjZV9kZXB0aCA8IDApIHsNCiAgICAgICAgICBzID0gMDsNCiAgICAgICAgICAoZnVuY3Rpb24oXyl7IGJ1Zi5wdXNoKHt0b1N0cmluZzogZnVuY3Rpb24oKXsgcmV0dXJuIF9ldmFsKGhkbHIsIF8uam9pbignJykpOyB9fSk7IH0pKGFsdF9idWYpOw0KICAgICAgICB9IGVsc2Ugew0KICAgICAgICAgIGFsdF9idWYucHVzaChnWzBdKTsNCiAgICAgICAgfQ0KICAgICAgfSBlbHNlIGlmIChnWzBdID09ICd7Jykgew0KICAgICAgICArK2JyYWNlX2RlcHRoOw0KICAgICAgICBhbHRfYnVmLnB1c2goZ1swXSk7DQogICAgICB9IGVsc2UgaWYgKGdbMF0uY2hhckF0KDApID09ICclJykgew0KICAgICAgICB0aHJvdyB7IG1lc3NhZ2U6ICdTeW50YXggZXJyb3InIH07DQogICAgICB9IGVsc2Ugew0KICAgICAgICBhbHRfYnVmLnB1c2goZ1swXSk7DQogICAgICB9DQogICAgICBicmVhazsNCiAgICB9DQogIH0NCiAgcmV0dXJuIGJ1Zi5qb2luKCcnKTsNCn07DQogIDwvc2NyaXB0Pg0KICA8c2NyaXB0IHR5cGU9InRleHQvamF2YXNjcmlwdC10ZW1wbGF0ZSIgaWQ9InRlbXBsYXRlMSI%2BDQp7DQogIHZhciBjID0gJXtyZXBlYXQoJ3MnLCBubikuam9pbignICsgJyl9LCByID0gW107DQogIHdoaWxlICgobiAtPSAle25ufSkgPj0gMCkNCiAgICByLnB1c2goYyk7DQogIG4gKz0gJXtubn07DQogIHN3aXRjaCAobikgew0KJSVyZXBlYXQoMSwgbm4gLSAxLCBpKQ0KICBjYXNlICV7aX06DQogICAgci5wdXNoKCV7cmVwZWF0KCdzJywgaSkuam9pbignICsgJyl9KTsgDQogICAgYnJlYWs7DQolJWVuZHJlcGVhdA0KICB9DQogIHJldHVybiByLmpvaW4oJycpOw0KfQ0KICA8L3NjcmlwdD4NCiAgPHNjcmlwdCB0eXBlPSJ0ZXh0L2phdmFzY3JpcHQtdGVtcGxhdGUiIGlkPSJ0ZW1wbGF0ZTIiPg0Kew0KICB2YXIgYyA9ICV7cmVwZWF0KCdzJywgbm4pLmpvaW4oJyArICcpfSwgciA9ICcnOw0KICB3aGlsZSAoKG4gLT0gJXtubn0pID49IDApDQogICAgciArPSBjOw0KICBuICs9ICV7bm59Ow0KICBzd2l0Y2ggKG4pIHsNCiUlcmVwZWF0KDEsIG5uIC0gMSwgaSkNCiAgY2FzZSAle2l9Og0KICAgIHIgKz0gJXtyZXBlYXQoJ3MnLCBpKS5qb2luKCcgKyAnKX07IA0KICAgIGJyZWFrOw0KJSVlbmRyZXBlYXQNCiAgfQ0KICByZXR1cm4gcjsNCn0NCiAgPC9zY3JpcHQ%2BDQogIDxzY3JpcHQgdHlwZT0idGV4dC9qYXZhc2NyaXB0Ij4NCnZhciB0YXJnZXRzID0gW107DQp0YXJnZXRzLnB1c2goew0KICBuYW1lOiAnY29uY2F0X29wJywNCiAgcnVuOiBmdW5jdGlvbihzLCBuKSB7DQogICAgdmFyIHIgPSAnJzsNCiAgICBmb3IgKHZhciBpID0gbjsgLS1pID49IDA7KSB7DQogICAgICByICs9IHM7DQogICAgfQ0KICAgIHJldHVybiByOw0KICB9DQp9KTsNCg0KdGFyZ2V0cy5wdXNoKHsNCiAgbmFtZTogJ2pvaW4nLA0KICBydW46IGZ1bmN0aW9uKHMsIG4pIHsNCiAgICB2YXIgciA9IFtdOyBmb3IgKHZhciBpID0gbjsgLS1pID49IDA7KSB7DQogICAgICByLnB1c2gocyk7DQogICAgfQ0KICAgIHJldHVybiByLmpvaW4oJycpOw0KICB9DQp9KTsNCg0KdmFyIGRlZl9mdW4gPSBmdW5jdGlvbih0cGwsIG5uKSB7DQogIHJldHVybiBuZXcgRnVuY3Rpb24oWydzJywgJ24nXSwNCiAgICBwcm9jZXNzX3RlbXBsYXRlKGRvY3VtZW50LmdldEVsZW1lbnRCeUlkKHRwbCkuaW5uZXJIVE1MLCB7DQogICAgICBubjogbm4sDQoNCiAgICAgIHJlcGVhdDogZnVuY3Rpb24oYywgbikgew0KICAgICAgICB2YXIgcmV0dmFsID0gW107DQogICAgICAgIGZvciAodmFyIGkgPSBuOyAtLWkgPj0gMDsgKQ0KICAgICAgICAgIHJldHZhbC5wdXNoKGMpOw0KICAgICAgICByZXR1cm4gcmV0dmFsOw0KICAgICAgfSwNCg0KICAgICAgaGFuZGxlX3RhZzogZnVuY3Rpb24ocGFyc2VyLCBuYW1lLCBhcmdzKSB7DQogICAgICAgIHN3aXRjaCAobmFtZSkgew0KICAgICAgICBjYXNlICdyZXBlYXQnOg0KICAgICAgICAgIGFyZ3MgPSBhcmdzLnNwbGl0KC9ccyosXHMqLyk7DQogICAgICAgICAgYXJnc1swXSA9IF9ldmFsKHRoaXMsIGFyZ3NbMF0pOw0KICAgICAgICAgIGFyZ3NbMV0gPSBfZXZhbCh0aGlzLCBhcmdzWzFdKTsNCiAgICAgICAgICBwYXJzZXIuc2F2ZV9idWZmZXIoYXJncyk7DQogICAgICAgICAgYnJlYWs7DQogICAgICAgIGNhc2UgJ2VuZHJlcGVhdCc6DQogICAgICAgICAgdmFyIGJ1ZiA9IHBhcnNlci5nZXRfYnVmZmVyKCk7DQogICAgICAgICAgYXJncyA9IHBhcnNlci5yZXN0b3JlX2J1ZmZlcigpOw0KICAgICAgICAgIGZvciAodmFyIGkgPSBhcmdzWzBdLCBlID0gYXJnc1swXSArIGFyZ3NbMV07IGkgPCBlOyArK2kpIHsNCiAgICAgICAgICAgIGlmIChhcmdzWzJdKQ0KICAgICAgICAgICAgICB0aGlzW2FyZ3NbMl1dID0gaTsNCiAgICAgICAgICAgIHBhcnNlci5hcHBlbmQoYnVmKTsNCiAgICAgICAgICB9DQogICAgICAgICAgYnJlYWs7DQogICAgICAgIH0NCiAgICAgIH0NCiAgICB9KSk7DQp9DQoNCmZvciAodmFyIGkgPSAxNjsgaSA8IDY0OyArK2kpIHsNCiAgaWYoaSUxNj09MCl0YXJnZXRzLnB1c2goeyBuYW1lOiAnaHlicmlkJyArIGksIHJ1bjogZGVmX2Z1bigndGVtcGxhdGUxJywgaSkgfSk7DQp9DQoNCmZvciAodmFyIGkgPSAxNjsgaSA8IDY0OyArK2kpIHsNCiAgaWYoaSUxNj09MCl0YXJnZXRzLnB1c2goeyBuYW1lOiAnYnVsaycgKyBpLCBydW46IGRlZl9mdW4oJ3RlbXBsYXRlMicsIGkpIH0pOw0KfQ0KDQp0YXJnZXRzLnB1c2goew0KbmFtZToncmVjdXJzaXZlJywNCnJ1bjpmdW5jdGlvbihzLG4pew0KICB2YXIgcSA9ICcnOw0KICB3aGlsZShuKXsNCiAgICBpZihuJTIpIHEgKz0gczsNCiAgICBzICs9IHM7DQogICAgbiA%2BPj0gMTsNCiAgfQ0KICByZXR1cm4gcTsNCn0NCg0KfSk7DQogIDwvc2NyaXB0Pg0KICA8c3R5bGUgdHlwZT0idGV4dC9jc3MiPg0KdGFibGUuYm9yZGVyZWQgew0KICBib3JkZXI6IDFweCBzb2xpZCBibGFjazsNCiAgYm9yZGVyLWNvbGxhcHNlOiBjb2xsYXBzZTsNCn0NCg0KdGFibGUuYm9yZGVyZWQgdGQsDQp0YWJsZS5ib3JkZXJlZCB0aCB7DQogIGJvcmRlcjogMXB4IHNvbGlkIGJsYWNrOw0KfQ0KICA8L3N0eWxlPg0KPC9oZWFkPg0KPGJvZHk%2BDQogIDx0YWJsZSBjbGFzcz0iYm9yZGVyZWQiPg0KICAgIDx0aGVhZD4NCiAgICAgIDx0cj4NCiAgICAgICAgPHRoIHJvd3NwYW49IjIiPk5hbWU8L3RoPg0KICAgICAgICA8dGg%2BRWxhcHNlZCB0aW1lPC90aD4NCiAgICAgIDwvdHI%2BDQogICAgICA8dHI%2BDQogICAgICAgIDx0aD48c2NyaXB0IHR5cGU9InRleHQvamF2YXNjcmlwdCI%2BDQpkb2N1bWVudC53cml0ZShuYXZpZ2F0b3IudXNlckFnZW50KTsNCjwvc2NyaXB0PjwvdGg%2BDQogICAgICA8L3RyPg0KICAgIDwvdGhlYWQ%2BDQogICAgPHRib2R5Pg0KICA8c2NyaXB0IHR5cGU9InRleHQvamF2YXNjcmlwdCI%2BDQogICAgdmFyIHJ1biA9IGZ1bmN0aW9uKGYpIHsNCiAgICAgIHZhciBzdGFydCA9IG5ldyBEYXRlKCk7DQogICAgICB2YXIgcmVzdWx0ID0gZignMDEyMzQ1Njc4OScsIDEzMTA3MSkubGVuZ3RoICsgZignMDEyMzQ1Njc4OScsIDEzMTA3MSkubGVuZ3RoOw0KICAgICAgdmFyIGVuZCA9IG5ldyBEYXRlKCk7DQogICAgICByZXR1cm4gcmVzdWx0ID09IDEzMTA3MSAqIDEwICogMiA%2FIChlbmQuZ2V0VGltZSgpIC0gc3RhcnQuZ2V0VGltZSgpKSAvIDI6IG51bGw7DQogICAgfTsNCiAgICBmb3IgKHZhciBpIGluIHRhcmdldHMpIHsNCiAgICAgIHZhciByZXN1bHQgPSBydW4odGFyZ2V0c1tpXS5ydW4pDQogICAgICBkb2N1bWVudC53cml0ZSgnPHRyPjx0ZD4nKTsNCiAgICAgIGRvY3VtZW50LndyaXRlKHRhcmdldHNbaV0ubmFtZSk7DQogICAgICBkb2N1bWVudC53cml0ZSgnPC90ZD48dGQ%2BJyk7DQogICAgICBkb2N1bWVudC53cml0ZShyZXN1bHQgIT0gbnVsbCA%2FIHJlc3VsdCArICJtcyI6ICdlcnJvcicpOw0KICAgICAgZG9jdW1lbnQud3JpdGUoJzwvdGQ%2BPC90cj4nKTsNCiAgICB9DQogIDwvc2NyaXB0Pg0KICAgIDwvdGJvZHk%2BDQogIDwvdGFibGU%2BDQo8L2JvZHk%2BDQo8L2h0bWw%2BDQo%3D

 |