MENU

JavaScript配列・連想配列

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

更新日:2021/05/18

 

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

 

 

関連記事:
【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 ) )の回数が、カウントダウンバージョンの方が少なくなっているのです。

 

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

 

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

 

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

 

2分検索で効率化

 

これまでのコードはインデックス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から順番に比較していく方法を選択するほうが無難ですね。

けーちゃんおススメJavaScript入門書

  • スラスラ読める JavaScript ふりがなプログラミング
  • プログラム未経験者がJavaScript始めるならコレ!
    コードを掲載して自分で理解しろという投げっぱなしな入門書とは異なり、コードに一つ一つどんなことをやっているかをふりがなという形式で解説しています。
    それでいてJavaScriptの基礎と応用を学べる良書です。
  • これからWebをはじめる人のHTML&CSS、JavaScriptのきほんのきほん
  • JavaScriptの機能を実践で活かすにはHTMLやCSSの知識が不可欠です。
    しかしそれらの知識があることが前提として書かれている書籍が多い中、この本は総合的な知識を身に着けることができます。
    HTMLやCSSの知識も不安な方には、ぴったりの一冊です
  •  

    入門書の役割は、自分のやりたいことをネットで調べることができるようになるための、基礎的な知識の獲得です。
    まずはこれらの本でしっかりと基礎知識を身につけましょう。
    そしてもっと高度なことや専門的なことはネットで調べ、情報が足りないと感じたら書籍を購入してください。


    期間限定情報:
    6/21と6/22は年に一度のプライム会員大感謝祭!
    欲しかったアレが安く手に入るチャンスです
    忘れずにチェックしてください!
    僕は以前のタイムセール祭りで4Kモニタが買ったけど、それより安かったらどうしよう・・・

    ちなみにプライム会員でなくても、無料体験で参加できるようです。
    欲しい商品があるか、確認だけでもしておきましょう。

    記事の内容について

     

    こんにちはけーちゃんです。
    説明するのって難しいですね。


    「なんか言ってることおかしくない?」
    たぶん、こんなご意見あると思います。

    裏付けを取りながら記事を作成していますが、僕の勘違いだったり、そもそも情報源の内容が間違えていたりで、正確でないことが多いと思います。

    そんなときは、ご意見もらえたら嬉しいです。

    ご意見はこちら。
    https://note.affi-sapo-sv.com/info.php

    【お願い】

    お願い

    ■このページのURL


    ■このページのタイトル


    ■リンクタグ


    ※リンクして頂いた方でご希望者には貴サイトの紹介記事を作成してリンクを設置します。
    サイト上部の問い合わせよりご連絡ください。
    ただしサイトのジャンルによっては、お断りさせていただくことがあります。