くないらぼ

python でおかねをあならいず

pandas.DataFrame のforループをゆるふわ△改良して300倍高速化する

python 高速化

主張：高速化は最後のおたのしみにしましょう。

無駄にいじいじして高速化させて満足し、結局その後はほとんど使わなかったなあ、、、が私の日常です。

えらい人も言っていますが、高速化なんてホント最後でいいんです・・・。 今まで何十回後悔したことか。。。（これからもまたやりますが。）

pythonであれば numba,cython,swig など、コンパイルしちゃう系の力（パワー）を借りることで、 全く同じアルゴリズムでもざっくり100倍単位で簡単に高速化できます。

しかし、このやり方ではpythonのインタープリターなゆるふわ△言語の良さを（該当コード部分において）捨ててしまいます。結局C/C++に魂を売っているだけです。
私は魂を売ることそれ自体が好きなので良いですが、この行為はpythonの持つ別の面での高速性、つまり "生産性の高さ" を犠牲にしています。
コードの実行スピードが速くなっても生産性が下がれば、制作時間＋コード実行時間は悪化していることがよくあります。私はほぼ確実に悪化できています。

こんなデメリットもあるため、高速化は生産性をほとんど犠牲にしないで済むような段階、つまりできるだけ最後の段階でやるとお得になるわけです。

この点において、numpyなどは実に良い粒度で魂を売ることに成功しているため、使用者は生産性をほとんど損なわずに高速化の恩恵を得ることができます。 このバランスはとても素晴らしく、魂を売る者ならこの塩梅を目指すと良いでしょう。

（とはいえ、千倍以上高速化されて、数時間の処理が数秒になったりすると高速化それ自体に喜んでしまい、高速化沼に引きずり込まれます＾＾）

本題 : pandas.DataFrame のforループをゆるふわ△改良して300倍高速化する

ここから本題ですが、上記のようにできるだけ魂を売らずに（== pythonの柔軟さを損なわずに）高速化するという、ゆるふわ△高速化をしてみます。
よく、pythonのfor文は遅いからダメだ、とかいう人がいますが、個人的にはその意見には同意しかねます。

for文は悪者ではなく、for文内に遅いコードを書くことが悪いのです。

forループだけを回した時間計測結果を下の方に書きましたが、pythonの他の処理に比べて遅いなんてことはないと思います。


さて、以下のような DataFrameがあったとします。

import pandas as pd
df = pd.DataFrame({"a":list(range(500000))})
df.shape # (500000,1)

変数 df は pandas.DataFrame で、 50万行です。
ここでは、非常にややこしい条件分岐があるため、for文を使うことを選んだケースを想定しています。
そして何かを計算するため、変数dfのa列を1行ずつ順番に取り出したくなったとします。 （バックテストとかね。）

なお、ここでの時間計測ですが、%%time とか書くのが面倒なので、 Jupyter の nbextensions の ExecuteTime ってやつで自動で計測させています。 若干オーバーヘッドがある気がして、数ms遅いかもしれません。
キャッシュに関しては無視しています。キャッシュが効いたからこそ速かった場合もあるかもしれませんが、一旦はそれも実力（？）として比較しています。


なお、使用したバージョンはこれでした。
python 3.6.3
pandas 0.22.0
計測はそんなに速くないノートでやっているので時間は遅めです。


(a) ナイーブというか公式的（？）な実装 -> 27秒
for idx,row in df.iterrows(): 
    row.a # 27秒

(a) row はpandas.Series型で、結構いかつめのオブジェクトです。
これがdf.iterrows() によって計50万回も生成されるので、遅いメモリ確保がたくさん発生してそうです。。。


(b)ちょっと意識高くしてみた -> 10秒
for idx in range(df.shape[0]): 
    df.a.iloc[idx] # 10秒

(b) Seriesの生成は避けることができましたが、 iloc の内部で起きているindexの探索やら例外処理が重そうです。（ソース見てないので想像）
また、50万回もあると、 df.a の裏で暗躍している、 __getattr__ もほんのちょっとだけ負荷になってるかもしれません。


(b') (b)をベースにして、 __getattr__ が殆ど作用しないようにした。 -> 6.4秒
df_a = df.a
for idx in range(df.shape[0]):
    df_a.iloc[idx] # 6.4秒

(b') あら！！　思ったよりも __getattr__ の影響が大きかったです。自分でも驚きました。
・・・というか、DataFrameの __getattr__ のオーバーライドがいかついんでしょうか。。。普通こんなに重くないでしょ・・・


ということで、ちょっと脱線してノーマルの __getattr__ を計測。 -> 75ms
class A:
    def __init__(self):
        self.a = 0

InsA = A()
for _ in range(500000):
    InsA.a # 75ms

やっぱりこんなもんでした！ つまり pandas の DataFrameの __getattr__ 内の処理が重いだけでした。これは気をつけなきゃ・・・


(b'') さらに、 .iloc（これは普通の関数呼び出し）も一個にまとめてみた。 -> 6.2秒
df_a_iloc = df.a.iloc
for idx in range(df.shape[0]):
    df_a_iloc[idx] # 6.2秒

(b'') これは(b')とほとんど変わらず。 __getattr__ の負荷に比べると、関数呼び出しのコストは無視できるレベルですね。


(b''') (b)のdf.aの代わりに df["a"] を使う版 -> 8.9秒

ちょっと(b)との比較まで話が戻るのですが、 df.a のアクセスと、 df["a"] のアクセスはどっちが速いのでしょうか。

for idx in range(df.shape[0]): 
    df["a"].iloc[idx] # 8.9秒

(b''') __getitem__でのアクセス(df["a"]) のが __getattr__ (df.a (b)にて10秒だった )よりもちょっと速いんですね。へー。


(c) pandasを捨て、numpyに逃げた -> 2.5秒
for idx in range(df.shape[0]):
    df.a.values[idx] # 2.5秒

(c) pandasをうたっていたくせにやっぱり numpyに逃げる好例ですね。
valuesでnumpy.arrayにしてからのindexingならほとんど生アクセスに近いので速いです。


(c') (c)をベースにして例の __getattr__地獄を回避した -> 0.45秒(448ms)
df_a = df.a
for idx in range(df.shape[0]):
    df_a.values[idx] # 0.45秒 (448ms)


(c'') (c')からさらに .values 分の __getattr__ も削減 -> 0.09秒(90ms) ←さいしゅうけっか
a = df.a.values
for idx in range(df.shape[0]):
    a[idx] # 0.09秒( 90ms)


(参考) 50万回の空ループ -> 0.03秒(35ms)

ちなみに空ループが以下のように35msでしたので、これがゆるふわ△高速化の限界値でしょう。
( values[ ] の __getitem__ や take も試したのですが、前者は 120ms, 後者は 350ms と遅かったです。なんでだろう。どんな実装になっているのでしょうか。)

for _ in range(500000):
    pass # 0.03秒( 35ms)



まとめ

  • numbaやcythonを新たに使わずに、 27000ms(27秒)→90ms と、 300倍に高速化できました。
  • for文は悪くないよ、for文の中で重い処理を書くことが悪いんだよ。


最後に注意
pandasでもそうですが、できるだけfor文を使わない書き方で済ませるのが良いです。（基本的には apply とか groupby を使いましょう）