システムトレードソフト「Protra」のバックテストが遅い原因の調査

スポンサーリンク

もしもし虎よ

 
 

 

Protra(プロトラ)よ

 
 
 

世界のうちでお前ほど

 
 

歩みの のろいものはない

 
 
どうして そんなにのろいのか。

 

 
 

一回のバックテストで8時間とか、21時間とか……。

 
 
 

Protraは遅いが、僕が老いるのは早いんだよ!

 
 
 

こんな計算処理を待ち続けたから、人生がもう終わりそうだわ……。

 
 

ひかれたレールに乗っかり 生きてきたが道も終わり

ようやく気付く穴が心にぽっかり 今終わる人生一度の旅

『人生一度』 By SOFFet

冒頭でも書いたがシステムトレードのバックテストツールである「Protra」の計算速度が遅い。

FileIOが問題、マルチプロセッサを活用してない……

などが問題だと思ってた。
 

まぁ、それはあるのかもしれない。

だけどストラテジーによって1時間程度のものや8時間かかる手法もある。

これは明らかにストラテジーの書き方に問題がある。

重い腰を上げて調査してみた。

 
 

今回は、Protraを使って、かつ私のストラテジーを使っている人にしか関係ないローカル話。

世界中に1人、2人しかいないと思う。

そして、「ローコード/ノーコード開発」が叫ばれる中、20年前から私の脳みそは止まってるな……。

スポンサーリンク

まずはC#で処理時間を測定できるようにする

まさかのここから。

時間計測は、どの言語でも似た書き方をする。

PtSim/MainForm.cs を次のように書き換えた。

計測開始は「実行」ボタンが押される直前とした。

そして、以前ファイル出力で実装していた部分に次のように記載した。

バックテスト完了後に売買結果をテキストに保存する(システムトレード)
過去のイザナミ愛用者のブログを読み漁ると、2015年頃までは独自ストラテジー・開発ヒントを公開されている方が多かったように感じます。ですが、次のようなバッシングを受けて、多くの方(hamhamseven氏など)が自粛されたという経緯...

これでファイルに実行時間が残る。

遅い部分を特定する

所感では計算スピードが段々と後半になるにつれて落ちている印象がある。

メモリを使いすぎなのかな……?

 
 

何がともあれ、「問題認識」したら次は「原因調査と分析」がセオリー。

 
 
 

そう。社会人には当然のルールです!

 
 
 

 
 

毎日、毎日「課題は?目的は?」と上司に言われて、イラッとくるよね。

【推測1】# loop-type: date-onlyが遅い?

通常、PtSimは保有しているすべての株価データのうち、一番古い日付から最新の日付まで一度だけシステムを実行する。

それを抑制し銘柄を横断するシステムを作るために

#loop-type: date-only

をコード冒頭に書いている。

騰落レシオやソート処理を使わない場合には不要だけど、ライブラリを共通にして実装方法を共通化する目的で常につけている。

これが遅いのでは?

という指摘を頂いた。

が、サンプルであるMACrossとMACrossWithCapはどちらも15分程度で実行時間に有意な差が無いらしく、この説は異なるらしい。

また、ソースを確認してもFileIOで遅くなる要因がないらしい。

【推測2】{-1}Closeが遅いのでは?

銘柄を横断するシステムなので、過去や未来の終値や高値を参照するとFileIOが走り遅いのでは?

という推測。

つまり、次のような実装だ。

ということで、TIlib.ptに新規のAPIを追加して比較してみた。

この実装では、当日の処理をしている際にメモリに3日間分のCloseとVolumeを保存している。

コードとしてはイケてないが、とりあえず これで実験開始。

【CloseVolume_newを呼び出した場合】

  • 経過時間 = 0日0時間21分21秒
  • 経過時間 = 0日0時間17分43秒

【{-1}Close、{-2}Close、{-3}Closeを呼び出した場合】

  • 経過時間 = 0日0時間23分7秒
  • 経過時間 = 0日0時間20分0秒

どちらも20分前後で差が無かった……。

【推測3】購入処理が長い?

実はストラテジー部分ではなく、購入銘柄を決めた後の処理が長いのでは?

という指摘。

 
 

いや無い無い。

変えてるのはストラテジー部分だよ?

 
 

と思ったが測定してみた。

ソートを使わない場合と使う場合で計測するだけ。

利用したストラテジーは次のページのもの。東証一部だけのバックテストでも3時間30分程度かかった。

cosisin氏の高スペックデイトレ戦略有効性検証(システムトレード)
システムトレードのバックテストを継続的に続けているが、それに対して嬉しい反響をもらった。うん。儲かってないのは事実だ。利益曲線が寝ないストラテジーが未だ作れてないからね。でも、手法を公開した事で利...

ソートを使わない場合は次のような実装に書き換える。

【ソートを使う場合】

【ソートを使わない場合】

 

で計測。

 

【オリジナル】

  • 実行時間 = 0日3時間44分26秒

【Sortなし】

  • 実行時間 = 0日0時間26分29秒

 
 

つまり、こういうこと。

 

 
 

圧倒的に遅いのはソート処理

 
 

色々な実行処理をコメントアウトしながら測定しているので必ずしも正確な数値ではないが、ソート処理が原因なのは疑いようもない事実だ。

原因箇所の特定

確認すると約500銘柄のシグナルが出ていた。

つまり、O(n2) で計算すると250,000回 の交換を行っている。

この処理数で そんなに処理スピード落ちるかなぁ……?

 
 

と考えていたが、年々シグナル数が増えていた。少しずつ遅くなる理由はこれか?

1,500銘柄でシグナルが出ているとすると、2,250,000回の並び替えを行っている。

それは確かに遅そうだ。

 
 

ソート処理は、グコウ氏の書き方を拝借したんだよな……。

【Protra】買い銘柄に優先順位をつける | グコウログ
以前の記事「市場トレンドを売買ルールに入れる」で、ルールと売買の関数を独立させる方法を用いました。今回はその応用編として、売買ルールを満たした銘柄の内 優先順位を付けて購入する方法です。同日に買いシグナルが複数出た場合、通常の記載法では証券

例えば「マージソート」に実装を変更すると早くなるのかな?面倒だな。

名称 計算時間 内部/外部 安定/不安定 備考
バブルソート O(n2) 内部ソート 安定 遅い
選択ソート O(n2) 内部ソート 安定 交換回数がバブルソートより少ない。
挿入ソート O(n2) 内部ソート 安定 ほぼソート済や少ないデータに対しては高速
シェルソート O(n2) ※ 内部ソート 不安定 ※最悪の場合
間隔 h の取り方次第でO(n2)よりは高速になる。
クイックソート O(n log n) 内部ソート 不安定 実用上最速とされる。ピボットの取り方がまずいと最悪計算量 O(n2) に陥る。
マージソート O(n log n) 外部ソート 安定 安定かつ高速だがメモリを使用する。
ヒープソート O(n log n) 内部ソート 不安定
バケットソート O(n) 外部ソート 安定 キーの取りうる値がm種類しかなく、mがあまり大きくないという前提が必要。強い制限があるが、非常に高速。
基数ソート O(n) 外部ソート 安定 キーの取りうる値がm種類しかなく、最大値と最小値がはっきりしているという前提が必要。キーの桁数分バケットソートを繰り返す。

資金以上のシグナルが出る際には、優先度の考えは必須でありイザナミでは当たり前の機能だ。

これを無くすことは出来ない……。

まとめ

見て見ぬ振りをしていた実行時間。

毎日実践投入予定のストラテジーの自動実行をしているが、シグナルがメールで届かない時がたまにある。

そりゃぁ、バックテストが「21時間」かかかってたら「終値」が公開される夕方から翌日の9:00までにバックテストが終わらないよね。

 
 

ソート処理は修正が必要だなぁ……。

2021年(社会人17年) テクノロジー システムトレード
スポンサーリンク

コメント

  1. 匿名 より:

    Sortライブラリーを使ってみてください

  2. nehori より:

    コメントありがとうございます。

    10年以上前に個人の方が作成した「Protra」というアプリで動作する独自言語を使って実装しているので、Sortライブラリは存在しないと思ってます。

    C#やPythonであればSort関数やライブラリが充実してますが・・・。
    再帰やFor構文すらサポートして無いんですよね・・・。

  3. マコト より:

    実装を見た感じだとシグナル数×シグナル数ではなくてシグナル数×検証対象全銘柄のような気が。

    バブルソートは常に総舐め確定なのでクイックソートかマージソートのほうが良いとは思います。
    が、そもそもの問題でシグナルを全件覚えて毎回ソートする必要はありますか?

    // 1) [デイトレ逆張りサンプル(順位)]が[10]より[小さい(同じ含む)]
    // 1) 移動平均乖離率(終値)(100) 小さい順

    この部分だけを見ると、覚えておくのは10件で良さそうに思えます。

    要素数が若いほうが優先順位が上として、要素数10で以下のような二次元配列を作成。
    二次元配列が難しいなら要素数が同じ配列2つでも良いです。
    [銘柄コード][移動平均乖離率]

    1)【ランキング条件(デイトレ逆張りサンプル)】を満たしたら、最下位の要素と比較。
    2-a)最下位の要素の[移動平均乖離率]と比べて下位であったら、それで終了。
    2-b)最下位の要素より上位であったら最下位の要素を書き換え。
    3)ソートして優先順位の並び替え。

    最初の10シグナルまでは要素10にnullが入っている?のでその場合は問答無用で要素の書き換えです。
    資金の都合で入れないことが確定しているようなものはそもそも上記の順位付け処理は不要です。
    投入総額で動的に変わるというのであれば、要素数を10ではなくて30くらいにしておけば良いかと思います。

  4. nehori より:

    マコトさんコメントありがとうございます。

    再帰を使わないマージソートを実装しようと思いましたが、
    選択ソートで上限値を決めるのが速度的にも実装負荷的にも良さそうです。

ねほり.com
タイトルとURLをコピーしました