手書きしたほうが速いメソッドと疎な配列

9558 ワード
JavaScript 配列 JavaScript テキストリンク

JavaScriptで配列を駆使するようなプログラムを書くことも多いですが、状況によっては標準のメソッドを使うより、手書きでループを回したほうが速いこともあります。

Qiitaの記事を読んでいて

少し前に投稿されたTypeScriptの記事を見ていたのですが、その中で、

重大なボトルネックとなりうるため全体で100msに1回以上の間隔で実行される場合を除き以下のメソッドを原則使用禁止とする。

  • Array#concat
  • Array#slice
  • Array#splice

なんていう記述がありました。さすがに「え、そうなの？」と思いましたが、すぐ下に付いていたベンチマークは、たしかにそのような結果を示しました。

そうなる理由

もちろん、ネイティブに実装してあることもあるような標準メソッドが、JavaScript上に実装したものより遅いというのはさすがにおかしいので、調べてみました。すると、原因がわかりました。ということで、仕様書に沿って、JavaScriptでArray#sliceを書き下してみることにします（thisが特殊なオブジェクトだった場合など、厳密な動作は一部違うかもしれません）。

slice.js

Array.prototype.slice = function(start, end){
  function ToInteger(num){
    //ToNumber
    num = +num;
    //NaN
    if (num !== num) return 0;
    if ((num === 0) || (num === Number.POSITIVE_INFINITY) || (num === Number.NEGATIVE_INFINITY) ){
      return num;
    }
    if (num > 0) {
      return Math.floor(num);
    } else {
      return -Math.floor(-num);
    }
  }

  //ToObject
  if (this == null) throw new TypeError;
  var obj = Object(this);

  var arr = [];

  var lenVal = obj.length;

  // ToUint32
  var len = lenVal >>> 0;

  var relativeStart = ToInteger(start);
  var k;
  if (relativeStart < 0) {
    k = Math.max(len + relativeStart, 0);
  } else {
    k = Math.min(relativeStart, len);
  }

  var relativeEnd;
  if (end === undefined) {
    relativeEnd = len;
  } else {
    relativeEnd = ToInteger(end);
  }

  //仕様書ではfinalだけど、予約語なので回避
  var final_;
  if (relativeEnd < 0) {
    final_ = Math.max(len + relativeEnd, 0);
  } else {
    final_ = Math.min(relativeEnd, len);
  }

  var n = 0, kPresent, kValue;
  while (k < final_) {
    //[[HasProperty]]
    kPresent = k in obj;
    if (kPresent) {
      kValue = obj[k];
      arr[n] = kValue;
    }
    ++k;
    ++n;
  }

  return arr;
};

引数の処理が大半を占めていますが、注目すべきはwhileのメインループの中です。k in objとして、プロパティの存在チェックをしていますが、これは普通にobj[k]を参照するより遅くなっています。これらはconcatやspliceにも共通しています。

もちろん、0からlength -1まできっちり詰まった配列であれば、k in objは常に真なので、ループから除外することで高速化できます。一方で、プロパティとして空きがある、疎な配列の場合だと、k in objをチェックせずに回せばundefinedが入ります。

もちろん、そのままでも必要な性能が出ていれば無理に変える必要はありませんし、意図的に（undefinedが要素として入っていると困るような）疎な配列を使う場面もそう多くはないかもしれません。とはいえ、標準のメソッドが汎用に作ってあることで、こんなオーバーヘッドがあることを、知っておいて損はないでしょう。

ふわふわpython-マジックメソッド(magic method)
深さ学習pythonデータ構造(一)-シーケンス読み出しpickleとcPickle