イテレートによる速度低下 - pandas

pandas（の内部で動くNumPy）は、SIMD命令を使って同じ演算を一斉に行うことで高速化を実現している。

それに従わない書き方（for文を使ったイテレートや、df.apply()）をすると途端に遅くなる。

どれくらい違うのか、多少非効率的に見えても一気に計算させた方が速くなるのか、調べたメモ。

こんな、IDごとにxy座標が記録されたデータがあるとする。データはID→timeの順にソート済みであるとする。

  ID  time   x   y   ...other columns...
   1     0  10  20   ...
   1     1  11  21
   1     2  11  25
   ...
   1  1000 123  67
   2     0  57  21
   2     1  55  19
   ...

各IDについて、時系列的に隣り合う2点間距離を合計し、総移動距離を算出したい。

データ: およそ7000ID, 100万レコード

groupbyごとにイテレートし、さらにIDごとのdfでも1行ずつイテレート。結果はリストに溜める。

buf = []
for cid, cdf in df.groupby('ID'):

    dist = 0
    px, py = cdf['x'].iloc[0], cdf['y'].iloc[0]
    for idx, row in islice(cdf.iterrows(), 1, None):
        x, y = row['x'], row['y']
        dist += ((x - px) ** 2 + (y - py) ** 2) ** 0.5
        px, py = x, y
    buf.append([cid, dist])

groupbyごとにイテレートし、IDごとではNumpyのベクトル計算で距離を算出。結果はリストに溜める。

buf = []
for cid, cdf in df.groupby('ID'):
    xs, ys = cdf['x'].as_matrix(), cdf['y'].as_matrix()
    dists = (np.diff(xs) ** 2 + np.diff(ys) ** 2) ** 0.5
    buf.append((cid, dists.sum()))

groupbyごとにイテレートし、IDごとではpandasのベクトル計算で距離を算出。結果はリストに溜める。

buf = []
for cid, cdf in df.groupby('ID'):
    dists = (cdf['x'].diff() ** 2 + cdf['y'].diff() ** 2) ** 0.5
    buf.append((cid, dists.sum()))

Numpyで一気にベクトル計算し、IDの切り替わりの部分だけ修正する。結果はDataFrameで得る。

xs, ys = df['x'].as_matrix(), df['y'].as_matrix()
dists = (np.diff(xs) ** 2 + np.diff(ys) ** 2) ** 0.5
dists = np.append(dists, 0)  # pandasに戻すにあたって長さを揃える
df['dist'] = dists
df.loc[df.groupby('ID').cumcount(ascending=False) == 0, 'dist'] = 0
sdf = df.groupby('ID')['dist'].sum()

DataFrameに新規カラムdistを追加し、「次のレコードとの距離」を埋めている。

5行目について、GroupBy.cumcount()は、グループ化前のレコードに対して自身が同一グループ内で何番目か(0-indexed)を与える。ascending=Falseにすることで逆順になり、末尾レコードが0になる。つまり、IDの切り替わりである末尾レコードを抽出してdistを0にしている。

単純に末尾レコードを得るだけならGroupBy.last()が使えるが、元のDataFrameに代入操作を行うにはindex情報が必要で、last()の結果からはそれをどう取得すればいいかわからなかった。

pandasのdiffを用いてベクトル計算し、IDの切り替わりの部分だけ修正する。結果はDataFrameで得る。

df['dist'] = (df['x'].diff() ** 2 + df['y'].diff() ** 2) ** 0.5
df.loc[df.groupby('ID').cumcount() == 0, 'dist'] = 0
sdf = df.groupby('ID')['dist'].sum()

pandasのdiffは「前のレコードとの差分」を計算する（最初のレコードはNaNになる）。そのため方法4とは異なり、各グループ最初のレコードが除去すべきレコードとなる。

イテレートをすると途端に遅くなっている。特に1で用いたiterrows()は致命的に遅い。多少無駄はあっても、一気にまとめて計算できるならその方がよいと判断できる。

方法4と5では、5の方が速い。やっぱり用意されてる関数はできるだけ使った方がいいっぽい。ただし方法4も微差。

方法2と3を比較すると、2の方が明確に速かった。完全なDataFrameに対するdiffはpandasのdiffを使った方が速いが、そこから切り出した一部に対するdiffは苦手なのだろうか。この辺は注意すべきかも知れない。

まとめて計算するデメリットは、一度に必要なメモリが多い点。これは物理的にメモリをいっぱい積もう。

• Python 3.x - データフレームの中の一個前の列を参照して、次の列の演算を行う Python,Pandas(64620)｜teratail

各レコードについて、所定の条件に当てはまるなら値が決まるが、当てはまらないなら前の値を継承させたい。（所定の条件は、現レコードの情報のみで判別が可能）

この場合は、条件に当てはまらないレコードにはNaNを入れておき、fillna(method='ffill')を使うことで、自動的に前の値で埋めてくれる。

……というfillna()の使い方メモだが、リンク先の例の場合はそもそも条件に当てはまるかの判別でapply()を使わざるを得なくて、そこでイテレートが走っちゃってるんで、それなら前の値を保持しながらfor文を回すのと大差ない気もする。

ケース1の距離計算のように直前の値しか参照しなければ、一括計算した後の微修正も楽だが、数個前後の値まで必要となる場合、修正すべきデータも増えるし、枠の長さによって落とすべきデータが異なるので処理もだんだん複雑になっていく。

移動平均の定義を、畳み込み積分や移動平均を求めるnumpy.convolve関数の使い方 - DeepAgeに倣って'full', 'same', 'valid'に分けて考える。

'valid'（計算に当たってデータがない部分の値は算出しない）とすると、前後のデータと被る部分の値をすっきり削除するだけで済む。

'full'（枠と一部でも被る部分の値を全て算出する）は、そもそもデータの長さが元のデータ以上になってしまうため、まとめて算出するのは難しい気がする。

'same'（先頭はfull, 末尾はvalidに従い、移動平均後のデータ数が元のデータと等しくなる）の場合、うまいこと前後のデータと被る部分を再計算してやる必要がある。

枠の長さが5の場合、IDごとの先頭4レコードを修正の必要がある。

• 1番目のレコードは、結果をx5し、元データにおける前の1～4レコードを減算する
• 2番目のレコードは、結果をx5し、元データにおける前の1～3レコードを減算し、2で割る
• 3番目のレコードは、結果をx5し、元データにおける前の1～2レコードを減算し、3で割る
• 4番目のレコードは、結果をx5し、元データにおける前の1レコードを減算し、4で割る

枠の長さがwの場合、先頭w-1レコードを修正の必要がある。

• i番目のレコードは、結果をw倍し、元データにおける前の1～(w-i)レコードを減算し、iで割る

ただ、これをどうやってforなしに実装するかを考えあぐねる。特に減算の部分。