にせねこメモ

はてなダイアリーがUTF-8じゃないので移ってきました。

Pythonでの長い文字列の連結は遅い

Python

概要

Python 3で、長い文字列を格納した文字列変数に+=で連結して文字列を保持していると遅い。
文字列のリストとして保持しておいて最後に連結すると速い。

擬似コードでは

# text_iterは文字列を返すiterableオブジェクト
#遅い
out_text = ""
for text in text_iter: 
    out_text += text

#速い
out_list = []
for text in text_iter:
    out_list.append(text)
out_text = "".join(out_list)

背景

Python 3で、テキストファイルを読み込んで、指定の条件に合致した行だけ取り出すというプログラムを書いていた。だが、どうにも実行が遅い。

そのコードでは、ループで行を取り出し、それを文字列変数に+=で結合して保持して、最後にファイルに書き込んでいた。

もしかして、文字列の連結がよくないのでは？と思ったので実験してみた。

実験

沢山の行が含まれるテキストを、各行ごとにループを回し、行の文字列を変数に蓄積していくというプログラムを考える。

一行ずつループを回して、結果を格納していくが、

  1. 文字列変数にどんどん連結していく
  2. list変数にappendしていって、最後に"".joinで連結して文字列にする

という2つの方法が考えられる。この2つを比較してみる。

コード

テストに使ったテキストはhttps://dumps.wikimedia.org/jawiki/20210720/のjawiki-20210720-all-titles.gzを解凍したもので、90MB程度、3778098行ある。これと同じディレクトリに次のpythonコードを入れて実行する。


コードを示す。

# coding: utf-8

import codecs
import time

TEXTFILE = "jawiki-20210720-all-titles"
REPORT_INTERVAL = 100000

if __name__ == '__main__':
    print("Start Processing...")
    out_text = ""
    with codecs.open(TEXTFILE, "r", "utf-8") as f:
        lines = f.readlines()
    
    # 1.
    start_time_1 = time.time()
    n_processed = 0
    out_text = ""
    for line in lines:
        out_text += line
        n_processed += 1
        if n_processed % REPORT_INTERVAL == 0:
            print(n_processed, "lines processed")
    elapsed_1 = time.time() - start_time_1
    print(len(out_text))

    # 2.
    out_list = []
    n_processed = 0
    start_time_2 = time.time()
    for line in lines:
        out_list.append(line)
        n_processed += 1
        if n_processed % REPORT_INTERVAL == 0:
            print(n_processed, "lines processed")
    out_text = "".join(out_list)
    elapsed_2 = time.time() - start_time_2
    print(len(out_text))
    
    print("str_concat:", elapsed_1, "sec")
    print("list:", elapsed_2, "sec")

これを実行する。


それで、最初に文字列の結合によるものをやっているが、出力の間隔を見ているとどんどん遅くなっていくのが分かる。
最後に出力される結果を見ると、

str_concat: 519.9358415603638 sec
list: 0.746680736541748 sec

…うそやろ!?…となっていて、378万回弱の文字列の連結は8分以上かかっている一方、リストへの追加は1秒未満で終わっていることがわかる。その差約700倍…

実験した環境は、

である。

ちなみに、同じPCでCygwin上のPython 3.8.9で実行した場合は

str_concat: 93.5771963596344 sec
list: 0.7298173904418945 sec

とかで、それでも100倍以上の差はある。

考察

文字列の+による連結は非破壊的操作なので、毎回結合後の文字列全体を新しい値として生成してメモリに格納してるので遅いということなのかなと思う。
list.appendは破壊的操作なので、新しく追加する部分だけ処理すればいいので速い。

結論

長いテキストを処理するときに、処理後のテキストを保持するのには、連結して文字列で保持すると遅く、文字列のlistで保持して後で"".joinした方が速い。