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の内包表記について言及するのを忘れていた。これらは、リスト内包表記を素直に拡張しただけである。

1 件のコメント:

  1. いつも有用な翻訳をどうもありがとうございます。

    翻訳された文章を読んでいていくつか気になった箇所があるので報告します。

    「ジェネレータ式のまわりのカッコは、ジェネレータ式の一部ではないことも技術的にありえあるからだ」という部分ですが、原文だと "the parentheses around a generator expression are not technically part of the generator expression syntax." となっており、素直に読むと
    「ジェネレータ式のまわりのカッコは、厳密にはジェネレータ式の一部ではない」となるのではないかと思います。

    また、その少し上で「リスト内包表記と、ジェネレータ表現の違いは小さい」とありますが、原文では fairly subtle と書かれているので、「きわめて微妙な違いがある」とした方がニュアンスが近く前後の文脈に合いそうです。

    返信削除