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

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 の初期化処理をリファクタリングして再計測しました

.@t2y URL [0 for i in xrange(len(seqs))] みたいな書き方たまに見かけるけど、正解は [0]*len(seqs) だと思う。

2011-02-07 16:42:16 via web

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

-    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 でさらに詳しく解説してくれました。

さらに

@t2y range(0, max) もrange(max)で良いんじゃないかな、と重箱の隅を（ｒｙ

2011-02-07 19:43:09 via TweetDeck to @t2y

だそうな(> <)

#!/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