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

もしもし虎よ

Protra（プロトラ）よ

世界のうちでお前ほど

歩みののろいものはない

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

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

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

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

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

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

『人生一度』　By SOFFet

まずはC#で処理時間を測定できるようにする
遅い部分を特定する
原因箇所の特定
まとめ

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

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

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

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

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

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

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

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

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

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

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

まさかのここから。

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

// 開始時刻を保持
DateTime _startTime = DateTime.Now;

（何かの処理）

// 終了時刻を保持
DateTime _endTime = DateTime.Now;

// 経過時間を求める
TimeSpan ts = _endTime - _startTime;

// 経過時間を表示
Console.WriteLine("実行時間 = " + (int)ts.Days + "日" +
                                 (int)ts.Hours + "時間" +
                                 (int)ts.Minutes + "分" +
                                 (int)ts.Seconds + "秒");

// 開始時刻を保持

DateTime _startTime = DateTime.Now;

（何かの処理）

// 終了時刻を保持

DateTime _endTime = DateTime.Now;

// 経過時間を求める

TimeSpan ts = _endTime - _startTime;

// 経過時間を表示

Console.WriteLine("実行時間 = " + (int)ts.Days + "日" +

(int)ts.Hours + "時間" +

(int)ts.Minutes + "分" +

(int)ts.Seconds + "秒");

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

    public partial class MainForm : Form
    {
        private string _name;
+        private DateTime _startTime;
+        private DateTime _endTime;

        public MainForm()
        {
            InitializeComponent();
+            _startTime = DateTime.MaxValue;

public partial class MainForm : Form

{

private string _name;

+ private DateTime _startTime;

+ private DateTime _endTime;

public MainForm()

{

InitializeComponent();

+ _startTime = DateTime.MaxValue;

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

        private void buttonExecute_Click(object sender, EventArgs e)
        {
            if (backgroundWorkerExecute.IsBusy)
            {
                backgroundWorkerExecute.CancelAsync();
                Cursor = Cursors.WaitCursor;
                buttonExecute.Enabled = false;
                return;
            }
            var system = ptFileTreeView.SelectedFile;
            var brandList = comboBoxBrandList.SelectedItem;
            if (system == null || brandList == null)
                return;
+            _startTime = DateTime.Now;
            buttonExecute.Text = "中断";

private void buttonExecute_Click(object sender, EventArgs e)

{

if (backgroundWorkerExecute.IsBusy)

{

backgroundWorkerExecute.CancelAsync();

Cursor = Cursors.WaitCursor;

buttonExecute.Enabled = false;

return;

}

var system = ptFileTreeView.SelectedFile;

var brandList = comboBoxBrandList.SelectedItem;

if (system == null || brandList == null)

return;

+ _startTime = DateTime.Now;

buttonExecute.Text = "中断";

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

バックテスト完了後に売買結果をテキストに保存する（システムトレード）

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

        private void backgroundWorkerExecute_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
...(中略)
               // ファイルに書き出しをする
                _endTime = DateTime.Now;
                TimeSpan ts = _endTime - _startTime;
                File.WriteAllText(@".\data\log\lasttrading.txt",
                         "実行時間 = " + (int)ts.Days + "日" +
                                         (int)ts.Hours + "時間" +
                                         (int)ts.Minutes + "分" +
                                         (int)ts.Seconds + "秒\r\n" +
                         textBoxExecute.Text);

private void backgroundWorkerExecute_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)

{

...(中略)

// ファイルに書き出しをする

_endTime = DateTime.Now;

TimeSpan ts = _endTime - _startTime;

File.WriteAllText(@".\data\log\lasttrading.txt",

"実行時間 = " + (int)ts.Days + "日" +

(int)ts.Hours + "時間" +

(int)ts.Minutes + "分" +

(int)ts.Seconds + "秒\r\n" +

textBoxExecute.Text);

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

遅い部分を特定する

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

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

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

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

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

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

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

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

#loop-type: date-only

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

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

これが遅いのでは？

という指摘を頂いた。

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

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

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

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

という推測。

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

if ! (diffma25 && diffma5 && {-1}Close && Close && {-2}Close && {-3}Close)
         return
end
if ! (Volume && {-1}Volume && {-2}Volume)
       return
end
if (SalesValue2()/3 + {-1}SalesValue2()/3 + {-2}SalesValue2()/3 <= 50000 && Close <= 50)
       return
end

if ! (diffma25 && diffma5 && {-1}Close && Close && {-2}Close && {-3}Close)

return

end

if ! (Volume && {-1}Volume && {-2}Volume)

return

end

if (SalesValue2()/3 + {-1}SalesValue2()/3 + {-2}SalesValue2()/3 <= 50000 && Close <= 50)

return

end

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

//  過去のClose/Volume を保有する
def CloseVolume_new(days)
	obj = [10]
	obj[0] = null // {-3}Close
	obj[1] = null // {-2}Close
	obj[2] = null // {-1}Close
	obj[3] = null // Close
	obj[4] = null // {-3}Volume
	obj[5] = null // {-2}Volume
	obj[6] = null // {-1}Volume
	obj[7] = null // Volume
	obj[8] = [days]
	obj[9] = null // preserve dropped value
	return obj
end

def CloseVolume_next(obj)
	obj[0] = obj[1]
	obj[1] = obj[2]
	obj[2] = obj[3]
	obj[3] = Close
	obj[4] = obj[5]
	obj[5] = obj[6]
	obj[6] = obj[7]
	obj[7] = Volume
end

// 過去のClose/Volume を保有する

def CloseVolume_new(days)

obj = [10]

obj[0] = null // {-3}Close

obj[1] = null // {-2}Close

obj[2] = null // {-1}Close

obj[3] = null // Close

obj[4] = null // {-3}Volume

obj[5] = null // {-2}Volume

obj[6] = null // {-1}Volume

obj[7] = null // Volume

obj[8] = [days]

obj[9] = null // preserve dropped value

return obj

end

def CloseVolume_next(obj)

obj[0] = obj[1]

obj[1] = obj[2]

obj[2] = obj[3]

obj[3] = Close

obj[4] = obj[5]

obj[5] = obj[6]

obj[6] = obj[7]

obj[7] = Volume

end

この実装では、当日の処理をしている際にメモリに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氏の高スペックデイトレ戦略有効性検証（システムトレード）

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

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

【ソートを使う場合】

i = -1
while (i + 1 < $code_num)
        i = i + 1
        {codes[i]}Sort(i)
end

i = -1

while (i + 1 < $code_num)

i = i + 1

{codes[i]}Sort(i)

end

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

i = -1
a1 = 0
while (i + 1 < $code_num)
        i = i + 1
        if ($buyflag[i][0])
              $sortList2[a1] = codes[i]  //証券コードを記録
              a1 = a1 + 1
        end
end

i = -1

a1 = 0

while (i + 1 < $code_num)

i = i + 1

if ($buyflag[i][0])

$sortList2[a1] = codes[i] //証券コードを記録

a1 = a1 + 1

end

で計測。

【オリジナル】

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

【Sortなし】

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

つまり、こういうこと。

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

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

原因箇所の特定

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

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

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

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

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

それは確かに遅そうだ。

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

【Protra】買い銘柄に優先順位をつける | グコウログ

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

//==================================================
// Swap
//==================================================
def Swap(i, a1)
         a2 = 0
         while (a2 < $buyCnt - a1 - 1)
                   $sortList1[$buyCnt - a2 - 1] = $sortList1[$buyCnt - a2 - 2] //値 並び替え
                   $sortList2[$buyCnt - a2 - 1] = $sortList2[$buyCnt - a2 - 2] //証券コード並び替え
                   a2 = a2 + 1
         end
         $sortList1[a1] = $buyflag[i][1] //値を置き換え
         $sortList2[a1] = Code  //証券コードを記録
         $sortCnt = $sortCnt + 1
end

//==================================================
// 昇順/降順($reverse = 1)にソート（各種ストラテジーの買いをまとめて扱う）
//==================================================
def Sort(i)
         a1 = 0
         // Main関数で買いルールを満たした銘柄
         if ($buyflag[i][0])
                  while (a1 < $buyCnt) // 一件ずつ
                           if (a1 == $sortCnt)
                                    $sortList1[a1] = $buyflag[i][1] // 昇順/降順ソーティングに使用する変数値
                                    $sortList2[a1] = Code     //証券コードを記録
                                    $sortCnt = $sortCnt + 1
                                    break
                           elsif ($reverse && $buyflag[i][1] > $sortList1[a1])
                                    Swap(i, a1)
                                    break
                           elsif (! $reverse && $buyflag[i][1] < $sortList1[a1])
                                    Swap(i, a1)
                                    break
                           end
                           a1 = a1 + 1
                  end
         end
end

//==================================================

// Swap

//==================================================

def Swap(i, a1)

a2 = 0

while (a2 < $buyCnt - a1 - 1)

$sortList1[$buyCnt - a2 - 1] = $sortList1[$buyCnt - a2 - 2] //値並び替え

$sortList2[$buyCnt - a2 - 1] = $sortList2[$buyCnt - a2 - 2] //証券コード並び替え

a2 = a2 + 1

end

$sortList1[a1] = $buyflag[i][1] //値を置き換え

$sortList2[a1] = Code //証券コードを記録

$sortCnt = $sortCnt + 1

end

//==================================================

// 昇順/降順($reverse = 1)にソート（各種ストラテジーの買いをまとめて扱う）

//==================================================

def Sort(i)

a1 = 0

// Main関数で買いルールを満たした銘柄

if ($buyflag[i][0])

while (a1 < $buyCnt) // 一件ずつ

if (a1 == $sortCnt)

$sortList1[a1] = $buyflag[i][1] // 昇順/降順ソーティングに使用する変数値

$sortList2[a1] = Code //証券コードを記録

$sortCnt = $sortCnt + 1

break

elsif ($reverse && $buyflag[i][1] > $sortList1[a1])

Swap(i, a1)

break

elsif (! $reverse && $buyflag[i][1] < $sortList1[a1])

Swap(i, a1)

break

end

a1 = a1 + 1

end

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

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

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

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

まとめ

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

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

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

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

匿名より:

5月28日 8:51 AM

Sortライブラリーを使ってみてください
nehori より:

5月28日 9:20 AM

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

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

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

5月28日 2:09 PM

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

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

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

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

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

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

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

5月28日 5:17 PM

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

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