文字列の結合と分割の速度について

スタッフブログ

こんにちは、最近プログラムのアルゴリズムを考える勉強に取り組んでいる森山です。今勉強に使っているサイトでは実行速度が速いプログラムを組む事が求められるのですが、何も考えずに実装するとタイムアウトしてしまうこともよくあります。そこで今よりも実行の速いアルゴリズムを考えるのですが、同じ処理をするメソッドでも実装の都合で速い物と遅いものがあり、一度調べておけば選択肢の中からもっとも速いものを選べるのでは?と思いました。ということで今回はJavaScriptで文字列を結合する時と分割する時の実行速度について調べてみたので紹介したいと思います。

文字列の連結の種類

Array.prototype.join

joinメソッドは、配列オブジェクトの全要素を順に連結して新たな配列を返します。引数には区切り文字を指定できますが、空文字を指定すれば区切り文字無しで連結することができるので今回はこの方法で時間の測定をします。

String.prototype.concat

concatメソッドは、1つ以上の引数を文字列に連結して新しい文字列を返します。処理としては、今までの文字列のconcatメソッドの引数に新たに追加したい文字を渡すのを文字数分繰り返して連結します。このメソッドには引数が複数指定できるのですが、それよりも1回ずつ追加したほうが速かった為今回は1回ずつで測定します。

加算代入演算子

加算代入演算子は、右辺の値を左辺の値に加算した結果を左辺の変数に代入します。少しややこしく聞こえますが、結局のところa = a + bと書いていたものをa += bという風に省略ができるという風に認識してもらえば良いと思います。

文字列の連結の実行速度

    const text1 = ["a", "b", "c"];
    const text2 = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];
    const text3 = ["abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "abcdefghijklmnopqrstuvwxyz"];
    let str = text.join("");
    let str = "";
    for (const char of text) {
        str = str.concat(char);
    }
    let str = "";
    for (const char of text){
        str += char;
    }

今回テストしたのは3種類の文字列で、それぞれabc(1文字 x 3個)の連結と小文字のアルファベット全種類(1文字 x 26個)の連結、小文字全種3セット(26文字 x 3個)の連結です。テストした処理は先ほど紹介した、Array.prototype.joinとString.prototype.concatと加算代入演算子です。joinメソッドはメソッド内でループ処理実行されますが、他2つはそれぞれループ処理が必要なためfor...of文でループ処理を統一しています。

測定した環境は記事執筆時最新版の、Google Chromeのver88.0.4324.150です。それぞれの連結処理を100万回繰り返した時間を計測して、それを50回繰り返して平均を取りました。

(1文字 x 3個) (1文字 x 26個) (26文字 x 3個)
joinメソッド 81.932 ms 431.285 ms 87.931 ms
concatメソッド 15.644 ms 141.188 ms 12.694 ms
加算代入演算子 16.618 ms 141.406 ms 11.934 ms

全体を通して一番時間がかかったのはjoinメソッドでした。ですが、concatメソッドと加算代入演算子の差が少なく、アルファベット全種3セットと他2つで速度が逆転しています。これに関しては誤差の可能性を疑って何度か計測し直しましたが、平均的にアルファベットabcと1文字全種ではconcatが速く、アルファベット全種セットでは加算代入演算子が速かったです。

文字列の分割の種類

ブラケット表記法

ブラケット表記法はプロパティアクセサーの一種で、配列の要素にアクセスする時などに使う角括弧に数字や文字列を入れてアクセスする方法です。String型もブラケット表記法にてアクセスすることができるので全文字にアクセスして1つずつ配列に追加する方法で分解します。

String.prototype.charAt

charAtメソッドは文字列の中の指定された位置にある単一の文字を返します。使い方はブラケット表記法にとても似ていて、インデックス番号を引数に渡すことで文字を取得できるのは変わりません。これもブラケット表記法と同じく、全文字にアクセスして1つずつ配列に追加する方法で分解します。

Array.from

fromメソッドは配列のようなオブジェクトや反復可能オブジェクトからシャローコピーされた配列を生成します。今回は文字列が反復可能オブジェクトに当たるのでメソッドの引数にそのまま渡せば配列に変換してくれます。

String.prototype.split

splitメソッドは、文字列を指定した区切り文字で分割して配列を生成します。引数には区切り文字を指定するのですが、空文字を指定するとすべての文字の間で区切るので結果としてすべてを分割した配列が生成されます。

スプレッド構文

スプレッド構文は、反復可能オブジェクトやオブジェクト式を期待された場所で展開できます。このスプレッド構文とよく似た動きをするものでFunction.prototype.applyというものもありますが、こちらは関数のメソッドなのに対し、スプレッド構文は期待された箇所であればいつでも使える上手軽なのでよく使割れると思います。期待された箇所であれば良いので配列の中にスプレッド構文で文字列を入れればそのまま分割された配列が生成されます。

残余引数

残余引数は、不定数の引数を配列として表すことができます。これは関数の引数などでスプレッド構文のように引数にしておくことで受け取っていない引数を配列でまとめて受け取れます。そして、分割代入でもこの残余引数を使用することができるので文字列をそのまますべて残余引数で受け取れば分割された配列が生成されます。

文字列の分割の実行速度

    const text1 = "abc"
    const text2 = "abcdefghijklmnopqrstuvwxyz"
    const text3 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    const arr = [];
    for (let i = 0; i < text.length; i++){
        arr.push(text[i]);
    }
    const arr = [];
    for (let i = 0; i < text.length; i++){
        arr.push(text.charAt(i));
    }
    const arr = Array.from(text);
    const arr = text.split("");
    const arr = [...text];
    const [...arr] = text;

計測したのは3種類の文字列と6種類の分割処理です。文字列は先ほどのテストのテキスト処理結果である3文字のアルファベットとアルファベット小文字全種、アルファベット3セットを使用しました。また、分割処理の中には文字のみを生成するものがあるためループにはfor文、追加にはpushメソッドを使用しています。

アルファベット3文字 アルファベット26文字 アルファベット78文字
ブラケット表記法 21.064 ms 105.556 ms 311.877 ms
charAtメソッド 19.911 ms 102.104 ms 313.32 ms
fromメソッド 21.677 ms 125.690 ms 340.140 ms
splitメソッド 66.115 ms 90.519 ms 146.156 ms
スプレッド構文 16.849 ms 122.126 ms 336.402 ms
残余引数 24.948 ms 138.658 ms 396.235 ms

今回もっとも効率が悪かったのは残余引数のようです。スプレッド構文もほぼ同じような処理だと思っていたのですが、想像以上に速度の差が付き、3文字では最速でした。速度を考えるのなら残余引数で書いている部分は渡す側でスプレッド構文に変更したほうが良いと思います。また、3文字の分割だけで見るとsplitメソッドがとびぬけて遅いですが、文字数が長くなるとむしろ効率が上がっています。何らかの最適化がされているのでしょうが、文字数が多いと2倍以上の速度差が出るのであれば普段から使ってみても良いかもしれません。

次に効率が良かったのはブラケット表記法とcharAtメソッドです。この2つはほとんど差が無くて断定はできませんが文字数が少ない内はcharAtメソッドが速く、多くなるとブラケット表記法が巻き返すような傾向ではないでしょうか。どちらにせよ文字列が長くなるならsplitメソッドの方が速いのでどちらかといえばcharAtメソッドが良さそうです。

まとめ

今回は文字列の結合と分割の速度を計測しましたが、文字列結合をするときは加算代入演算子を使用して、分割するときに文字列が長ければsplitメソッドを使い、短ければスプレッド構文で分割するのが良いと思います。しかし、これはあくまでブラウザの実装に依存する話なので実装が変われば結果も変わると思います。その点にはご注意ください。