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

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 ~平衡二分探索木編~