ロスカット判定を高速に計算する

初めまして、今年botを始めたパセリと申します。仮想通貨botter Advent Calendar 2022を見ていたら自分も何か書きたくなってきたので役立つかどうか謎ですがそれ用の記事として投稿させていただきます。初noteです。

losscut priceを設定したい

botを動かしていると時々思わぬ値動きで心が大変痛むことも多々ありまして、まあ筋が悪いからなのですが、約定した値段からx%下がった（上がった）ら損切するロジックを入れたいなと思いました。そしてそれ込みでシミュレーションしたい。

方法の検討

簡単のため、richmanbtc氏のml botチュートリアルを基に説明しようと思います。（いつもお世話になっております）未読の方は先にそちらを読んで頂ければ。

（以下買いの場合を仮定します）やりたいこととしては、足の開始時間t1においてある指値buy_price[t1]が約定したとき、そのポジションが決済されるまでの足t2（この間の足の数は対応するsell_fetをみる）でbuy_price[t1]*(1-x)>lo[i]となる安値loがあればロスカットとして処理します*1。

一番単純な方法としてはt1からt2までのlo全てでbuy_price[t1]*(1-x)と比較すればよいのですが、足の数Nに対して計算量がO(N^2)になりまして、何度も執行シミュレーションを回す場合に時間がかかってしまいます。

そこで全ての(t1,t2)の組み合わせに対してあらかじめ最も小さいloを求めておけば各足に対してO(1)、全体でO(N)で判定できます。めでたしめでたし。

・・・めでたしなのですが、一方メモリはO(N^2)必要で、これは問題です。（問題ですよね？？）そこで配列のある区間における最小値を高速で求めるデータ構造、セグメント木を使います。セグメント木の解説は優良記事が多々ありますので（こちらなど）省略しますが、これによりメモリO(logN)、計算量O(logN)で区間の最小値を求めることができます。

*1: 決済される足内で同時にロスカット基準を満たすとどちらが先か分からず判定できないのですが、とりあえず考えないことにします。

実装

pythonで概要を書きます。セグメント木の実装はやや面倒なのでこちらのライブラリを拝借させていただきます。

import numpy as np
from atcoder.segtree import SegTree


lo = df["lo"].values # 安値の配列

# シミュレーションの前処理としてohlcvからSegTreeを構築しておく、計算量O(N)
# min: セグメント木内での比較用関数、buy側ではmin
# np.inf: セグメント木内でのデフォルト値、buy側ではinf等どのloよりも高くなる値を入れる
seg = SegTree(min, np.inf, lo)


# シミュレーション内で判定する部分、計算量O(logN)
# これを約定した各足で求めるので全体でO(NlogN)
def is_reached(seg:SegTree, t1:int, t2:int, losscut_price:float)->bool:
    return seg.prod(t1, t2) < losscut_price

おわりに

全然そんなことしなくても求まるよ？？みたいな指摘がありましたら是非教えてください。使います。

（追記）もっと速い方法

早速ご指摘がありました（アルゴリズム弱小がばれる）ありがとうございます。

最小値を更新することがないので、Sparse Tableのほうが最小値取得はO(1)となり速いと思います。
（ただ、空間計算量がO(NlogN)になってしまいますが）
(参考:https://t.co/1DlkKQ7KuJ)

— 綴る浪人生@独語地学も勝負 (@Hnot77082254) December 23, 2022

Sparse Tableの解説はこちらなどが分かりやすかったので載せておきます。

TODO: pythonで良いライブラリを見つけたらコードをここに貼る