なにも わからぬ

パソコンとプログラミング関係をメモっていきたい

Pythonで内包表記芸/内包表記でフィボナッチ第999999項

Pythonといえば内包表記芸、何でもかんでも内包表記で書けば宝くじに当たるわ身長は10km伸びるわ彼女ができて札束風呂でウハウハです(※個人の感想です)。が、今までlist.__setitem__等のメソッドを知らず内包表記をしゃぶりつくせていなかったことが判明したため、自分の理解のためにまとめてみる。

内包表記芸で使うテクニック

内包表記内ローカル変数

[i+a[i] for a in [[0,2,4,6,8]] for i in range(5)] # [0, 3, 6, 9, 12]

for文でiterableを回すと、そのfor文のブロック内で変数として使えるってだけの話なんだけど、内包表記芸ではこれを多用する。

内包表記内変数への書き込み

これがキモ。内包表記内ではn = 1のような代入式を書くことができない(と思う)が、a.append(1)は書くことができる(そして戻り値のNoneが値として評価される)。さらにa.__setitem__(0, 1)a[0] = 1と等価)やa.__delitem__(0)del(a[0])と等価)なども使えるため、リストならばほぼ自由にアクセスできると言っていい。数値や文字列の変数もoperatorモジュールのiadd()などで操作できそうに思えるが、数値や文字列はイミュータブルのため、これらのメソッドによる再代入はできない。

詳しくは 10.3. operator — 関数形式の標準演算子 — Python 3.6.1 ドキュメント

後置ifの悪用

内包表記内では後置ifっぽいのが書け、条件が真でないと以降のコードは読まれないし、リストへの要素追加も行われない。

[i for i in range(10) if i%2==0] # [0, 2, 4, 6, 8]

そしてif文に与えられた条件式は値が確定しない限り評価されるため、条件式として上記のa.__setitem__()などを書くと、要素追加は行わずに変数操作のみを行うということができる。

[a[0] for a in [[0]] for i in range(1, 11) if a.__setitem__(0, a[0]+i) or i==10] # [55]

このコードは本体リストへの要素追加の前にa.__setitem__(0, a[0]+i) or i==10を評価する。a.__setitem__(0, a[0]+i)の戻り値は常にNoneのため条件式に影響は及ぼさないが、リストaへのアクセスは毎回行われる。そして条件式が真となり本体のリストへの要素追加が起こるのはi==10のときのみ。このテクニックを使わないと、内包表記内変数へのアクセスのたびに本体の要素数が増えてしまうため重要。

内包表記でフィボナッチ数

フィボナッチ数列は漸化式で定義され、n番目のフィボナッチ数を覚えておいてn+1番目とn+2番目を求めるために使う必要があり、内包表記内では自分自身へのアクセスができないため内包表記では求められなさそうに見える。そこで内包表記内の変数としてリストを持っておき、そっちへappendすることで自分自身へのアクセスの代わりとする。

# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
[i if i<2 else (a.append(sum(a[-2:])), a[-1])[1] for a in [[0,1]] for i in range(10)]

上のコードでは0項目・1項目だけ場合分けして、あとはリストaに計算したフィボナッチ数をappendしていき、その最後の要素a[-1]を追加していくリスト内包表記となっている。a.append(sum(a[-2:]))の戻り値はNoneなので、(None, a[-1])[1]としてa[-1]のみをリストに追加している。

このコードの動作を考えるとわかる通り、内部で二重にリストを保持して無駄だし遅いしメモリも食うので、常にaの要素数が次のフィボナッチ数を計算するために必要な2個だけになるようにしてみる。

# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
[i if i<2 else (a.append(sum(a[-2:])), a.__delitem__(0), a[-1])[2] for a in [[0,1]] for i in range(10)]

要素を追加した後にindex=0の要素を消している。このコードのaが確かに要素数2個になっているかは、a[-1]の部分をa[:]にしてみるとわかる。

[0, 1, [1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 13], [13, 21], [21, 34]]

これでフィボナッチ数列をまるまる求めるコードはできたけど、結局数列を全てリストで保持しているため数が多くなるとメモリをバカ食いして死ぬことになる。

f:id:htkb:20170619222930j:plain

そこで999999番目のフィボナッチ数だけを求めてみる。ここで前述の後置ifの悪用が役立つ。

追記:999999項目と言いながら1000001項目を求めるコードだったので修正しました。ご指摘感謝します。修正ここから

if a.append(i if i<2 else (sum(a[-2:]), a.__delitem__(0))[0]) or i==999999

これはaへのappend(及びi<2ならば__delitem__も)は毎回行われるが、i==999999にならないと本体のリストへの追加を行わない。aの要素数はループが何回回っても2個に保たれるため、メモリ消費量が少ないまま内包表記でFib999999を求められる。

 [a[-1] for a in [[]] for i in range(1000000) if a.append(i if i<2 else (sum(a[-2:]), a.__delitem__(0))[0]) or i==999999]

f:id:htkb:20170622213102j:plain

修正ここまで

合ってるのか合ってないのかは知らないけど、メモリ消費量も特に増えることなく数秒後に数字がどばっと表示された。めでたしめでたし。

内包表記内で多次元リストを持ち、list.__setitem__()で値を書き込んだりすれば、内包表記内でDP(動的計画法)のテーブルを回すこともできる。

Submission #1365750 - Typical DP Contest | AtCoder

いやー夢が広がりまくりだと思いませんか!!Zen of Python?知らん!!