リストからディクショナリへの変換の最適化にみる賢明な Python プログラミング

Python クックブック第2版「4.12 キーと値が交互に入ったリストから dict を構築」というレシピがあります。
原典: Dicts from lists « Python recipes « ActiveState Code

リストからディクショナリを生成する方法として、zip() と dict() 関数を組み合わせた簡潔な方法を紹介しています。

def DictFromList(myList):
    return dict(zip(myList[:-1:2], myList[1::2]))

これは簡潔で素晴らしいなと感心していたら、コメント(クックブック)には、この方法よりも高速且つ汎用性の高い方法として、ジェネレータを用いた方法も紹介されていました。

def pairwise(iterable):
    itnext = iter(iterable).next
    while 1:
        yield itnext(), itnext()

イテラブルなシーケンスに対して適用できるので汎用性が高くなり、ジェネレータを用いることで巨大なリストからの変換に対してメモリの消費量も少なくなります。クックブックの考察によると、このコードにはさらにもう1つトリックがあるようです。以下に引用します。

pairwise はちょっとおもしろい実装になっている。第1文では、引数 iterable に対してビルトイン関数 iter をコールし、これにより得られる反復子の結合メソッド next を、ローカル名 itnext に結合している。ちょっと奇妙に思われるかもしれないが、Python では一般性が高く、良いテクニックである。あるオブジェクトが存在し、このオブジェクトに対してやりたいことが、ループ中での結合メソッドのコールのみであれば、そのメソッドを抽出、ローカル名に代入しておき、このローカル名を関数であるかのようにコールするのだ。
Amazon.co.jp： Python クックブック第2版: Alex Martelli, Anna Martelli Ravenscroft, David Ascher, 鴨澤眞夫, 當山仁健, 吉田聡, 吉宗貞紀: 本

上記のコードと動作は同じですが、以下のコードは処理速度が約60%遅くなるとあります。

def pairwise_slow(iterable):
    it = iter(iterable)
    while 1:
        yeild it.next(), it.next()

さらにクックブックを引用します。

シンプルさと明白性に焦点を合わすのは良いこと、というか素晴らしいことだ - 実際それは Python の中心原則である。しかし何の見返りもなくパフォーマンスを投げ捨てることは、まったく別の話であり、どんな言語においても推奨されることのない習慣だ。つまり、正しくクリアでシンプルなコードを書くことに注力するのは素晴らしいことだが、自分のニーズに最も適切な Python イディオムを学んで使うことも、極めて賢明なことなのだ。
Amazon.co.jp： Python クックブック第2版: Alex Martelli, Anna Martelli Ravenscroft, David Ascher, 鴨澤眞夫, 當山仁健, 吉田聡, 吉宗貞紀: 本

良いレシピに出会えて幸せな気分ですね(^ ^;;
以下に、私の環境(MacOS X 10.5.8, 2GHz Core2Duo, 2GB 667MHz DDR2)における、リストの要素1万、100万、1000万のときの各々の方法によるプロファイル結果を Python2.6 と Python3.1 で計測してみました。リストの要素数が大きくなるにつれて、処理速度に差が出ることが分かります。
また、リスト要素1000万のときの、Python2.6 と Python3.1 のプロファイル結果を見ると、Python3.1 では大幅に改善されていることが見て取れます。

実行結果。

$ python2.6 profile_time_convert_dict26.py 
Running dict_from_list which has 10000 items took 0.010 seconds
Running dict_from_sequence which has 10000 items took 0.000 seconds
Running dict_from_list which has 1000000 items took 0.960 seconds
Running dict_from_sequence which has 1000000 items took 0.350 seconds
Running dict_from_list which has 10000000 items took 57.260 seconds
Running dict_from_sequence which has 10000000 items took 3.390 seconds

$ python3.1 profile_time_convert_dict31.py 
Running dict_from_list which has 10000 items took 0.004 seconds
Running dict_from_sequence which has 10000 items took 0.002 seconds
Running dict_from_list which has 1000000 items took 0.742 seconds
Running dict_from_sequence which has 1000000 items took 0.317 seconds
Running dict_from_list which has 10000000 items took 8.648 seconds
Running dict_from_sequence which has 10000000 items took 3.478 seconds

python2.x のソースコード。

#!/bin/env python

import time
import random

item_num = [10000, 1000000, 10000000]

def main():
    get_profile(item_num, dict_from_list, dict_from_sequence)

def get_profile(num_list, *funcs):
    totals = {}
    for num in num_list:
        kav_list = [ i for i in range(num) ]
        for func in funcs:
            totals[func] = 0.0
            starttime = time.clock()
            apply(func, [kav_list])
            stoptime = time.clock()
            elapsed = stoptime - starttime
            totals[func] = totals[func] + elapsed
             
            print "Running %s which has %d items took %.3f seconds" % (
                func.__name__, num, totals[func])

def dict_from_list(key_and_values):
    return dict(zip(key_and_values[::2], key_and_values[1::2]))

def dict_from_sequence(seq):
    def pairwise(iterable):
        itnext = iter(iterable).next
        while True:
            yield itnext(), itnext()
    return dict(pairwise(seq))

if __name__ == '__main__':
    main()

python3 のソースコード。

#!/bin/env python

import time
import random

item_num = [10000, 1000000, 10000000]

def main():
    get_profile(item_num, dict_from_list, dict_from_sequence)

def get_profile(num_list, *funcs):
    totals = {}
    for num in num_list:
        kav_list = [ i for i in range(num) ]
        for func in funcs:
            totals[func] = 0.0
            starttime = time.clock()
            func(*[kav_list])
            stoptime = time.clock()
            elapsed = stoptime - starttime
            totals[func] = totals[func] + elapsed
             
            print("Running %s which has %d items took %.3f seconds" % (
                func.__name__, num, totals[func]))

def dict_from_list(key_and_values):
    return dict(list(zip(key_and_values[::2], key_and_values[1::2])))

def dict_from_sequence(seq):
    def pairwise(iterable):
        itnext = iter(iterable).__next__
        while True:
            yield itnext(), itnext()
    return dict(pairwise(seq))

if __name__ == '__main__':
    main()

2to3 の diff。

$ 2to3 -w -n profile_time_convert_dict31.py
RefactoringTool: Skipping implicit fixer: buffer
RefactoringTool: Skipping implicit fixer: idioms
RefactoringTool: Skipping implicit fixer: set_literal
RefactoringTool: Skipping implicit fixer: ws_comma
 --- profile_time_convert_dict31.py (original)
 +++ profile_time_convert_dict31.py (refactored)
 @@ -15,20 +15,20 @@ 
          for func in funcs:
              totals[func] = 0.0
              starttime = time.clock()
 -            apply(func, [kav_list])
 +            func(*[kav_list])
              stoptime = time.clock()
              elapsed = stoptime - starttime
              totals[func] = totals[func] + elapsed
               
 -            print "Running %s which has %d items took %.3f seconds" % (
 -                func.__name__, num, totals[func])
 +            print("Running %s which has %d items took %.3f seconds" % (
 +                func.__name__, num, totals[func]))
 
  def dict_from_list(key_and_values):
 -    return dict(zip(key_and_values[::2], key_and_values[1::2]))
 +    return dict(list(zip(key_and_values[::2], key_and_values[1::2])))
  
  def dict_from_sequence(seq):
      def pairwise(iterable):
 -        itnext = iter(iterable).next
 +        itnext = iter(iterable).__next__
          while True:
              yield itnext(), itnext()
      return dict(pairwise(seq))
 RefactoringTool: Files that were modified:
 RefactoringTool: profile_time_convert_dict31.py