Python bite: string.replace()の性能
Tagged:  •  

文字集合変換のエントリを書いた際に、 社内から:

string.replace()を 使うよりも、 辞書(マップ)+ループの方が計算量が少ないのでは?

という指摘を受けました。

なるほど、 変換候補一覧のサイズ N、 変換対象文字列長を M とした場合、 string.replace() 方式なら O(N x M) ですが、 辞書+ループなら理論上は O(M) で済む筈です。

Python の cgi.escape() が:

s = s.replace("&", "&")
s = s.replace("<", "&lt;")
s = s.replace(">", "&gt;")
cgi.escape() 実装(抜粋)

などという実装だったことと、 「おそらく string.replace() は native 実装」 という期待から、 string.replace() を繰り返し利用する実装としていたのですが、 確かに、 計算量面で勝る「辞書+ループ」方式と、 実際のところどれほど違うのかは具体的に把握していませんでした。

いざという時になって咬まれるよりは、さっさと検証してみましょう。

以下、Python 2.5.1 での実行結果を基にしています。

string.replace() 繰り返しによる変換は、 以下のように実装しました。

def func(target, table):
    for f, t in table:
        target = target.replace(f, t)
    return target
string.replace() 繰り返しによる変換の実装

他方、「辞書+ループ」による変換は、 以下のような実装になります。

def func(target, map):
    converted = []
    for c in target:
        converted.append(map.get(c, c))
    return ''.join(converted)
「辞書+ループ」による変換の実装

変換候補が 256 組、 変換対象の文字列長が 256 文字という条件で、 「必ず変換が発生する(但し対応する候補は、平均的に分散)」場合と、 「全く変換が発生しない」場合の2種類の文字列に対する変換を、 256 回繰り返して性能を計測してみました。

まずは、 string.replace() 繰り返しによる変換での性能です (主要部分の抜粋)。

      131589 function calls in 1.558 CPU seconds

ncalls  tottime  percall  cumtime  percall (function)
131072    0.794    0.000    0.794    0.000 :0(replace)
   512    0.748    0.001    1.542    0.003 bench.py:26(func)

string.replace() 繰り返しによる変換の性能

bench.py:26(func) 行が変換関数そのものの消費時間です。

これに対して、 「辞書+ループ」方式による変換実装での性能は以下のようになりました。

      263173 function calls in 3.082 CPU seconds

ncalls  tottime  percall  cumtime  percall (function)
131072    0.683    0.000    0.683    0.000 :0(append)
131072    0.760    0.000    0.760    0.000 :0(get)
   512    0.016    0.000    0.016    0.000 :0(join)
   512    1.623    0.003    3.082    0.006 bench.py:34(func)

「辞書+ループ」の性能

こちらは bench.py:34(func) 行が変換関数そのものの消費時間です。

辞書検索の :0(get)、 配列拡張の :0(append) が結構な時間を消費している点も注目ですが、 候補対のリストでループを回して string.replace() を起動する bench.py:26(func) よりも、 変換対象でループを回しつつ辞書を引く bench.py:34(func) の方が、 2倍以上時間を消費している点が要注意です。

また、 変換候補対の数をそのまま(256 固定)に、 変換対象文字列長を伸ばした場合、 性能は以下のように推移します。

変換対象文字列長 「replace()」版 「辞書」版 性能比
256 1.558 3.082 1:1.98
512 1.659 5.559 1:3.35
1024 1.827 12.137 1:6.64

結論としては、 変換候補数に対して、 変換対象文字列が十分長い場合は、 string.replace() を繰り返した方が有利といえるでしょう。