【JavaScript】 ソート済みの配列に値を挿入する効率的な方法

JavaScriptには配列内のデータを並び変えるsortというメソッドがあります。
しかし配列内のデータが順番に並び変えられていて、その配列に新しい値を挿入したい場合は、sortメソッドは非効率です。

ソート済みの配列に新しい値を挿入する場合、sortメソッドを使用するのは効率が悪いです。

例えば次のような配列があるとします。

const array = [3,1,5,7];

この配列はソートされていないので、sortメソッドを使用して並び替るのは問題ありません。

array.sort();
console.log( array ); // [ 1, 3, 5, 7 ]

これに値を追加して、sortメソッドで並び変えてみます。

array.push( 4 );
console.log( array ); // [ 1, 3, 5, 7, 4 ]

array.sort();
console.log( array ); // [ 1, 3, 4, 5, 7 ]

期待通りの結果になりました。
この処理の何が問題なのでしょうか？

sortメソッドの引数に、比較関数を与えて値比較の流れを見てみます。

array.push( 4 );
array.sort( (a,b)=>{
        console.log( a,b );
        return a-b;
    });

// 1 3 ← ムダ
// 3 5 ← ムダ
// 5 7 ← ムダ
// 7 4
// 5 4
// 3 4

新しい値を挿入するには、元からある値と新しい値の比較だけで済むはずです。
しかし1と3、3と5など、元からある値の比較が行われています。
これは無駄な比較ですね。
効率が悪いと言えます。

挿入する値と配列内の要素を順番に比較して値が要素より小さいとき、その位置に挿入してみます。

const insertValue = (val,array) => {
            const length = array.length;

            for( let i = 0 ; i < array.length ; i ++ )
                if( array[i] > val ) {
                    array.splice( i , 0 , val );
                    return;
                }
            array.push( val );
        };

insertValue( 4 , array );

console.log( array ); //  [ 1, 3, 4, 5, 7 ]

挿入位置が決定した場合、spliceメソッドを呼び出して、配列内に値を挿入しています。

配列に要素がない、または挿入値が配列内の要素よりも大きい場合は、pushメソッドで配列の最後に値を追加しています。

最初の例と速度比較してみます。

最初の例を次のコードで10000回繰り返します。

const startTime = Date.now();

for( let i = 0; i < 10000 ; i ++ ){
    array.push( i );
    array.sort();
}

console.log( Date.now() - startTime ); // 2563

処理が終わるまでFirefoxは2563ミリ秒、Chrome1341ミリ秒かかりました。

バックで動作している拡張機能などの影響を受けるので、他のPCで実行するとまた違った結果がでると思います。
ここでは、2秒程度かかっていると思ってください。

次は、ここで紹介したコードを10000回繰り返します。

const startTime = Date.now();

for( let i = 0; i < 10000 ; i ++ ){
    insertValue(i , array);
}

console.log( Date.now() - startTime ); 

Firefox203ミリ秒
Chrome60ミリ秒でした。

少なくても10倍以上速くなっていますね。

ちなみにspliceメソッドは、内部でインデックスの付け替えを行っています。
毎回付け替えを行うのも効率が悪い気がします。

ですが、0から順番にカウントアップしている上のコードでは、初期要素の範囲を超えると、常に最終インデックスに値がセットされるため、インデックスの付け替えがおこなわれていません。

そこでインデックスの付け替えが最大限になるように、次のようにカウントダウンで挿入してみます。

for( let i = 10000; i > 0 ; i -- ){
    insertValue(i  + 1, array);
}

こうすると、最終インデックスよりも前に挿入されるため、インデックスの張替がおこなわれます。
そのため処理速度が遅くなるはずです。

Firefox203ミリ秒→66ミリ秒
Chrome60ミリ秒→16ミリ秒でした。

逆に速くなってますね…

実はinsertValue関数内での値の比較処理（ if( array[i] > val ) )の回数が、カウントダウンバージョンの方が少なくなっているのです。

つまり、インデックスの張替よりも、コード上での比較の方が時間がかかっているのです。

もしかしたら一つ一つ貼りかえているのではなくて、最適な方法で実装されているのかもしれません。

あまり気にしなくてもよさそうです。

これまでのコードはインデックス0から順番に見ていくため、目的の値が配列の後半にあると、速度が遅くなります。

そこで配列の中央インデックスの値を取り出し、大ききれば後半、小さければ前半の範囲で、さらに中央のインデックスの値を比較するという処理を繰り返します。
その結果、少ない試行回数で目的の値を検索することができます。
これは、2分検索法と呼ばれています。

insertValue関数を、この考え方で書き換えてinsertValue2関数を作成してみます。

const insertValue2 = (val,array) => {
            const length = array.length;
            if( length === 0 || array[length-1] <= val ){
                array.push( val );return;
            }

            let left=0,right = length;
            let index = Math.floor((left + right) / 2);
            while (right > left) {
                [right,left] = val < array[index] ? [ index,left ] : [ right , index + 1 ];
                index = Math.floor((left + right) / 2);
            }
            array.splice(index, 0, val);

        };

また10000回実行してみます。
0から順番にカウントアップすると、最初の比較で終わってしまうので、ランダムで10000個の数値を作成して、その値を挿入してみます。

    // 10000個のランダム数値を配列にセット
const rndValue = Array.from({length:10000},()=>Math.floor( Math.random() * 10000 ) );

    // insertValue関数の速度計測
let array = [3,2,5,7];
array.sort();

let startTime = Date.now();

for( let i = 0; i < 10000 ; i ++ ){
    insertValue(rndValue[i] , array);
}
console.log( Date.now() - startTime );

    // insertValue2関数の速度計測
array = [3,2,5,7];
array.sort();

startTime = Date.now();

for( let i = 0; i < 10000 ; i ++ ){
    insertValue2(rndValue[i] , array);
}
console.log( Date.now() - startTime );

Firefoxの結果：

insertValue 135ミリ秒
insertValue2 58ミリ秒

Chromeの結果：

insertValue 49ミリ秒
insertValue2 21ミリ秒

実行するたびに異なるランダム配列が作成されるので、FirefoxとChromeのどちらが速いかという比較はここでは意味がありません。

insertValue関数とinsertValue2関数の速度差を見ると、2分検索法を用いたinsertValue2の方が50%以上の時間短縮になっています。

ただしこの2分検索コードは理論上正しいと思われるコードです。
実際に運用するには、それなりのテストが必要です。

また、元の配列に同じ値はあるとき、前に挿入するのか後ろに挿入するのかなどの調整をおこないたいとき、非常に悩むと思います。

もし速度がそれほど重要でないなら、素直に0から順番に比較していく方法を選択するほうが無難ですね。