Help us understand the problem. What is going on with this article?

Array.prototype.splice()の遅さと改善策

More than 1 year has passed since last update.

JavaScriptのArray.prototype.splice()は、配列の途中に要素を追加するメソッドですが、追加する回数(以下ループ回数)が3万を超えると無視できないくらいの時間となります。たとえば、手元のパソコンで以下のコードを実行すると、1.153秒かかりました。

let start = new Date().getTime();
let arr = [];
for (let i = 0; i < 30000; i++) {
  arr.splice(0, 0, i);
}
console.log((new Date().getTime() - start) / 1000);

splice()の問題点は、ループ回数が半分のときにかかる時間が、約4分の1=0.294秒であることです。これはつまり、ループ回数が倍の6万になると、かかる時間が約4倍になってしまうということです。実際に測ってみると4.652秒でした。ループ回数と計算時間の関係を表にまとめてみます。

ループ回数 計算時間
15,000 0.294s
30,000 1.153s
60,000 4.652s

この表を見ると、どうやら計算時間はループ回数の2乗に比例するようです。

このような計算量の増加があるため、ループ回数が3万を超えるような場合、splice()を使うべきではありません。

しかし、使うべきではないとしても、splice()のようなメソッドが欲しくなることはあります。たとえば、10万文字を超える文章があり、漢字の後ろに振り仮名をつける処理を書きたいとします。以下のような感じです。

吾輩は猫である。名前はまだ無い。
吾輩(わがはい)は猫(ねこ)である。名前(なまえ)はまだ無(な)い。

このときに、文章を配列として持っていたとき、振り仮名を追加するときにsplice()を使うことになりますが、10万文字だと単純計算で15秒程かかります。もしこのスクリプトがブラウザ上で動くとしたら、かなり長く感じると思います。途中でページを閉じたくなる可能性が高いです。

ということで、配列ではない別のデータ構造が欲しくなります。
理想のデータ構造に求める条件は2つです。

  1. 追加する場所と要素数に依らず、要素の追加にそれほど時間がかからない
  2. 添字(インデックス)による要素の参照にそれほど時間がかからない

2つ目の条件について。どれだけ要素の追加が高速にできたとしても、要素の参照が遅いと、文章を表示するときに時間がかかってしまいます。文章を表示するとき、まず一文字目を表示して次に二文字目を表示して…というように前から順番に文字を取り出すことになりますが、このときに時間がかかってはいけないので、2つ目の条件も必要になります。

この2つの条件を満たすものの一つが、Treapと呼ばれるデータ構造です。

TreapをJavaScriptのコンストラクタで実装したとき、それを使用するコードは次のようになります(実装内容は記事後半に記載します)。

let treap = new Treap();
treap.insert(0, 1);             // treap = [1]
treap.insert(0, 2);             // treap = [2, 1]
treap.insert(1, 3);             // treap = [2, 3, 1]
console.log(treap.search(0));   //=> 2
console.log(treap.search(1));   //=> 3
console.log(treap.search(2));   //=> 1

Treap.prototype.insert()splice()に相当し、Treap.prototype.search()が添字による要素の参照に相当します。insert()を使って冒頭のコードを書き変えてみます。

let start = new Date().getTime();
let treap = new Treap();
for (let i = 0; i < 30000; i++) {
  treap.insert(0, i);
}
console.log((new Date().getTime() - start) / 1000);

結果は次のようになりました(計算時間は、何度か実行したおおよその平均です)。

ループ回数 計算時間 ループ回数 計算時間 ループ回数 計算時間
15,000 0.032s 120,000 0.094s 960,000 0.669s
30,000 0.046s 240,000 0.182s 1,920,000 1.279s
60,000 0.062s 480,000 0.354s 3,840,000 2.624s

splice()と違って、要素の追加にかかる時間がループ回数そのものに比例していることがわかります。ループ回数の2乗ではなくループ回数に比例しているため、計算時間の爆発的な増加はありません。そして、添字による要素の参照のメソッドであるsearch()も、同じようにループ回数と計算時間は比例します。

ループ回数と計算時間が比例するということは、つまりinsert()search()1回にかかる時間は、要素数に関わらず一定だということです。splice()はそうではありません。要素数1の配列に要素を追加するときの時間と比較した、要素数1億の配列に追加するときにかかる時間は、およそ1億倍です。

いかにTreapが2つの条件を満たすデータ構造として優れているかがわかります。

結論

といった感じで、splice()がボトルネックの場合にはTreapの使用を検討してみるのもいいかもしれません。

最後にTreapコンストラクタのソースコードを置いておきます。もしよければ使ってみてください。何かバグがありましたらご報告いただけると嬉しいです。

const Treap = function() {
  this._root = null;
};

{
  const Node = function(v) {
    this.val = v;
    this.lch = null;
    this.rch = null;
    this.pri = Math.random();
    this.cnt = 1;
  };

  const count = t => !t ? 0 : t.cnt;

  const update = t => {
    t.cnt = count(t.lch) + count(t.rch) + 1;
    return t;
  };

  const merge = (l, r) => {
    if (!l || !r) return !l ? r : l;

    if (l.pri > r.pri) {
      l.rch = merge(l.rch, r);
      return update(l);
    } else {
      r.lch = merge(l, r.lch);
      return update(r);
    }
  };

  const split = (t, k) => {
    if (!t) return [null, null];

    if (k <= count(t.lch)) {
      let s = split(t.lch, k);
      t.lch = s[1];
      return [s[0], update(t)];
    } else {
      let s = split(t.rch, k - count(t.lch) - 1);
      t.rch = s[0];
      return [update(t), s[1]];
    }
  };

  const insert = (t, k, v) => {
    let s = split(t, k);
    let l = merge(s[0], new Node(v));
    return merge(l, s[1]);
  };

  const search = (t, k) => {
    if (k < 0 || k >= count(t)) return null;

    if (count(t.lch) === k) {
      return t.val; 
    } else if (count(t.lch) > k) {
      return search(t.lch, k);
    } else {
      return search(t.rch, k - count(t.lch) - 1);
    }
  };

  Treap.prototype.count = function() {
    return count(this._root);
  };

  Treap.prototype.insert = function(k, v) {
    this._root = insert(this._root, k, v);
  };

  Treap.prototype.search = function(k) {
    return search(this._root, k);
  };
}

参考

プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away