こんにちは！スナフキンです．2ヶ月前ぐらいから，パラメタ最適化のための汎用バックテスターをちょいちょい暇なときに作っていたのですが，最近ようやく使い物になるレベルになってきました．バックテスターを作るときに気にするのは，正確さ，速度の2点だと思います．この2つはある意味トレードオフの関係にありますが，今回高速化に取り組んでみた結果86400秒（1日）分，解像度1秒（=86400回のループ）のバックテストを1-2秒程度で完了できる程度には高速化することができたので，そのTipsを共有しようと思います．ちなみにCythonやnumbaを使ったり，あるいは一部をC++で記述するなどの特殊なことはしていません．

はじめに

さて，バックテスト高速化と言いましたが，ぼくのバックテストプログラムはそもそもどういう構成になっているかを知らなければよく分からないと思うので，まず簡単に説明すると．

一定の時間解像度（0.5秒，1秒，2秒など）で注文を出すかどうか，また出した注文が約定するかどうか判定する．注文形式は成行と指値に対応している．
1で約定判定した注文の情報を元にPLを計算する．

というものです．データには約定履歴を1の時間解像度でsummarizeしたものを使っており，約定履歴さえ入手することができれば任意の取引所に対応できます．2の後にPLのグラフを描画したり，あるいは1,2を違うパラメタで繰り返して最適化を行ったりもしますが，それはあくまで付帯的な処理ですし，高速化といってもマルチプロセスで回すぐらいしかないので，今回は特に1,2を高速化することについてまとめます．

ボトルネック特定

高速化するといっても，そもそも何が原因で低速になっているのかを見極めなければ手の施し用がなく，まずはどこで速度の低下が発生しているかを特定する必要があります．（=ボトルネック特定）この際に非常に役に立つのがline_profilerというモジュールで，pipで入れることができます．使い方については次の記事がわかりやすかったです．

https://twitter.com/Nagi7692/status/1041999593532141568

これにより，コードに何行めがボトルネックになっているかを簡単に特定できます．コードの高速化はかなり地味な作業で，ひたすら遅い個所を見つけては訂正しての繰り返しになります．特に，ぼくのように効率を全く考えずにとりあえずある程度コードを書いてから修正をしていく場合には，なかなか大変な作業になると思いますが，プログラムの使用用途によっては費用対効果が絶大なので根気強く取り組みましょう．

高速化のためにやったこと7つ

ではボトルネック特定後，実際に取り組んだ高速化Tipsを紹介します．基本的に，pythonではfor文やwhile分でループを回すのは避けたほうが高速になることが多いです．javascript界隈では，逮捕者が出たとしてfor文が話題になっていますが，pythonを高速化したい場合でもfor文は禁止というわけです．下に行くほど，ぼくのプログラム特有の個別具体的で一般性が低いものになると思われます．（=読んでくださっているあなたが同じ事象に遭遇する確率が下がります．）また，pandasでデータを保持しているため，pandasに関するものが多いです．下のTipsは必ずしもベストプラクティスではないと思いますので，もっと良い方法があれば教えていただきたいです！なお，以下で出てくるサンプルコードは全てjupyter notebook上での実行を想定しています．

共通で使う前処理できるデータはなるべく前処理する

resamplingした約定データなど，異なるパラメタでバックテストするときなどに共通で使えるデータは前もって処理してファイルに保存しておくことで，無駄に何度も計算し直すことを避けられます．これはコードの書き方以前の問題ですが，やっていない場合はかなり効果が高いです．

できる限り行列で処理する

これは常識と言っていいほどのことですが，pythonで計算処理する場合，基本的にnumpy.ndarrayを使って行列演算をするべきです．特にデータ量が多いときは単純なforループで計算するのとは比べ物にならないほどの速度で計算できます．速度比較については以下の記事がわかりやすいです．

http://sucrose.hatenablog.com/entry/2012/12/25/174118

時系列データ処理はforでなくpandasのresampleやrollingを使う

時系列データを扱うとき，どうしても必要でない場合にはpandas.DataFrame.iterrowsやpandas.DataFrame.itertuplesなどを使ってforループで回さないようにしましょう．これだけで速度が100倍になったりします．むしろforで回していてpandas.DataFrame.resampleを使った結果速くなった，というのは賞賛されるべきことではなく，それに至る前にはめちゃくちゃ非効率なやり方をしていたとして無知を恥じるべきことだと思います．（ぼくのことです．）

pandasの要素へのアクセスは.valuesでndarrayに変換した上で行う

pandas.Dataframeは.locや.atなどの要素へのアクセス用関数が用意されていますが，.valuesでndarrayに変換した方がより速いです．1回のアクセスなら微々たるものですが，数百万回アクセスする場合には大きな差になるので気をつけましょう．

%%time
for i in range(1000000):
    df.at[0, 'a']
# CPU times: user 3.38 s, sys: 15.3 ms, total: 3.39 s 
# Wall time: 3.4 s

%%time

for i in range(1000000):

df.at[0, 'a']

# CPU times: user 3.38 s, sys: 15.3 ms, total: 3.39 s

# Wall time: 3.4 s

%%time
a = df['a'].values
for i in range(1000000):
    a[0]
# CPU times: user 2.03 s, sys: 8.91 ms, total: 2.04 s
# Wall time: 2.05 s

%%time

a = df['a'].values

for i in range(1000000):

a[0]

# CPU times: user 2.03 s, sys: 8.91 ms, total: 2.04 s

# Wall time: 2.05 s

pandasの検索はなるべく最小回数にする．

pandasでの条件検索は比較的時間を食います．この検索処理の回数をなるべく最小回数にしましょう．

クラスよりも辞書を使う

pythonのクラス生成は辞書生成よりも遅く，また，pythonのクラスのメンバー変数へのアクセスは，辞書のキーを指定してのアクセスよりも低速です．複雑な処理を必要としない場合には，むやみにクラスを作らずに辞書で扱ったほうが速いです．ぼくは何でもクラスにしてしまう癖があり，注文クラスを以下のように作っていたのですが，辞書にすることでパフォーマンスが改善しました．

# クラスと辞書の比較
class Order():

    def __init__(self, created_at, side=None, size=0, price=None, cancel_interval=31536000):
        self.created_at = created_at
        self.side = side
        self.size = size
        self.price = price
        self.executed_price = price
        self.cancel_interval = cancel_interval
        self.executed_at = None
        self.executed_size = 0
        self.canceled_at = None
        self.is_canceled = False

def generate_class_orders():
    for i in range(1000000):
        order = Order(2,'buy', 0, 111, 3333)
    return order

def generate_dict_orders():
    for i in range(1000000):
        order =  {'cancel_interval': 3333,
                     'canceled_at': None,
                     'created_at': 2,
                     'executed_at': None,
                     'executed_price': 111,
                     'executed_size': 0,
                     'is_canceled': False,
                     'price': 111,
                     'side': 'buy',
                     'size': 0}
    return order

def access_order_instance(order_instance):
    for i in range(10000000):
        price = order_instance.price
        
def access_order_dict(order_dict):
    for i in range(10000000):
        price = order_dict['price']

# クラスと辞書の比較

class Order():

def __init__(self, created_at, side=None, size=0, price=None, cancel_interval=31536000):

self.created_at = created_at

self.side = side

self.size = size

self.price = price

self.executed_price = price

self.cancel_interval = cancel_interval

self.executed_at = None

self.executed_size = 0

self.canceled_at = None

self.is_canceled = False

def generate_class_orders():

for i in range(1000000):

order = Order(2,'buy', 0, 111, 3333)

return order

def generate_dict_orders():

for i in range(1000000):

order = {'cancel_interval': 3333,

'canceled_at': None,

'created_at': 2,

'executed_at': None,

'executed_price': 111,

'executed_size': 0,

'is_canceled': False,

'price': 111,

'side': 'buy',

'size': 0}

return order

def access_order_instance(order_instance):

for i in range(10000000):

price = order_instance.price

def access_order_dict(order_dict):

for i in range(10000000):

price = order_dict['price']

%%time
order_instance = generate_class_orders()

# CPU times: user 613 ms, sys: 2.59 ms, total: 615 ms
# Wall time: 615 ms

%%time

order_instance = generate_class_orders()

# CPU times: user 613 ms, sys: 2.59 ms, total: 615 ms

# Wall time: 615 ms

%%time
order_dict = generate_dict_orders()

# CPU times: user 219 ms, sys: 2.63 ms, total: 222 ms
# Wall time: 221 ms

%%time

order_dict = generate_dict_orders()

# CPU times: user 219 ms, sys: 2.63 ms, total: 222 ms

# Wall time: 221 ms

%%time
access_order_instance(order_instance)

# CPU times: user 449 ms, sys: 2.09 ms, total: 451 ms
# Wall time: 451 ms

%%time

access_order_instance(order_instance)

# CPU times: user 449 ms, sys: 2.09 ms, total: 451 ms

# Wall time: 451 ms

%%time
access_order_dict(order_dict)


# CPU times: user 361 ms, sys: 3.17 ms, total: 364 ms
# Wall time: 364 ms

%%time

access_order_dict(order_dict)

# CPU times: user 361 ms, sys: 3.17 ms, total: 364 ms

# Wall time: 364 ms

リストのインデックス検索を辞書で行う

最後はけっこうマニアックであまり遭遇頻度が高くなさそうな事例です．pythonではリストのインデックスを取得したい場合に，list.indexという関数を使えます．すなわち，l = [1,2,4]のようなリストがあったときに，4がリスト内で何番目にあるのかを知りたいときにl.index(4)とすると2が返ってくるということです．しかし，これはリストを最初から検索する方法を取っているため，例えば[1,2,3…..100000]というリストの99999などのインデックスを検索しようとすると非常に時間がかかります．そこで，こういう場合にはリストの要素とインデックスを対応させた辞書を用意しておくと非常に高速に検索ができます．

l = [i+2 for i in range(100000)]

def find(l, numbers):
    indexes = []
    for i in range(10000):
        for n in numbers:
            if i == 0:
                indexes.append(l.index(n))
    print(indexes)

d = {l[i]:i for i in range(len(l))}

def find_from_dict(d, numbers):
    indexes = []
    for i in range(10000):
        for n in numbers:
            if i == 0:
                indexes.append(d[n])
    print(indexes)

l = [i+2 for i in range(100000)]

def find(l, numbers):

indexes = []

for i in range(10000):

for n in numbers:

if i == 0:

indexes.append(l.index(n))

print(indexes)

d = {l[i]:i for i in range(len(l))}

def find_from_dict(d, numbers):

indexes = []

for i in range(10000):

for n in numbers:

if i == 0:

indexes.append(d[n])

print(indexes)

%%time
find(l, [10000,50000,75226])

# [9998, 49998, 75224]
# CPU times: user 3.22 ms, sys: 156 µs, total: 3.37 ms
# Wall time: 3.38 ms

%%time

find(l, [10000,50000,75226])

# [9998, 49998, 75224]

# CPU times: user 3.22 ms, sys: 156 µs, total: 3.37 ms

# Wall time: 3.38 ms

%%time
find_from_dict(d, [10000, 50000, 75226])

# [9998, 49998, 75224]
# CPU times: user 1.42 ms, sys: 91 µs, total: 1.51 ms
# Wall time: 1.45 ms

%%time

find_from_dict(d, [10000, 50000, 75226])

# [9998, 49998, 75224]

# CPU times: user 1.42 ms, sys: 91 µs, total: 1.51 ms

# Wall time: 1.45 ms

頑張ればさらに改善できそうな点

ここまでにやったことで，1日分のバックテストを1秒解像度で1-2秒程度でできるようになりました．さらにline_profilerで見てみると，やはり上述のpandasでの検索がボトルネックとして残っており，全体の処理の40%ぐらいを占めています．これをNagiさんが以前つぶやいていたように，インメモリのSQLiteに書き換えるなどして高速化すれば，現在の処理速度の30-40%程度速くできるかもしれません．しかし，ここまでの高速化でやる気が尽きてしまったので，いずれ暇で仕方ないときにでもやろうと思います．

皆様もpythonでの高速化して，数万パターンのパラメタでの最適化など，できることを増やしてみてはどうでしょうか？ここまでお読みいただきありがとうございました．