読者です 読者をやめる 読者になる 読者になる

latest log

酩酊状態で書いたエンジニアポエムです。酩酊状態で読んでください。

uupaa looper 見っけたよー

(ε・◇・)з hasOwnProperty を使った for in ループより 20%~84% 低コストな、うーぱー式 ループのご紹介だよ~


Object.keys を使い、key を列挙することで、hasOwnProperty を使った for in ループよりも速くなります。

var keys = Object.keys(obj), i = 0, iz = keys.length;

for (; i < iz; ++i) {
  var key = keys[i];
  var value = obj[key];
  ...

ベンチマーク

http://jsperf.com/perf-for-in-loop-vs-pre-enum-keys-for-loop/8

Browser for_in_hasOwnProperty loop uupaa-looper
Chrome 16.0.912.77 14,765 (75% slower) 60,038
Firefox 10 33,655 (43% slower) 59,113
IE 9.0.4 (x86) 18,888 (67% slower) 57,784
IE 10 pp2 18,808 (72% slower) 66,385
Opera 11.61 16,365 (21% slower) 20,706
iPhone 4S (iOS 5.0.1) 2,265 (57% slower) 5,211
iPad 2 (iOS 5.0.1) 2,674 (58% slower) 6,296
Galaxy Nexus (Android 4.0.1) 2,753 (80% slower) 14,064
Galaxy Nexus Chrome β (Android 4.0.1) 2,082 (84% slower) 12,652

f:id:uupaa:20141016132502p:plain

f:id:uupaa:20141016133008p:plain

<script>
// 一般的なやり方の for-in ループです
// 毎回 hasOwnProperty() を呼びます
function for_in_hasOwnProperty(hash) {
    var rv = [], key;

    for (key in hash) {
        if (hash.hasOwnProperty(key)) {
            rv.push(key);
        }
    }
    return rv;
}

// 一般的ではありませんが、限定的な用途で使える for-in ループです
// 毎回 hasOwnProperty() を呼ばないため、多少速くなります
function for_in(hash) {
    var rv = [], key;

    for (key in hash) {
        rv.push(key);
    }
    return rv;
}

// Object.keys でキーを列挙しておく新しいやり方です
// for in + hasOwnProperty や for in ループよりも基本的に高速です
function uupaa_looper(hash) {
    var rv = [], ary = Object.keys(hash), i = 0, iz = ary.length;

    for (; i < iz; ++i) {
        rv.push(ary[i]);
    }
    return rv;
}

テストデータ

function createTestData(count) {
    var rv = {}, i = 0;

    for (; i < count; ++i) {
        rv[i] = i;
    }
    return rv;
}

function times(num, fn, arg) {
    var now = Date.now(), i = 0;

    for (; i < num; ++i) {
        fn(arg);
    }
    console.log(fn.name, Date.now() - now);
}


Object.prototype.oreore1 = "oreore1";
Object.prototype.oreore2 = "oreore2";
Object.prototype.oreore3 = "oreore3";
Object.prototype.oreore4 = "oreore4";

// 1000 times x 200 keys
var testData = createTestData(200);
times(1000, for_in_hasOwnProperty,        testData);
times(1000, for_in,       testData);
times(1000, uupaa_looper, testData);

// 1 times x 10000 keys
testData = createTestData(10000);
times(1, for_in_hasOwnProperty,        testData);
times(1, for_in,       testData);
times(1, uupaa_looper, testData);

</script>

つまり?

  • for (key in object) な for-in ループでは object の prototype チェーンをたどってしまい、object に本来無関係なメソッドやプロパティ(oreore等)も列挙してしまいます
    • 無関係な prototype メンバーのピックアップを避けるには hasOwnProperty を使い除外します
    • JavaScript は関数呼び出しコストが高いので、ループ毎に hasOwnProperty を呼ぶとその分だけ遅くなります
  • for-in ループには、ループを開始する前に key を列挙しリストを作成するといった見えない処理が挟まります
    • リスト作成処理には、object の prototype チェーンを順番に辿り、同じ名前を除外するといった、重めの処理が隠れているのです
      • for_in が uupaa_looper よりも遅いのは、この「見えない処理」が関係しています
  • Object.keys(object) は prototype メンバーを列挙せずに、object に関連する物だけを列挙します。速いです

といった条件を加味し、事前に Object.keys で作成し、それを for ループで… というのがこのやり方です。

(ε・◇・)з このやり方は既出かもしれないけど、さっきやっと気づいたんだよね
(ε・﹏・)з 名前が無いと検索しづらいから「uupaa looper」って名前つけといたよ

レガシーブラウザ対策も

これで Object.keys が使えるようになります。

Object.keys = function(source) {
    var rv = [], key, ri = 0;

    for (key in source) {
        if (source.hasOwnProperty(key)) {
            rv[ri++] = key;
        }
    }
    return rv;
};

(ε・◇・)っ rv[ri++] = key; は rv.push(key); よりも高速なのです in レガシーブラウザ
(ε・◇・)っ Chrome では push のほうが速いのです #豆

終わりに

クラスを派生させる構造を基礎としている 某JavaScript ゲームライブラリなどは、このようなやり方にすると、より速くなるのではないでしょうか。

また、ary = Object.keys(object).sort() とすることで、キーの出現順を安定させクロスブラウザにする事も可能になります(ちょっとコスト増えますが)。


(ε・◇・)з それ既に名前ついてるよー とかありましたら @uupaa までー
(ε・◇・)з js で有効なTips は ActionScript でも有効な Tips だったりしませんか? (だれか~