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

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

```javascript
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のコンストラクタで実装したとき、それを使用するコードは次のようになります（実装内容は記事後半に記載します）。

```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()`を使って冒頭のコードを書き変えてみます。

```javascript
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`コンストラクタのソースコードを置いておきます。もしよければ使ってみてください。何かバグがありましたらご報告いただけると嬉しいです。

```javascript
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　～平衡二分探索木編～](https://www.slideshare.net/iwiwi/2-12188757)