【Python】取引シミュレーションの売買タイミング計算の効率化

今回は小ネタ記事です。株や為替, または電力・原油など資源の取引市場では価格が刻々と変動します。今回は市場の価格履歴データから売買タイミングをシミュレーションする際の計算効率化についての備忘録です。
用途のひとつとして, 市場のアノマリー検証が考えられます。内容としてはかなり単純化したケースなので実際にシミュレーションを行うときは現実に則した工夫 (e.g. 予算や保持期間の制約や手数料など) が必要だと思います。

取引シミュレーションの売買タイミング計算

各時点の価格履歴データとして以下の時系列が得られたとする。時点を t_i (0 ≦ i < n) として,  どの時点で購入し, どの時点で売却すると利益が最大になるかを調べる。この例では, Python 3.7  を使い配列構造は NumPy array でなく Python のlist を使う。

prices = [8, 4, 1, 5, 4, 4, 2, 6, 3, 7]

最初に愚直な方法を考える。 最初に i=0 として時点 t_0 で購入し t_{i+1} で売却した時の利益, t_{i+2} で売却した時の利益, … t_{n-1} で売却した時の利益を計算する。次に i を 1 進め, 時点 t_1 で購入, t_{i+1} から t_{n-1} までのそれぞれの時点で売却する。この手続きを i が n-1 まで繰り返す。

max_profit = (0, None, None) # (profit, buy_index, sell_index)

for i in range(len(prices)):
    for j in range(i+1, len(prices)):
        profit = prices[j] - prices[i]
        if max_profit[0] < profit:
            max_profit = (profit, i, j)

上記では, max_profit は (6, 2, 9) となり, 時点 2 で購入し時点 9 で売却すると 6 の利益が得られる。

この方法は O(N^2) となり効率が良くない。(現時点で買ったのを過去に遡っては売れないので未来方向だけになり 1/2 の定数が掛かるがオーダー記法上は無視)

そこで, 現時点 t_{i} の以前の時点 t_{i-1} までの最小値とその時点を保持して, 現時点との差が最大となった時点で売却するように変更すると O(N) に効率化できる。

max_profit = (0, None, None) # (profit, buy_index, sell_index)
min_price = (float('inf'), None)

for i, price in enumerate(prices):
    if price < min_price[0]:
        min_price = (price, i)
    profit = price - min_price[0]
    if max_profit[0] < profit:
        max_profit = (profit, min_price[1], i)

上記では全期間で1度だけ購入/売却を実行しているが, 仮に複数回の取引が可能だとする。ただし, 保有できるのは同時に1単位までとする。
この場合, 売却した後に記録していた最小値と最大差分をリセットするように変更する。

max_profit = 0
total_profit = [] # [(profit, buy_index, sell_index), ...]
min_price = (float('inf'), None)

for i, price in enumerate(prices):
    if price < min_price[0]:
        min_price = (price, i)
    profit = price - min_price[0]
    if max_profit < profit:
        total_profit.append((profit, min_price[1], i))
        min_price = (profit, i)
        max_profit = 0

total_profit は [(4, 2, 3), (4, 6, 7), (4, 8, 9)] となり, 全期間に渡る利益は sum([x[0] for x in total_profit]) で求まり 12 となる。表と図で整理すると以下となる。

Index	0	1	2	3	4	5	6	7	8	9
Obs	8	4	1	5	4	4	2	6	3	7
Min	8	4	1	1	4	4	2	2	3	3
Max diff	0	0	0	4	0	0	0	4	0	4
Profit	0	0	0	4	4	4	4	8	8	12

おわりに

取引回数が指定されない場合は上記方法で良いと思いますが, 取引回数が N 回のみに制限された場合はやや複雑になります。例えば, 2回だけの場合は, 前方向と逆方向から調べた結果を組み合わせて最大の利益とするなどの方法が考えられます。LeetCode に似たような問題があります。
念の為となりますが, 現実には現在 t_i の売買判断に t_{i+1} の価格は使えないので, 今回の記事はシミュレーションの用途に限定されます。