読者です 読者をやめる 読者になる 読者になる

シーケンスの一部を反転する

Python

 ちょっと時間がたってしまいましたが、id:morchinさんのエントリとそのコメント欄で興味深い議論が行われています。感想を述べるには出遅れた感があるのですが、一応書いておきます。

  • reverse()メソッドの問題点

http://d.hatena.ne.jp/morchin/20061028


 morchinさんの問題提起とその背景は、完全に理解したわけではありませんが、「シーケンスの一部を反転したい」が「シーケンスをスライシングをする時に、新たなインスタンスが発生するので効率が悪い」ということにあると思われます。
 この一連の議論・コメントの中で、出てきた解決策を、一部改変して、列挙しておきます。
 以下の解法A, B, Cは、リストの最初の3つの要素を反転させています。例えば[1, 2, 3, 4, 5]は[3, 2, 1, 4, 5]になります。

# 解法A
L[:3] = L[:3][::-1]
# 解法B
L[:3] = reversed(L[:3])
# 解法C
def g(L, e, s):
    while 1:
        e -= 1
        yield L[e]
        if e == s:
            break

L[:3] = g(L, 3, 0)

 「完全に理解したわけではない」という断り書きを入れたのは、僕の感覚では、(非常に短い)リストの生成がボトルネックになるとは思えないからです。
 上の3つの解法は、時間効率で言うと、A>B>Cとなることが予想できます。理由は解法Aは式しか含まないのに対して、解法Bでは関数呼び出しが行われており、解法Cではさらにgeneratorを使っているためです。
 一般的に言って、このケースのように、消費側(generatorを使う側)が活動を開始する前提として、生産者側(generator側)の生成物をすべてを要求する場合、generatorを使用することはコストがかかりすぎます。(さらに言うならば、そもそも、generatorを使用する必要がありません。)


 実際に、range(10)で生成したリストに上の解法を10000回適用した時の処理時間を測定してみました。

解法 処理時間(sec)
A 0.11417198181152344
B 0.16490888595581055
C 0.2936551570892334


 generatorを使った解法は、スライス式を使った解法の約3倍の時間がかかっています。
 やはり、Pythonプログラムの時間効率を改善したいならば、(メモリプールから割り当て済みの領域を取り出すだけの)インスタンス生成よりも、関数・メソッドの呼び出しの方を気にかけるべきだと思われます。


 では、generatorを使った解法が期待した通り、リスト・インスタンスを生成せず、メモリ効率を改善しているかというと、改善していません。
 なぜなら、C実装の内部でgeneratorからtupleが生成されているので、上の解法Cは、実質的には次のPythonコードと同等になってしまうからです。

L[:3] = tuple(g(L, 3, 0))

 Pythonにはlist, tuple, generatorのようなシーケンス・プロトコル・オブジェクトを渡して呼び出す関数が多数あります。例えば、次のようなものです。

>>> ' '.join(['spam', 'spam', 'egg'])
'spam spam egg'

>>> reversed(['spam', 'spam', 'egg'])
<listreverseiterator object at 0x535550>

>>> map(lambda x : x.upper(), ['spam', 'spam', 'egg'])
['SPAM', 'SPAM', 'EGG']

 これらの関数にgeneratorを渡しても動作しますが、list, tupleを渡した方が、高速に動作します。なぜなら、generatorを渡しても、結局、内部でtupleに変換されるので、この分のオーバーヘッドが生じるためです。
 これは、Python C APIでシーケンスを扱う場合、シーケンスがlist/tupleであることを保証した上で、list/tupleの保持するCの配列に逐次アクセスした方が時間効率がよいためであり、CPythonの組み込み関数・オブジェクト、拡張モジュールは一貫してこの方針で実装されています。


 まとめ。

  • 関数呼び出しよりも式で表現しよう。
  • generatorを使うときには、本当に使う必要があるのか考慮しよう。