IPython で簡単プロファイリング

python profile

methane のつぶやき を見て IPython で timeit を使用すると、簡単に実行時間を計測することができるのを知りました。

例えば、[1,3,2,3,4,1,5] -> [1,3,2,4,5] のような、同じ値を含むリストから順序を保持した上で重複を取り除きたいときに色んな実装が考えられます。

  • 結果リストに存在するかを in 演算子を使用して調べる実装
  • enumerate と index メソッドを使用して調べる実装
  • 結果リストに存在するかを bitmap を使用して調べる実装
#!/usr/bin/env python

import random

def make_data(max, num):
    results = []
    for i in range(10):
        results += (random.sample(range(0, max), num))
    return results

data_100 = make_data(100, 10)
data_10000 = make_data(10000, 1000)

print 'data_100, all: ', len(data_100), 'uniq: ', len(set(data_100))
print 'data_10000, all: ', len(data_10000), 'uniq: ', len(set(data_10000))

def keep_order_uniq1(seqs):
    results = []
    for seq in seqs:
        if seq not in results:
            results.append(seq)
    return results

def keep_order_uniq2(seqs):
    return [ seq for i, seq in enumerate(seqs) if seqs.index(seq) == i ]

def keep_order_uniq3(seqs):
    bitmaps = [ 0 for i in range(len(seqs)) ]
    results = []
    for seq in seqs:
        if bitmaps[seq] == 0:
            results.append(seq)
            bitmaps[seq] = 1
    return results

実行結果。

In [1]: from remove_dup import *
data_100, all:  100 uniq:  67
data_10000, all:  10000 uniq:  6490

In [2]: timeit -n 10 keep_order_uniq1(data_100)
10 loops, best of 3: 135 us per loop

In [3]: timeit -n 10 keep_order_uniq2(data_100)
10 loops, best of 3: 194 us per loop

In [4]: timeit -n 10 keep_order_uniq3(data_100)
10 loops, best of 3: 44.5 us per loop

In [5]: timeit -n 10 keep_order_uniq1(data_10000)
10 loops, best of 3: 1.13 s per loop

In [6]: timeit -n 10 keep_order_uniq2(data_10000)
10 loops, best of 3: 1.48 s per loop

In [7]: timeit -n 10 keep_order_uniq3(data_10000)
10 loops, best of 3: 3.88 ms per loop

対象とするデータ量や要件にも依りますが、この場合 bitmap を使用する方が高速に動作することが分かります。また Django では、IPython がインストールされていると、対話型インタープリタが自動的に IPython になります。ちょっとした実装のプロファイルや既存関数のリファクタリングにとても便利です。 

# ./manage.py shell
Python 2.4.3 (#1, Sep  3 2009, 15:37:12) 
Type "copyright", "credits" or "license" for more information.

IPython 0.10 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object'. ?object also works, ?? prints more.

In [1]:

kou さんのコメントから追記。
上述の keep_order_uniq3() はリストが「0から始まり、且つ要素が連続している」という前提条件がありました。その意味では keep_order_uniq1() や keep_order_uniq2() と比較するのはフェアじゃないですね。bitmaps を辞書にしました。

def keep_order_uniq4(seqs):
    bitmaps = {}
    for seq in seqs:
        bitmaps.update([(seq, 0)])
    results = []
    for seq in seqs:
        if bitmaps[seq] == 0:
            results.append(seq)
            bitmaps[seq] = 1 
    return results

実行結果。

In [2]: l = [1]

In [3]: keep_order_uniq4(l)
Out[3]: [1]

In [4]: l = [1,3,5,3,1]

In [5]: keep_order_uniq4(l)
Out[5]: [1, 3, 5]

In [6]: timeit -n 10 keep_order_uniq3(data_10000)
10 loops, best of 3: 3.81 ms per loop

In [7]: timeit -n 10 keep_order_uniq4(data_10000)
10 loops, best of 3: 17.3 ms per loop

リストよりは少し時間がかかりますね。

2011/2/6 追記 コードをリファクタリングして再計測しました

Pythonのリスト内包表記でRubyのuniqメソッドと同じ事をする - logging.info(self) で話題になっているのを読んで、自分のコードを見返したのでリファクタリングしました。

2011/2/7 追記 bitmaps の初期化処理をリファクタリングして再計測しました

と正解を教えて頂いたのでさらにリファクタリングしました。

-    bitmaps = [0 for i in xrange(len(seqs))]
+    bitmaps = [0] * len(seqs)

6.6. シーケンス型 str, unicode, list, tuple, buffer, xrange の注釈2によると、後者の方が初期値の要素をリストの長さ分作成しないので効率が良さそうです。実際、実行結果も 3.48 ms から 2.49 ms に速くなりました。http://d.hatena.ne.jp/nishiohirokazu/20110207/1297067116 でさらに詳しく解説してくれました。

さらに

だそうな(> <)

#!/usr/bin/env python

import random

def keep_order_uniq1(seqs):
    """
    >>> l = [1,3,5,3,1]
    >>> keep_order_uniq1(l)
    [1, 3, 5]
    """
    results = []
    for s in seqs:
        if s not in results:
            results.append(s)
    return results

def keep_order_uniq2(seqs):
    """
    >>> l = [1,3,5,3,1]
    >>> keep_order_uniq2(l)
    [1, 3, 5]
    """
    return [s for num, s in enumerate(seqs) if seqs.index(s) == num]

def keep_order_uniq3(seqs):
    """
    >>> l = [1,3,2,3,1]
    >>> keep_order_uniq3(l)
    [1, 3, 2]
    """
    bitmaps = [0] * len(seqs)
    results = []
    for s in seqs:
        if bitmaps[s] == 0:
            results.append(s)
            bitmaps[s] = 1
    return results

def keep_order_uniq4(seqs):
    """
    >>> l = [1,3,5,3,1]
    >>> keep_order_uniq4(l)
    [1, 3, 5]
    """
    bitmap = {}
    results = []
    for s in seqs:
        if not bitmap.get(s):
            results.append(s)
            bitmap[s] = True
    return results

def make_data(max, num):
    results = []
    for i in range(10):
        results += (random.sample(range(max), num))
    return results

data_100 = make_data(100, 10)
data_10000 = make_data(10000, 1000)

実行結果。

In [2]: timeit -n 10 keep_order_uniq1(data_10000)
10 loops, best of 3: 1.14 s per loop

In [3]: timeit -n 10 keep_order_uniq2(data_10000)
10 loops, best of 3: 1.48 s per loop

In [4]: timeit -n 10 keep_order_uniq3(data_10000)
10 loops, best of 3: 2.49 ms per loop

In [5]: timeit -n 10 keep_order_uniq4(data_10000)
10 loops, best of 3: 5.98 ms per loop

リファレンス:
IPython の timeit で実行時間計測 - 人生いきあたりばったりで生きてます@はてな
Pythonの配列操作 - methaneのブログ
順序を保持するuniq - Pythonで遊ぶよ - pythonグループ
珠玉のプログラミングのお題を python で書いてみた : 1 - forest book
django-admin.py と manage.py — Django v1.0 documentation