西尾泰和のブログ @ Cybozu Labs

どうも、ご無沙汰です。 このブログをはじめた当初は「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
119906

1万件のリストをソートする過程で、 「比較のための関数」は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)」と書けるようです。

Pythonで実装してみました。

404 Blog Not Found:Code Snippets - reduce(l|r)を実装汁!

解答は下のようになります。

>>> reducel = reduce
>>> reducer = lambda f, xs: reduce(lambda y, x: f(x, y), reversed(xs))

動作を確認してみましょう。

>>> concat = lambda x, y: "(%s#%s)" % (x, y)
>>> reducer(concat, range(1, 5))
'(1#(2#(3#4)))'
>>> reducel(concat, range(1, 5))
'(((1#2)#3)#4)'

解説は後で書きます。

= ちなみにHaskellでは、まともに書くと下のようになってとても悲しいです。

reducer = foldr1
reducel = foldl1 

そこであえてfoldを封じてみると下のようになります。

reducer::(String->String->String)->[String]->String
reducer f [x] = x
reducer f (x:xs) = f x $ reducer f xs

reducel::(String->String->String)->[String]->String
reducel f [x, y] = f x y
reducel f (x:y:xs) = reducel f $ f x y :xs 

= PythonのreduceはHaskellのfoldlに相当するのですが foldrに相当する組み込みの関数はありません。 そこで、リストをreversedを使ってひっくり返し、 関数の引数の順番もひっくり返してreduceを使っています。

reducer = lambda f, xs: reduce(lambda y, x: f(x, y), reversed(xs))

ここで重要なのはxs.reverse()ではなく reversed(xs)を使うというところです。 reversed(xs)はxs.reverse()を関数型言語っぽく書くための飾りだというとらえ方を されている人もいるようですが、違います。 実際に10万件のリストをひっくり返すのにかかる時間を計ってみると reversed(xs)の方が100倍近く速い、という桁違いの差が出ていることがわかります。 (statとTimerに関しては西尾泰和のブログ @ Cybozu Labs: Python2.4以降での高速なソートを参照)

>>> stat(Timer("xs.reverse()", "xs = range(100000)").repeat(100, 100))
(0.039828419533763509, 0.0018198081738915054)
>>> stat(Timer("reversed(xs)", "xs = range(100000)").repeat(100, 100))
(0.00038362976300049923, 0.00013374982828255732)

なぜでしょうか？これはreversed(xs)が何を返しているのか見てみるとわかります。

>>> reversed(range(100))
<listreverseiterator object at 0x00DC46F0>

xs.reverse()はそこで実際にリストの中身を書き換えてしまうのに対し、 reversed(xs)は単に「リストに逆順でアクセスするイテレータ」を作っているわけです。

どうも、Java勉強中の西尾です。 Javaって難しいですね…。 今日はようやくリストを作る方法を理解したので、 自分の勉強のためにまとめてみたいと思います。 普段Pythonの記事ばっかりなのでたまには気分を変えて。

Pythonでは「複数のオブジェクトが入った配列のようなオブジェクト」を下のような記法で作成できます。

>>> xs = [1, 2, 3.14, "Hello!"] 

JavaScriptやRubyでも同じで、Perlだと@xs = (1, 2, 3.14, "Hello")になるようです。

また、このオブジェクトの中身を順に表示するにはfor文を使います。

>>> for x in xs:
        print x

        
1
2
3.14
Hello! 

これと同じことをJavaではどう書けばいいのか、 今日やっと理解しました。 Javaでは下のようになります。

Object[] xs = { 1, 2, 3.14, "Hello!" };
for (Object x : xs) {
        System.out.println(x);
}

ただ、これではxsが配列なので、 Pythonでは下のように書ける「アイテムの追加」などができません。

>>> xs = [1, 2, 3.14, "Hello!"]
>>> xs.append("Java")
>>> xs
[1, 2, 3.1400000000000001, 'Hello!', 'Java']

アイテムの追加などが可能なオブジェクトにするために、 Collectionインターフェイスを実装したクラス (Collection (Java 2 Platform SE 5.0)) のオブジェクトを作りたいと思います。 それにはArrays.asListを使います。

Vector<Object> xs = new Vector<Object>(Arrays.<Object>asList(1, 2, 3.14, "Hello!"));

Arrays.asListに配列を渡すと、List(これはCollectionの子インターフェイス)を 実装したクラス(Arrays$ArrayList)のオブジェクトを返してくれます。 なので下のように配列を渡しても上と同じことができます。

Arrays.asList(new Object[]{ 1, 2, 3.14, "Hello!"})

可変長引数でも渡せるので、実際に配列を作る必要はなく、 配列を作るための呪文「new Object[]{～}」が省けます。 ただしその場合「これらがObject型である」という情報が失われてしまうので、 それを補うために「Arrays.<Object>asList」と指定しています。

さて、これでListを作るところまではできたのですが、 残念ながらここで作られるListのaddメソッドを呼ぶと、 「サポートされていない」という趣旨の例外が発生します。 (UnsupportedOperationException)

おそらく、配列をListに詰め替えているのではなく、 単にListに見えるラッパをかぶせているだけなのでしょう。 そこでVectorに詰め替えます。 VectorのコンストラクタにCollectionを渡した場合には、 中身の詰め替えが行われます。 正確に言うならば、仕様にはそういうことは書かれていない (どころか、返ってくるリストがArraysのprivateなインナークラスなのでそもそも以下略) のでソースコードを追うことになります。 Vectorのコンストラクタで、渡されたCollectionのtoArrayを呼ぶのですが、 Arrays$ArrayListのtoArrayは自分の持っている配列をcloneして返すので、 この時点で詰め替えが行われます。

さてこれで追加や削除ができるようになりました。 ここでクイズです。下のコードを実行するとどういう出力が出るでしょうか？

Vector<Object> xs = new Vector<Object>(Arrays.<Object>asList(1, 2, 3.14, "Hello!"));
xs.remove(3.14);
xs.remove(1);
xs.set(1, "newItem");
xs.add(1, 999);
xs.add("Java");
Collections.reverse(xs);
for (Object x : xs) {
        System.out.println(x);
}

ヒント、Pythonで書くとこうなります。

>>> xs = [1, 2, 3.14, "Hello!"]
>>> xs.remove(3.14)
>>> xs.pop(1)
2
>>> xs[1] = "newItem"
>>> xs.insert(1, 999)
>>> xs.append("Java")
>>> xs.reverse()
>>> for x in xs:
	print x

解答。

Java
newItem
999
1

出力結果に「1」が入っているのが意外です。 実はxs.remove(3.14);とxs.remove(1);ではremoveの意味が違い、 前者は「3.14という値を取り除く」のに対し、後者は「1番目の位置の値を取り除く」 になっています。 いやはや、Javaは奥が深いですね。

追記： なぜこういう現象が起きるのかについて解説します。remove(int)とremove(Object)の両方のメソッドがあって、リテラルの1は(過去の諸々のしがらみによって)int型なのでremove(1)はremove(int)が呼ばます。一方リテラルの3.14はオートボクシングでObjectになるのでremove(Object)の側が呼ばれます。もしremove(Object)で1を削除したければ 明示的にxs.remove(new Integer(1));と書く必要があります。

ご指摘どうもありがとうございます＞Yのほぼコード置場 - Re:Javaでリストとか(ry