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つです。
- 追加する場所と要素数に依らず、要素の追加にそれほど時間がかからない
- 添字（インデックス）による要素の参照にそれほど時間がかからない
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);
};
}