Pythonの高速化のまとめ Ver.1

PythonでのFXのランダムウォークを検証で、はじめてのPythonプログラムを実装しましたが、書き方工夫すればもっと早くなるのでは?という疑問があったのでいろいろ試行錯誤しました。

まずは、ランダムウォークのソースを改変する前に、どこが遅いのかなぁと検討した性能劣化のポイントとそれらの対策を纏めていきたいと思います。

他の言語からのヒント

私は、過去下記のスクリプト言語の経験があります。経験談なので読み飛ばしてもらっても構いません。

  • 大学時代の研究でmatlabで実験
  • 仕事の業務でJavaScriptで画面インターフェース作成

matlab

大学時代にmatlabで大量の実験を繰り返しました。Pythonと同じくスクリプト言語で、数値演算系です。1回の実験が計算機10台で1週間とかかかっていたので、処理速度が遅いのは致命的でした。

処理速度を向上するのに、もっとも効果的だったは、ループを減らすことでした。

できる限り行列演算でmatlabのAPIでできるようにします。簡単な話、ループで計算するのではなく、ベクトルや行列を事前に作ってそれらをM*Mなど演算してしまうのです。たとえ、メモリを余分に使い、演算結果の一部しか使わないとしても、ループするよりベクトル・行列演算を活用するほうが速いです。

この点は、Pythonのだいたいの入門にも書かれてます。例えばPandasのAPI(sumとか)はCで実装されているので、自分でループ処理するより高速です。

そのため、常にループを書こうとするときは、ベクトル・行列演算に書き換えれないかを考えていました。

JavaScript

仕事で画面のインタフェースのためにJavaScriptを使ってました。Ajaxが流行る前のDOMスクリプティングと呼ばれる頃からです。

他のCやJavaの延長でコーディングすると気づかないことですが、JavaScriptもPythonと同じくスクリプトで動的な型付け言語です。なので、変数xに対し「x.length」と書いても実行するまで、lengthが存在するプロパティなのかチェックできません。実行する直前にxのオブジェクトにlengthが埋め込まれる可能性もあります。

こういったプロパティのアクセスに対し、実行時にlengthの走査(検索)が起こるので、その走査だけで処理時間かかります。すごい細かい改善ですが、同じプロパティを書くのであれば、事前にローカルの変数に退避しておくことで、処理速度が向上します。100万回ループする可能性のある処理のなかで、「x.length」を3回書いていれば、300万回lengthを走査することになります。それを減らすよう注意するだけで、だいぶ速くなることがあります。

大前提

安易にForループを書いては行けない

例えば、下記のような乱数配列の奇数位置の合計を計算することを考えます。1億件の配列ndarrayの条件付きの合計です。

size = 10000000
x = np.random.rand(size)

一番安易なForループ

これを何も考えずにForループで書いてしまうと下記のようになります。私のPCでは54秒かかりました。

z = 0
for i in np.arange(size):
    if i % 2 == 1:
        z = z + x[i]

何も考えず、この一番安易なForループの実装をしてはいけません

Forループは残るがちょっと工夫

少し工夫してnp.arangeで奇数だけのインデックスを作ってループしています。私のPCでは19秒かかりました。先程の例の半分以下にはなっています。

z = 0
for i in np.arange(1,size,2):
    z = z + x[i]

Forループなしで実装(配列の積+和)

配列ndarray同士の積は同じ位置の要素の積になるので、事前に奇数を表す[0,1,0,1,…]というような配列を用意して、積をとってできた配列をndarrayのsumで合計します。私のPCでは1秒でした。

y = np.zeros(size)
y[1:size:2] = 1
z = (x * y).sum()

Forループなしで実装(ベクトルの内積)

次はベクトルの内積で合計してみます。先の例の配列の内積を取ると奇数インデックスの合計が計算できます。私のPCでは0.5秒でした。先の配列の積+和の場合、一度、積の段階でndarrayを返すのでその分遅かったのだと思います。内積をすると、積と和を同時にndarray内部で実施できるので更に高速になります。

y = np.zeros(size)
y[1:size:2] = 1
z = np.dot(x,y)

正解

そもそも、ndarrayは要素インデックス指定で配列を取り出せるので、実は下記の1行で計算できます。私のPCでは0.15秒でした。

z = x[1:size:2].sum()

まとめ

今回の正解の実装を思いつくのが一番よいですが、言いたいことはそれではないです。

言いたいのは、処理を書こうと思ったときに、Forループを使おうと思ったら一旦手を止めて、Forループ以外の方法はないか?と考える癖を付けたほうがよいということです。適当なループの54秒と内積の0.5秒で100倍も速くなるので。

このような工夫ができない場合でも、次の考慮はしたほうがよく、最終手段はnumbaを使うことです。

やむなくForループを使う場合

工夫する部分

同じ参照を何度もしてはいけない

普段何気なく書いてしまう下記のような式を、JavaやCと同じ感覚で、ループの中で書いてはいけません。

  • x[i] # 配列の要素へのアクセス、特に同じインデックス
  • x[‘attr’] # ディクショナリの要素
  • x.sum()

最後のはわかりやすいですね。合計を何度もしては行けないのです。でもその上の2つもコストは小さいですが、同じことです。例えばこんなコードを書いていないでしょうか?

options = dict(digit=5, unit='usd')

# いろいろ書いてあって

for i in range(size):
    x[i] = round(x[i], options['digit'])

駄目なのは、x[i]ではなく、options[‘digit’]です。x[i]はループの中で、1回ですが、options[‘digit’]は全ループで同じものを参照しているのに、毎ループでキーによるディクショナリを参照しています。下記のようにループの前で別の変数に格納しておくべきです。

options = dict(digit=5, unit='usd')

# いろいろ書いてあって

option_digit = options['digit']
for i in range(size):
    x[i] = round(x[i], option_digit)

これはJavaScriptでもよくやる手法で、何度も評価される
式は、ステートメント途中で毎回書くのではなく、先頭で変数に格納しておく
と高速化できます。変数が1つ増えてしまい可読性が下がりますが、高速化が期待できます。

高級なオブジェクトを使ってはいけない

なるべくループする前にシンプルなオブジェクトにしておいたほうがよいです。

例えば、pandasのDataFrameで全行の特定カラムを使った演算をするためにループしていくのであれば、下記のように書いてしまいそうです。

# ticksは370343レコードのDataFrame
z = 0
for i, row in ticks.iterrows():
    z = z + (row.high - row.low)

このループだと、私のPCで15秒かかりました。このDataFrame.iterrows()は行をSeriesに変えてループしていきます。でもよく考えると、利用するカラムが特定されているので、わざわざiterrows()でループを回さずとも下記に書き換えれます。

z = 0
for (high, low) in zip(ticks.high, ticks.low):
    z = z + (high-low)

私のPCでは1秒で終わりました。

使うカラムが特定されているので、そのカラムのSeriesを明示的に取り出してループしています。DataFrame.iterrow()の変換に頼らないのでその分高速化できます。

工夫では満足できない場合はnumba

numbaについては本家のドキュメントやPythonを速くしたいときにやったこと -Numba編-を見てください。

Pythonのスクリプトを一部だけC化して処理できます。

サンプルとして移動平均を独自で計算するプログラムを使っていきます。

まずはnumbaを使わない例

まずは、numbaを使わずForループの実装をした場合です。PythonでFXのヒストリカルデータ分析 導入編のFXのEURESDの2017年のデータを使って、移動平均を計算します。

close = ticks.close.values
size = len(close)
window_size = 4
sma = np.zeros(size, dtype=np.float64)
for i in range(window_size-1,size):
    sma[i] = close[i-window_size+1:i+1].sum()/window_size

私のPCで1秒でした。

numbaを使った例

Forループの処理をまるごとnumbaでコンパイルして処理します。

@jit(nopython=True)は、pythonコードが残らないようにコンパイルしてほしいというオプションです。numbaはできる限りC化してくれますが、置き換えられないものはpythonで実行してしまいます。このオプションを付けておくと、置き換えられない式とうあれば、コンパイル時にエラーで通知してくれます。

例えば、下記の例で、合計sumを計算する部分でコメント化しているリスト等で用いるためのsumを使っているとnumbaには置き換えられないエラーになります。実際、今回のサンプルを作るときに引っかかりました。そこで、numbaでsumするためには、ndarrayのsumを使うようにすれば、コンパイルできました。

@jit('void(float64[:],int32,float64[:])', nopython=True)
def my_sma(close, window_size, sma):
    size = len(close)
    for i in range(window_size-1,size):
        sma[i] = close[i-window_size+1:i+1].sum()/window_size
        #sma[i] = sum(close[i-window_size+1:i+1])/window_size

close = ticks.close.values
window_size = 4
sma = np.zeros(size, dtype=np.float64)
my_sma(close, window_size, sma)

私のPCで0.017秒でした。コードを変えずに約600倍速くなっています。今回は、もとのpythonコードの時点で速く処理できるようにndarrayを使ったりしているのですが、それでも600倍速くなりました。

pythonのndarrayに用意されているAPIを使った場合

ちなみに、今回の移動平均を計算するのであれば、ndarrayのrollingで実装できます。

sma = ticks.close.rolling(window=4).mean()

私のPCで0.024秒でした。rollingもCで実装されているはずですが、numbaで独自実装したコードより遅い結果になりました。多分、いろんな実装を考えて高級に作られているのでしょう。Pythonで用意されているAPIもそれが最速ではないのですね。ここまでとは考えていましせんでした。

一般的に、コードを書くときに独自コードをかかず、なるべくPythonやライブラリで用意されているAPIを使うほうが高速といわれています。なぜなら、ライブラリ等はPythonスクリプトではなくCで実装されているからです。ですが、今回の結果から、どうしても高速化しなければ行けないときには、独自コードでnumbaコンパイルして計測してみる価値はあるということがわかります。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする