2010年9月21日火曜日

なぜPythonの割り算はC言語と違う方式なのか?

今日は何度も「なぜPythonの整数の割り算はC言語のようにゼロに向けて丸めるのではなく、切り捨てなのか?」と聞かれた。

数値が両方とも正の場合には、何も驚くようなことは発生しない。

>>> 5//2
2

しかし、どちらかの数値が負の場合、結果は切り捨てられる。言い換えると、ゼロから遠い方向(負の無限大方向)に向けて丸められる。

>>> -5//2
-3
>>> 5//-2
-3

この挙動は何人かの人を混乱させたようであるが、このような実装になっているのは数学的な根拠がある。整数の割り算の演算子(//)と、その弟の余りを計算する演算子(%)は、次のような数学的な関係を保っている。すべての変数は整数とする。

a/b = q あまり r

これは、次のような関係性を持っている。

b * q + r = a かつ 0 <= r < b
(ただし、a, bはともに0以上の整数)

もしも、この式の関係性を、負の数値まで拡張したいのであれば、2つの選択肢があります。もし商をゼロに向けて丸めるのであれば、付帯条件を0 <= abs(r)と変更する必要がある。それ以外には、qを負の無限大の方に向けて丸める方法がある。この場合、付帯条件は0 <= r < bのままである。

数学の整数論を考えると、数学者はいつも後者の選択を望ましいと考えてきた(Wikipedia参照)。この方式の割り算が役に立つ、おもしろい利用方法がいくつかあったので、Pythonでもこの後者の挙動を採用した。POSIXのタイムスタンプ(1970年からの経過の秒数)を取得して、時刻に変える、という場面を考えてみる。1日は24時間なので、24 * 3600 = 86400秒ある。これを計算するには、単にt % 86400とやれば良い。しかし、1970年依存のより前の時刻を計算したいと考えると、ゼロ方向に丸めてしまうと、無意味な結果が帰ってくることになる。負の無限大方向に丸めるというルールであれば、このような場面でも、そのまま適用できる。

コンピュータグラフィックスで、ピクセルの位置を計算する場面でも、同じ事が言える。こちらの方が良く発生するだろう。

もしbが負の値をであれば、すべてが逆さまになる。普遍条件は次のようになる。

0 >= r > b.

それでは、なぜC言語はこのような実装になっていないのだろうか?それは、Cが設計された当時のハードウェアがこのようにしていなかったからである。そして、現在では負の数は補数として表現されているが、当時のコンピュータは少なくとも整数に関しては、「符号+大きさ」という表現になっていた。私が最初に触れたコンピュータはデータを制御するメインフレームであったが、浮動小数点数と同じく、整数に補数を使うようになっていた。そのハードは負のゼロを表すパターンが60個もあったのである!

Pythonの浮動小数点数を完全に知り尽くしているTim Petersは、これらの規則を浮動小数点数の割り算にも広げたいという私の願望に対して、いくつか心配に思っていることを説明してくれた。彼の心配は正しかった。負の無限大の方向に丸めるというルールは、x%1.0という式があったときに、xが非常に小さい負の整数の時に精度が失われてしまうのである。しかし、これは整数の割り算を破壊するものではなく、//はそれに密に結合されている。

PS. 上記の説明では、/の代わりに//を使用した。これはPython 3の文法で、Python 2でも割り算が整数領域で行われるのを強調したいときに利用できる。Python 2の/演算子は、演算する数が両方整数か、一つ以上浮動小数点数が含まれているかで型が変わるという曖昧なところがある。しかし、これに関してはまったく別の話なので、ここでは説明しない。詳しくはPEP 238に書かれている。

2010年9月8日水曜日

リスト内包表記〜ジェネレータ式

リスト内包表記はPython 2.0で追加された。この機能はGreg Ewingによるパッチを元にして、Skip MontanaroとThomas Woutersらの貢献もあって実現された。私の記憶が正しければ、Tim Petersもこのアイディアをしっかりと保証してくれた。基本的には、リスト内包表記は数学者によって使用されてきた、よく知られた表記法をPythonicに解釈して実現したものである。

{x | x > 10}

これは、一般に、10より大きな数の集合と解釈される。数学の世界では、この形式は、例えば全ての実数、全ての整数などを表す普遍集合(universal set)であると、読み手は解釈する。Pythonの2.0には普遍集合の概念はなく、setもなかった。setについてもおもしろい話があるため、将来ブログに投稿することになるだろう。

この概念や、他の状況も踏まえ、次のようなPython流の表記が作られた:

[f(x) for x in S if P(x)]

これを実行すると、シーケンスSに含まれる値のうち、述部Pの評価結果に合う要素に対して、関数fを適用した結果を含むリストが生成される。if節はオプションとなっているし、また、for節を複数入れて、それぞれにif節を書いて、ネストされたループを表現することもできる。ただし、このネストされたループはあまり使われることはない。一般的には多次元の要素を、1次元のリストにマップすることが良く行われる。

リスト内包表記は、組み込み関数のmap()filter()の代替手段となっている。map(f, S)は、[f(x) for x in S]と同じ意味となるし、filter(P, S)[x for x in S if P(x)]と同じ意味となる。map()filter()を使った表現の方がコンパクトであるため、リスト内包表記の方が推奨されていないのでは?と思う人もいるだろう。しかし、より現実的なサンプルを見ると見解が変わるだろう。与えられたリストの全ての要素に数字の1が足された、新しいリストを作りたいとする。リスト内包表記を使った場合には、[x+1 for x in S]と表現できる。map()を使うと、map(lambda x: x+1, S)となる。"lambda x: x+1"はインラインで無名関数を作るPythonの書き方である。

ここでの本当の問題はPythonのラムダ記法が冗長すぎることで、この表記がもっと簡潔になればmap()を使った記法がより魅力的になるはずだ、ということがずっと主張されてきた。私個人の見解としてはこれには反対である。リスト内包表記の方が、特にマップされる式の複雑さが増加するとmap()を使った関数表記よりも見やすくなることが分かったからである。それに加えて、リスト内包表記を使った方が、実行速度の面からも、map()とラムダを使うよりも高速である。内部的に、ラムダ関数の呼び出し時には新しいスタックフレームが作られるオーバーヘッドがあるが、リスト内包表記の評価時には新しいスタックフレームが作られないからである。

リスト内包表記の成功を受けて、Python 2.4からは似たような表記であるが、実際にリストを生成せずにシーケンスを表現できる、ジェネレータ(これについては将来のエントリーで紹介する)が発明されることになった。この機能は「ジェネレータ式」と呼ばれる。

sum(x**2 for x in range(1, 11))

これは、引数にジェネレータ表現の引数を使用して、組み込みのsum()関数が呼ばれている。このジェネレータは、1から10までの数値の数の2乗を生成する。この関数は引数で生成された値をすべて合計して、385を返す。sum([x**2 for x in range(1, 11)])という表記と比べると、メリットは明らかである。リスト内包表記を使うと、すべての2乗の数を含むリストが実際に生成され、一度使われて破棄されてしまうのである。メモリ使用量が大きくなる巨大な配列の場合には、これも考慮すべきである。

リスト内包表記と、ジェネレータ表現の違いは小さいということも説明すべきだろう。例えば、Python 2では、次の表現は有効なリスト内包表記である。

[x**2 for x in 1, 2, 3]

しかし、次の表現はジェネレータ表現としては有効ではない。

(x**2 for x in 1, 2, 3)

"1, 2, 3"の部分にカッコを付けることで、きちんと動作させることができる。

(x**2 for x in (1, 2, 3))

Python 3では、これらのカッコは、リスト内包表記でも付ける必要がある。

[x**2 for x in (1, 2, 3)]

しかし、通常のforループや、明示的なforループの場合にはこれをキャンセルすることもできる。

for x in 1, 2, 3: print(x**2)

なぜ違いがあるのか、なぜPython 3.0ではリスト内包表記が厳格化されたのか?設計に影響を与えた要因としては、後方互換性、あいまいさの排除、等価性、言語の進化がある。初めPythonには、明示的なforループしかなかった。この場合には、'in'の後ろから、コロン(:)の前までであったため、あいまいなところはなかった。そのため、既知の値の上でループを回したいのであれば、煩わしくカッコを付ける必要はない。これを見ると、次のように書けた、Algol-60が思い出される。

for i := 1, 2, 3 do Statement

Algol-60はそれぞれの式の中に、step-until構文を利用することもできる。

for i := 1 step 1 until 10, 12 step 2 until
50, 55 step 5 until 100 do Statement

(これを振り返ると、Pythonのforループも、複数のシーケンス上でループが回せていたらもっとクールだっただろう)

Python 2.0にリスト内包表記を追加したときにも同じような推測法を適用した。シーケンスの式の後ろには閉じたブラケット']'、もしくは'for', 'if'キーワードのみが来るため問題が発生することはなかった。

しかし、ジェネレータ式が2.4で追加されると、あいまいさの問題が頭をもたげてきた。ジェネレータ式のまわりのカッコは、ジェネレータ式の一部ではないことも技術的にありえるからだ。次の例を見てみよう。

sum(x**2 for x in range(10))

外部のカッコは、sum()関数の呼び出しの一部であり、「裸の」ジェネレータ式が最初の引数として渡される。そのため、理論的には次の式は2通りの理解の仕方がある。

sum(x**2 for x in a, b)

これは、次の文を意図したものである。

sum(x**2 for x in (a, b))

このようにも理解できる。

sum((x**2 for x in a), b)

その後、活発な議論が行われ、(私の記憶が正しければ)このような場合には推測をしない、ジェネレータ内包表記の場合には、'in'キーワードの後ろには単一の式(もちろん繰り返し可能)を必要とする、ということになった。既に人気のある構文となっていた、リスト内包表記を使用していた既存のコードの互換性を崩したくない、という考えもあった。

Python 3の設計をしている時にリスト内包表記の動作に変更を加えた。次のようなリスト内包表記があったとすると、

[f(x) for x in S if P(x)]

組み込みのlist()関数をジェネレータ式に適用した、次の文と同一になるようにした。

list(f(x) for x in S if P(x))

このため、リスト内包表記でも、多少制約の強い、ジェネレータ式の構文を使用することを決定した。

Python 3ではもう一つ変更を加え、リスト内包表記とジェネレータ式の等価性が向上した。Python 2では、リスト内包表記のループ制御変数は周辺のスコープに「漏れ」ていた。

x = 'before'
a = [x for x in 1, 2, 3]

print x # this prints '3', not 'before'

これは、リスト内包表記の元本の実装によってもたらされた副作用である。これは昔からある、Pythonの「隠しておきたい小さな汚点」の一つであった。意図的な妥協のおかげで、リスト内包表記は最初から高速な実装であった。初心者がひっかかるような落とし穴ではなかったが、時々害を受ける人が出た。ジェネレータ式の実行には別の実行フレームが必要とされるため、ジェネレータ式では同じようなことはできなかった。そのため、特に小さなシーケンスを相手にする場合には、効率性の面でジェネレータ式はリスト内包表記に負けていた。

しかし、Python 3では、我々はジェネレータ式と同じ実装の戦略を取ることで、リスト内包表記の「隠しておきたい小さな汚点」を修正することを決定した。そのため、Python 3で上記のサンプルを実行すると(print(x)と変更を加えましょう :-)、'before'と表示され、リスト内包表記で一時的に隠された変数'x'も、周囲のスコープの'x'を上書きしないということが分かるだろう。

これによって、Python 3のリスト内包表記は遅くなったのではないか、と心配する人もいると思うが、Python 3を高速化しようという膨大な努力のおかげで、Python 3のリスト内包表記と、ジェネレータ式は、Python 2と比較してそれぞれ高速になっている。また、この2つの間にあった速度差も解消している。

更新: Python 3で追加された、setとdictの内包表記について言及するのを忘れていた。これらは、リスト内包表記を素直に拡張しただけである。