このBlogは移転しました。今後は aish.dev を御覧ください。

internのひみつ

Pythonにはintern()という組み込み関数がある。結構特別扱いで重要な組み込み関数なのだが、使い道が今ひとつ分かりにくいのか知らない人も多いようだ。

intern
<捕虜・危険人物などを>(一定の区域内に)拘禁する, 抑留する.
[新英和(第7版)・和英(第5版)中辞典 株式会社研究社]

なんだか物騒な関数だが、同じような機能を持つLisp族の関数から名前を拝借したのだろう。intern()Pythonスクリプトで書くと、だいたいこんな感じの処理になる。

_intern_map = {}
def intern(s):
    if s in _intern_map:
        return _intern_map[s]
    else:
        _intern_map[s] = s
        s.interned = True
        return s

文字列sと同じ文字列が専用の辞書_intern_mapに登録済みなら登録済みの文字列オブジェクトを返し、未登録ならsを登録してそのままsを返すという単純な処理だ。

intern()を通すと、同じ値の文字列は全て単一の文字列オブジェクトに置き換えることができる。

>>> s1 = "spam spam spam egg and spam"
>>> s2 = "spam spam spam egg and spam"
>>> print id(s1), id(s2)
43966040 43966152
>>> s1 is s2
False
>>> i1 = intern(s1)
>>> i2 = intern(s2)
>>> print id(i1), id(i2)
43966040 43966040
>>> i1 is i2
True

この例では、s1s2はどちらもspam spam spam egg and spamと言う値の、別々の文字列オブジェクトだが、この二つをintern()で変換すると、どちらも同じ文字列オブジェクトを示すように置き換えられる。

このようにintern化した文字列は、==演算子ではなく、is演算子で比較することが出来る。同じ値の文字列は、かならず同じ文字列オブジェクトであることが保証されているからだ。通常の==演算子による比較には文字列長に比例した処理時間が必要だが、isによる比較は文字列長に関係なく、一定の処理時間で済ますことが出来る。

>>> s1 = "a"*100000
>>> s2 = "a"*100000
>>> s1 == s2	# 100000文字分の比較時間が必要
True
>>> i1 = intern(s1)
>>> i2 = intern(s2)
>>> i1 is i2	# 文字列長に関わらず、高速に比較できる
True

intern()による前処理は必要になるが、同じ文字列を何度も比較する場合には処理時間の短縮が期待できる。Pythonの辞書オブジェクトは、intern化された文字列がキーとなっている場合には、自動的に==ではなくisを使って比較するようになっている。

>>> s1 = "spam spam spam egg and spam"
>>> d1 = {s1:1}
>>> d1["spam spam spam egg and spam"]	# ==演算子で要素を比較
1
>>> i1 = intern("spam spam spam egg and spam")
>>> d2 = {i1:1}
>>> d2[i1]	# is演算子で要素を比較
1

という訳でintern()は大量の文字列比較を行う場合の古典的な最適化手法なわけだが、現代のハードウェア環境では意外と役立たずな場合もあるので気を付けていただきたい。

==演算子による文字列比較の処理時間は文字列長に比例するわけだが、なにしろ今時のCPUによる文字列比較はべらぼうに速い。私の手元の環境では、文字列長が10文字以下の場合にはis==有意な速度差を計測することは出来なかった。短い文字列の比較が主体となる場合には、使ってもあまり意味は無さそうである。

ただし、文字列長が短くても、その数が非常に多いとintern()の意味が出てくる。辞書に100万個の文字列キーが存在するようなケースだ。isによる比較のメリットは固定時間で済むことだけではない。文字列を実際にメモリから読み出さずにそのアドレスだけを比較するため、CPUのキャッシュを大量の文字列で汚さないで済むのだ。従って辞書のキーがキャッシュに乗り切れないほどたくさんある場合には、キャッシュミスの減少によるパフォーマンス向上効果がある。