Python 内包表記

Question

jupyter notebookでとある数列を求めるプログラムを作りました。
for文の中にあるfor文(for j in range(compare.size + 1)...)を内包表記で簡潔に書きたいのですが、
breakの入れ方がわかりません。教えてください。

%matplotlib inline
import math
import matplotlib.pyplot as plt
import numpy as np

pd.options.display.max_columns = None
pd.options.display.notebook_repr_html = True
    
grundy_ceil = np.array([0])
grundy_ceil_1p = np.array([0])

for n in range(1, 101):
    compare = np.array([])

    compare = np.append(compare, [grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))])
        
    for j in range(compare.size + 1):
       if not j in compare:
            grundy_ceil = np.append(grundy_ceil, j)
            break

df = pd.DataFrame(grundy_ceil).T

Answer 1

可能です。リスト内包表記だけをつかって同じように動作するコードが以下です。

import math
import numpy as np
import pandas as pd

b = np.array([0])
for n in range(1, 101):
    a = np.array([])
    a = b[:-(math.ceil(n/2)+1):-1]
    b = np.append(b, [x for x in range(len(a)+1) if x not in a])
df = pd.DataFrame(b).T

ただし、上記のリスト内包表記は元のコードよりも実行速度が10~20%ほど遅いです。

速度重視ならmkgreiさんのコードと上記を組み合わせた以下のコードのほうが10~20%ほど速いようです。

import math
import numpy as np
import pandas as pd
from itertools import count

b = [0]
for n in range(1, 101):
    a = b[:-(math.ceil(n/2)+1):-1]
    b.append(next(i for i in count() if i not in a))
df = pd.DataFrame(b).T

101ぐらいでは実感できないですが1001を超えてくると差がはっきりとわかります。

Comments

[mkgrei]

next()を使うと見やすくなるだけでした。
速度は実はあまり変わりません。
cProfileを使って調べると比較がボトルネックだったので…
がんばったのに、悲しい…

早くするのならaをset()にすることみたいですね。
そうすればnot inがO(1)になるので。

ご指摘の通りデータサイズも重要ですね。
101個程度なら何をやっても気にならないです。

[O.K.]

回答ありがとうございます。

a = b[:-(math.ceil(n/2)+1):-1]
のところはどういう文法になっているのでしょうか？

[mkgrei]

ここが詳しい。
https://qiita.com/kakk_a/items/54e81346d8f35733ab5e

[yag1kaz]

a = b[:-(math.ceil(n/2)+1):-1]

で処理している内容は

『配列bの要素を、後ろから数えてmath.ceil(n/2)個までの要素を、逆順に取り出してaに代入せよ』

ということになります。
後ろから数えてX個目までを取り出す処理は、

list[:-X+1:-1]

と書くことで実現できますのでそれを利用しています。

蛇足）
括弧を余分につけて
list[:-(X+1):-1]
と書いてもおなじですが、こう書くとサルが2匹寝転んで縦につながっているみたいでちょっと面白いですねｗ

[mkgrei]

その視点は遊び心があっていいですね。←蛇足について

[O.K.]

なるほどわかりました。
ありがとうございます。

Answer 2

今回の目的を果たすためであれば、条件を満たす最初のものを取り出すことができるはずです。
こんなやつ。
ここを参考にしています。

from itertools import count
a = [grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))]
j = next(i for i in count() if i not in a)

コードの速さが気になるのであれば、numpy.arrayへのキャストなくすべきでしょう。
また検索があるので、listやnp.arrayではなくsetを使うとだいぶ早くなります。

import math
import pandas as pd
from itertools import count
grundy_ceil = [0]

for n in range(1, 101):
    a = set([grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))])
    grundy_ceil.append(next(i for i in count() if i not in a))

df = pd.DataFrame(grundy_ceil).T

---

追記：完全に趣味ですが。ここを参考に。
yag1kazさんのlistからの取り出し方も取り入れました。
sliceをリスト内包表記で書くと遅くなるのは盲点でした…

from timeit import timeit
from itertools import count
import math
import pandas as pd
import numpy as np

pd.options.display.max_columns = None
pd.options.display.notebook_repr_html = True

def f0():
    grundy_ceil = np.array([0])
    #grundy_ceil_1p = np.array([0])
    for n in range(1, 101):
        compare = np.array([])
        compare = np.append(compare, [grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))])
        for j in range(compare.size + 1):
           if not j in compare:
                grundy_ceil = np.append(grundy_ceil, j)
                break
    df = pd.DataFrame(grundy_ceil).T
    return df

def f1():
    grundy_ceil = [0]
    for n in range(1, 101):
        a = [grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))]
        j = next(i for i in count() if i not in a)
        grundy_ceil.append(j)
    df = pd.DataFrame(grundy_ceil).T
    return df

def f2():
    grundy_ceil = [0]
    for n in range(1, 101):
        a = np.array([grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))])
        j = next(i for i in count() if i not in a)
        grundy_ceil.append(j)
    df = pd.DataFrame(grundy_ceil).T
    return df

def f3():
    grundy_ceil = [0]
    for n in range(1, 101):
        a = set([grundy_ceil[n - i] for i in range(1, math.ceil(n /2 + 1))])
        j = next(i for i in count() if i not in a)
        grundy_ceil.append(j)
    df = pd.DataFrame(grundy_ceil).T
    return df

def f4():
    grundy_ceil = [0]
    for n in range(1, 101):
        a = set(grundy_ceil[:-math.ceil(n/2+1):-1])
        j = next(i for i in count() if i not in a)
        grundy_ceil.append(j)
    df = pd.DataFrame(grundy_ceil).T
    return df

a = f0()
b = f1()
c = f2()
d = f3()
e = f4()
print('f1', np.allclose(a[0].values, b[0].values))
print('f2', np.allclose(a[0].values, c[0].values))
print('f3', np.allclose(a[0].values, d[0].values))
print('f4', np.allclose(a[0].values, e[0].values))
'''
一応同じ結果になることを確認
f1 True
f2 True
f3 True
f4 True
'''
n = 1000
print('Original  {}'.format(timeit(f0, number=n)))
print('list      {}'.format(timeit(f1, number=n)))
print('np.array  {}'.format(timeit(f2, number=n)))
print('set       {}'.format(timeit(f3, number=n)))
print('slice+set {}'.format(timeit(f4, number=n)))
'''
Original  9.65767323700129
list      1.1692692330107093
np.array  7.38920716199209
set       0.9272018460032996
slice+set 0.6420557640085462
'''

Comments

[O.K.]

回答ありがとうございます。
setを使うというのは盲点でした。

Answer 3

Python内包表記はbreak（ループ中断）をサポートしません。（for文では何か問題があるのでしょうか？）

一応、禁じ手的なハック も存在するようですが、全くおすすめしません。

Comments

[O.K.]

そうでしたか。ありがとうございます。
できるだけ短く書きたかったので。