Python2.4以降での高速なソート
どうも、ご無沙汰です。
このブログをはじめた当初は「1日1エントリー公開しよう」
などともくろんでいたのですが、はやくも2週間以上間が空いてしまいました。
今回の話はCPythonにバージョン2.4から追加された機能についてです。 みなさんは、例えば「タプルの入ったリストを、そのタプルの2番目の要素でソートしたい」とか 「Entryオブジェクトのリストを、その属性updateTimeの値に従ってソートしたい」という場合、 どうしていますか？
まずは2.3以前から可能だった 「sortメソッドに比較用の関数を渡す方法」の実行にかかる時間を調べてみます。
# sortメソッドに比較用の関数を渡す方法 d.sort(lambda x, y: cmp(x[1], y[1]))実行時間の測定にはtimeitモジュールを使います。 (10.10 timeit -- 小さなコード断片の実行時間計測) ソートのコードと、ソートの前の準備のためのコードを渡してTimerオブジェクトを作ります。 ソートの対象はランダムな実数2つのタプルが10000個入ったリストです。
>>> setup = """ from random import random d = [(random(), random()) for i in range(10000)] """ >>> import timeit >>> t = timeit.Timer( stmt = "d.sort(lambda x, y: cmp(x[1], y[1]))", setup = setup)このTimerオブジェクトのrepeatメソッドを呼び出すと、 指定された回数の繰り返し実行をして、結果がリストで返されます。 リストの平均と標準偏差を計算する関数も作っておきます。
>>> def stat(xs):
sx = sum(xs)
sxx = sum(x * x for x in xs)
n = len(xs)
ave = sx / n
from math import sqrt
sd = sqrt((sxx - sx * sx / n) / (n - 1))
return ave, sd
>>> stat(t.repeat(100, 1))
(0.12305972965843466, 0.0021971415527818798)
ちなみにrepeatメソッドには2つの引数(100, 1)が渡されていますが、
これは「『setupを実行した後1回stmtを実行する』というのを100回実行する」
という意味です。
一度ソートしたリストを何度もソートしたのでは目的のものが計れないので、
1回データを作るごとに1回だけソートするようにしています。
さて、結果は(0.123, 0.002)と出ましたね。 10000個のリストをソートするのに、平均0.123秒かかっていることがわかります。
次は「あらかじめソートのキーが一番前に来るようなリストを作ってそれをソートする」 という方法です。
d2 = [(v[1], v) for v in d] d2.sort() d = [v for (v1, v) in d2]バージョン2.4から導入された組み込み関数sortedを使うと1行で書けます。
d = [v for (v0, v) in sorted([(v[0], v) for v in d])]この方法は「無駄なことをしている雰囲気」が漂うため遅いだろうと思われがちですが、 実際に計ってみると意外と速いです。
>>> stmt = """ d2 = [(v[1], v) for v in d] d2.sort() d = [v for (v1, v) in d2] """ >>> t = timeit.Timer( stmt = stmt, setup = setup) >>> stat(t.repeat(100, 1)) (0.026985818029788788, 0.0014615299209264103)1万件のリストのソートで、こちらのほうが6倍速いですね。 これはなぜでしょうか？
それは「比較のための関数」が何度呼ばれているのか調べてみるとわかります。
>>> class MyCmp(object): count = 0 def __call__(self, x, y): self.count += 1 return cmp(x, y) >>> myCmp = MyCmp() >>> [(random(), random()) for i in range(10000)].sort(myCmp) >>> myCmp.count 1199061万件のリストをソートする過程で、 「比較のための関数」は12万回呼び出されています。 関数の呼び出しはコストが高いので、 こういう大きいリストのソートをするときに 「比較のための関数」を与えるよりは、 「比較のためのリスト」を作ってしまう方が安上がりなのです。
さて、ここからが本題です。 バージョン2.4からはsortに 「『比較のためのリスト』を作るための関数」を渡せるようになりました。
d.sort(key = lambda x: x[1])2番目の方法より実行にかかる時間が短く、コードの量も少ないです。
>>> t = timeit.Timer(stmt = "d.sort(key = lambda x: x[1])", setup = setup) >>> stat(t.repeat(100, 1)) (0.021949049390459548, 0.0010707450967945632)現時点ではこれが最良の選択肢でしょう。
追記： 肝心なことを書くのを忘れていました。 こういう情報はいったいどこで見つけてくるのか、という話。 Pythonライブラリリファレンスの第2章には一度目を通しておくことをおすすめします。 2.3.6.4 変更可能なシーケンス型
追記2： Pythonライブラリリファレンスは何度読んでもまだ発見があるかも知れませんね。 3.10 operator -- 関数形式の標準演算子。 「lambda x: x[1]」は「itemgetter(1)」と書けるようです。
