文字列連結の常識、joinは本当に速いのか[Python3]

#immutableな文字列連結に、+を使うのはタブーという定説
何を言っているかわかる人は、すぐに計測結果と評価の項を見てもらって構わない。初級者＋αの人向けに書かれた本によく書かれている、「文字列連結には+を使用せず、joinメソッドを使用する」ベストプラクティスを守らずに困ったことがあまりないので、本当に大きく性能が違うのか疑ってみようという話である。
##immutableとmutable
PythonやJavaにおける文字列や数値はimmutable(イミュータブル)なオブジェクトだ。immutableとは、mutableと対の概念で、immutableなオブジェクトは一度生成されると値の変更ができない。どういう事かと言うと、immutableなオブジェクトの値を変更する際は、**必ず元のオブジェクトは破棄され、新しいオブジェクトとして生成されるという事だ。**Pythonでの数値オブジェクトの変更例を見てみよう。

%python3

>>>a = 3
>>>id(a)
10919488

>>>a = 5
>>>id(a)
10919552

id()を使用すると、オブジェクトが更新前後で同一かどうか確認することができる。値の更新が行われると元のaは破棄され、aは新しいオブジェクトとして(メモリ上の別の位置に)再生成されていることが分かる。
比較的新しい言語あるRustでは、この事を意識させるため、mutableか、immutableかを事前にユーザーに指定させる仕様になっている。

let x = 5;
x = 6;
error: re-assignment of immutable variable `x`

//イミュータブルな変数 `x` に再代入している

let mut x = 5; //mutable指定
x = 6;

//OK

##immutableな文字列の連結
Pythonユーザーなら、+で文字列連結が出来ることは知っていて、+での連結はいたって直感的で自然な表記といえる。

>>> S=‘’
>>> for I in range(10):
…	S += ’s’
>>> S
‘ssssssssss’


しかし、immutableな文字列の連結ベストプラクティスは、以下のようにjoinメソッドを使用する事であるとされている。

>>> L = ['pen', 'pineapple', 'apple', 'pen']
>>> S = '' . join(L)
>>> S
‘penpineappleapplepen’

immutableな文字列を+を使って繰り返し連結すると、繰り返しの度に新しいオブジェクトが生成されるため時間がかかり、実行時間に悪影響を及ぼすと言われているからだ。
今回は、このjoinメソッドを使用したimmutableな文字列連結の効果がどれほどか検証したい。 **最適化手法というものはその効果と必要な場面を知っていて初めて役に立つものであるからだ。**文字列連結には他の方法もあるのだが、今回は+演算子とjoinメソッドの2者比較を行なった。条件は以下の表にまとめてある。

Pythonバージョン	コア	動作周波数	メモリ	キャッシュメモリ
Python 3.6.0	Intel Core i5	2.3GHz（Turbo Boost使用時最大3.6GHz）	16GB	64MB

#+ VS join 2者比較
##連結する文字列の長さによる影響
今回は、文字列Sに繰り返し同じ文字列を連結し実行時間を計測した。連結回数は100回、1000回、10000回、100000回の5種類であり、測定値は全て100回測定の平均値をとっている。以下のグラフは、ループ回数5種類それぞれで、連結する文字列の長さ(1〜100文字)を変化させたときの実行時間変化だ。

100、1000回のループでは、両者ともに文字列の長さに関して時間の影響は少ないが、10000回、100000回までループが増えると+演算子の方は文字列の長さに対して単調に実行時間が増加していることが分かる。再生成する文字列の長さが極端に長くなると、+演算子を使用した時の性能は低下する。ただし、驚くべきは、ループ回数100回に関しては、文字列の長さが4文字以下であれば+の方が実行時間が短くなるということである。英単語の平均アルファベット長が4.5文字である事を考えると、小型プログラムであれば+演算子で良いのではないかと言う気がする。両者の性能差は、ループ100000回で文字列長が大きくなると大きくなり、最大で1ms程度である。

##ループ回数による影響
下のグラフは、連結する文字列の長さがそれぞれ5文字、20文字、100文字の場合の、ループ回数5種類の実行時間を比較したグラフだ。文字列長を固定すると、両者ともループの回数が10倍なら実行時間10倍と比例するようだ。(グラフは両対数グラフ)

#最適化手法としての評価
**全体の傾向としては、joinメソッドの方が+演算子より実行時間性能は良く、「ペストプラクティス」(プログラムで特定の機能を実装する際、まず最初の候補となる手法)と呼ぶにはふさわしい。**また、joinメソッドは文字列長増加に対して実行時間の増加がほとんど見られないので、実行時間の見積もりが可能な点では優れている。
**しかし、両者の差は10万回ループでも最大で1ms程度であった事を考えると、今回の例がプログラム性能に著しく影響を及ぼす事例は稀と言っていい。**ループ100回、文字列5文字未満であれば+演算子の方が速かったことも見逃せない。Python2.xではjoinメソッドの方が圧倒的に速いことが報告されているので、このあたりはPython3.xで何らかの最適化がなされたと推測される。
Python3.xでプログラムの性能を改善しようと思う場合には、今回の「ベストプラクティス」を気にするより、Python製のモジュールをC系実装のものに置き換えることを検討したほうが良さそうである。

#ソースコード
今回使用したソースコードを以下に置いておきます。自動化等をやっていただければ計測自体は2,3分程度で終わるので、気になる方はやってみてください。

import time
import sys

def useOperator(loop_number, string_length):
    average=0
    string='a'*string_length
    for j in range(100):
        start = time.time()
        S = ''
        for i in range(loop_number):
            S += string
        elapsed_time = time.time() - start
        average += elapsed_time
    average /= 100
    return average


def useJoin(loop_number, string_length):
    average=0
    string='a'*string_length
    for j in range(100):
        start = time.time()
        characters = []
        for i in range(loop_number):
            characters.append(string)
        S = ''.join(characters)
        elapsed_time = time.time() - start
        average += elapsed_time
    average /= 100
    return average

if __name__ == '__main__':
    try:
        line = '-----------'
        number_of_loops = int(sys.argv[1])
        string_length = int(sys.argv[2])
        print(line*10)
        print('simply use + operator to concatenate strings.\n' \
            + 'number_of_loops:{0} length of string:{1}'.format(number_of_loops, string_length))
        print("elapsed_time:{0}[sec]".format(useOperator(number_of_loops, string_length)))
        print(line*10)
        print('use join method to concatenate strings in list.\n'\
            + 'number_of_loops:{0} length of string:{1}'.format(number_of_loops, string_length))
        print("elapsed_time:{0}[sec]".format(useJoin(number_of_loops, string_length)))
    except IndexError:
        sys.stderr.write(line*5 + 'Error!' + line*5 +'\n' \
            +'Invalid input. This program need 2 inputs : number of loops and length of concatenated string.\n' \
            +'example: python3 concatenationSpeed.py 10000 3\n'+line*10 + '\n')

#余談:競技プログラミングにおける文字列連結の例
100000(=10⁵)回以上の文字列連結を行い、実行時間を争う例としては、競技プログラミングの世界になら例を見ることができる。例えば次のような問題である。

Atcoder Beginner Contest 049 C - 白昼夢
実行時間制限:2s
英小文字からなる文字列 Sが与えられます。Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=Tとすることができるか判定してください。

Tの末尾に dream dreamer erase eraser のいずれかを追加する。
制約1≦|S|≦10⁵ 、Sは英小文字からなる。

引用：Atcoder Beginner Contest 049 C - 白昼夢

ただし、この問題でも1msを争うことは全く無いといっていい。
よりオーダーの大きい問題で、文字列連結の回数が著しく多い場合に頭に置いていく、という程度で良さそうである。