[二分探索]少ないAPIリクエストで効率的にbitFlyer約定履歴を検索する
データ分析やバックテストにおいて最も重要で基本となるデータの一つが約定履歴データ(executions)です。
bitFlyerでは約定履歴データをREST APIで取得することはできますが、取得条件としてid(約定履歴毎に付与される一意の連番)のみ絞り込みが可能となっています。
また、一回のAPIリクエストで最大500件までしかデータ取得ができません。そのため、任意の時刻のデータを抽出するには、取得した約定履歴の時刻(exec_date)をチェックしながら、繰り返しAPIリクエストを行い、検索する必要があります。
本noteでは約定履歴データの制約と特性から二分探索を用いて少ないAPIリクエストで効率的に指定時刻の約定履歴を検索する方法を解説します。
[注意]
・本内容は分析・検証などにおけるデータ取得を想定しており、リアルタイム性が重要なbotなどに活用する手法ではありません。
・また、本内容の適用範囲はREST APIの仕様に依存します。
2018 年 12 月 19 日より、 before パラメータで取得できる約定履歴は、過去 31 日分となります。(bitFlyer Lightning API Documentationより抜粋)
【0. 目次】
■ 1. bitFlyerの約定履歴取得について
■ 2. 二分探索とは
■ 3. 二分探索の約定履歴への適用
■ 4. 二分探索での約定履歴検索の流れ
■ 5. コードサンプル
【1. bitFlyerの約定履歴取得について】
bitFlyerの約定履歴の概要を以下に示します。
[リクエスト]
GET /v1/getexecutions
[クエリパラメータ]
product_code : 通貨ペア
count : 取得する件数(最大500件)
before : 指定したid未満(過去)に絞り込み
after : 指定したidより大きい(未来)に絞り込み
約定履歴データはafter < id < beforeの中で新しいデータからcount件数分が新→古順リストで取得されます。
[レスポンス]
約定履歴(execution)データ形式
id : 約定履歴ID(一意の連番)
side : テイカー注文側(BUY or SELL)
price : 約定価格
size : 約定サイズ
exec_date : 約定日時(UTC)
buy_child_order_acceptance_id : 買い側の注文受付ID
sell_child_order_acceptance_id : 売り側の注文受付ID
[
{
"id": 39287,
"side": "BUY",
"price": 31690,
"size": 27.04,
"exec_date": "2015-07-08T02:43:34.823",
"buy_child_order_acceptance_id": "JRF20150707-200203-452209",
"sell_child_order_acceptance_id": "JRF20150708-024334-060234"
},
{
"id": 39286,
"side": "SELL",
"price": 33170,
"size": 0.36,
"exec_date": "2015-07-08T02:43:34.72",
"buy_child_order_acceptance_id": "JRF20150708-010230-400876",
"sell_child_order_acceptance_id": "JRF20150708-024334-197755"
}
]API詳細については「bitFlyer Lightning API Documentation」を参照してください。
また、「bitFlyer Lightning API Playground」にてAPIリクエストを簡単に行うことができますので、動作確認を行う場合はそちらも併せて参照してください。
上記概要の中で重要なポイントとして、
・約定履歴データは時系列に連続した一意の連番(id)でソート済
・idのみでの取得範囲の絞り込み(時刻ではできない)
・1回のAPIリクエストで最大500件
となります。
上記を踏まえて、任意時刻の約定履歴を検索する最もシンプルな方法は現在の最新約定履歴から約定日時を順にチェックしながら該当データが見つかるまで繰り返しidを遡る方法(線形探索)です。
上記の例では検索時刻が現在に近いため、APIリクエストは少ない回数で検索できていますが、これが1日前、3日前、1週間前・・・と過去になるにつれてさかのぼる約定履歴が膨大になり、APIリクエスト回数が飛躍的に増えてしまいます。
仮に1日の約定履歴が200万件だったとすると、1日前を検索するのに
200万件 ÷ 500件/リクエスト ＝ 4,000リクエスト
1リクエストを0.5秒とすると
4,000リクエスト × 0.5秒 ＝ 2,000秒(約33分)
※RateLimitや遅延などもあり、0.5秒では取得できない場合もあります。
4,000回のAPIリクエストを30分以上かけて行う必要があります。
これは時間的にも通信トラフィック的にも無駄や負荷が大きいです。
そこで、この約定履歴の仕様と特性の中で検索を効率的に行う方法として「二分探索」を用います。
参考比較のため、「線形探索」のコードサンプルを以下に示します。
(サンプルのため、細かいエラー処理などは割愛してあります。)
# -*- coding: utf-8 -*-
import time
import requests
from datetime import datetime
from pytz import utc
# 検索時刻(JST)
target_dt = "2019/01/29 16:50:00"
def main():
# 処理開始時刻
start_time = time.time()
# APIリクエスト回数
request_count = 0
# 検索時刻をUTC変換
dt = datetime.strptime(target_dt + "+0900", "%Y/%m/%d %H:%M:%S" + "%z")
utc_dt = dt.astimezone(utc)
print("[target date(JST)] {} -> [UTC] {}".format(target_dt, utc_dt))
# 検索時刻まで繰り返し
cur_dt = datetime.now(utc)
cur_id = None
params = dict(product_code="FX_BTC_JPY", count=500)
while utc_dt < cur_dt:
try:
# 約定履歴取得
if cur_id:
params["before"] = cur_id
response = requests.get("https://api.bitflyer.com/v1/getexecutions", params=params).json()
# 経過表示
request_count += 1
if request_count % 10 == 0:
print("[current id] {} [current date] {} [api call] {} [time] {:.2f} sec".format(
cur_id, cur_dt, request_count, time.time()-start_time))
# 取得結果より、id / 時刻 更新
cur_id = response[-1]["id"]
cur_dt = datetime.strptime(response[-1]["exec_date"] + "+0000", "%Y-%m-%dT%H:%M:%S.%f" + "%z")
time.sleep(0.2)
except Exception as e:
print(e)
return
# executionsは新->旧なので反転
execs = response[::-1]
# 指定時刻後の最初のIDを検索
for ex in execs:
ex_dt = datetime.strptime(ex["exec_date"] + "+0000", "%Y-%m-%dT%H:%M:%S.%f" + "%z")
if utc_dt < ex_dt:
# 検索結果出力
print("[target id] {} [api call] {} [time] {:.2f} sec".format(
ex["id"], request_count, time.time()-start_time))
return
if __name__ == "__main__":
main()
【2. 二分探索とは】
二分探索とは、以下の説明のとおりソート済データを検索する手法です。
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
ウィキペディアより
ポイントはソート済データであることです。
並び順が保証されているため、データの中央の値に対して検索対象が左右どちらにあるかチェックすることができるので、探索する毎に範囲が半減していきます。
二分探索では3回の探索で結果を求めることができました。
それに対して、先ほどの線形探索で右から順に検索すると22→20→19→・・・→6で9回となります。
(左から検索した場合は4回)
上記の例では検索範囲が小さいため、差はあまり出ませんが先ほどの約定履歴200万件のように膨大な範囲になると差は歴然となります。
【3. 二分探索の約定履歴への適用】
約定履歴データは前章で解説したとおり、時系列にidでソートされており、その並び順は約定日時においても同様となります。
そのため、idの中央値で約定履歴データを取得し、約定日時(exec_date)で左右の判定を行うことで二分探索を適用することができます。
現在、約定履歴は1日あたり200～300万件のデータが作成されていますが、二分探索は検索範囲の拡がりが検索コストに与える影響は線形探索に比べてとても小さいため、効率的に検索が可能です。
以下に1日前、1週間前、1ヵ月前を二分探索した結果を示します。
[1日前]
検索範囲 : 約348万
APIリクエスト : 18回
検索時間 : 4.22秒
[1週間前]
検索範囲 : 約2,028万
APIリクエスト : 19回
検索時間 : 4.52秒
[1ヵ月前]
検索範囲 : 約8,940万
APIリクエスト : 21回
検索時間 : 5.21秒
上記の結果からわかるように検索範囲が膨大になっても二分探索のAPIリクエスト数や検索時間は大きくは変わりません。
【4. 二分探索での約定履歴検索の流れ】
それでは具体的にどのような手順で二分探索を行うか解説していきます。
前章までですでにアルゴリズムの解説は終わっているため、コーディングに慣れている方は容易に自力で実装ができると思います。
ここではなるべくシンプルに分かりやすさを重視して解説を行いたいと思いますので、実装例の一つとして参考になれば幸いです。
大まかな流れは以下のとおりです。
① 検索範囲の設定(指定日時からおおよその開始idを算出)
② 検索範囲が500件以下になるまで二分探索
③ 絞り込んだ検索範囲から指定日時の約定履歴を取得
① 検索範囲の設定(指定日時からおおよその開始idを算出)
まずは二分探索を行うデータ範囲をざっくりと設定します。
範囲の末尾は現在の最新約定履歴idとなりますので、先頭(最も過去)のidを設定します。
様々な方法があると思いますが、今回は現在と指定日時の時間差(hours)を求め、１時間あたりの約定履歴を平均12万件として最新約定履歴idから差し引いて設定します。
# -*- coding: utf-8 -*-
import time
import requests
from datetime import datetime
from pytz import utc
# 検索時刻(JST)
target_dt = "2019/01/20 15:00:00"
# 検索時刻(JST)をdatetime(UTC)に変換
dt = datetime.strptime(target_dt + "+0900", "%Y/%m/%d %H:%M:%S" + "%z")
target_date = dt.astimezone(utc)
# target_dateと現在時刻のおおまかな時間差
hours = int((time.time() - target_date.timestamp()) / 3600) + 1
# 最新約定履歴ID取得
params = dict(product_code="FX_BTC_JPY", count=500)
response = requests.get("https://api.bitflyer.com/v1/getexecutions", params=params).json()
end_id = response[0]["id"]
# 二分探索開始ID設定
start_id = end_id - hours * 120000 # 平均12万件/時間と仮定する
これで二分探索の検索範囲(start_id～end_id)が求まりました。
しかし、ここで設定したstart_idは概算で算出したため、範囲内に指定時刻が含まれていない可能性があります。
そのため、start_idの約定履歴を取得し、指定時刻より過去になっているかチェックします。
# 設定した開始IDがtarget_dateより過去になっているかチェック
# start_idの約定履歴を取得
params["before"] = start_id + 1
response = requests.get("https://api.bitflyer.com/v1/getexecutions", params=params).json()
# start_idの約定日時(exec_date)をdatetime(UTC)変換
start_date = datetime.strptime(response[0]["exec_date"] + "+0000", "%Y-%m-%dT%H:%M:%S.%f" + "%z")
# target_dateより過去日時になるまでstart_idをずらす
while start_date > target_date:
# 1時間分(12万件)idを差し引いて約定履歴を再取得
start_id -= 120000
params["before"] = start_id + 1
response = requests.get("https://api.bitflyer.com/v1/getexecutions", params=params).json()
# start_idの約定日時(exec_date)をdatetime(UTC)変換
start_date = datetime.strptime(response[0]["exec_date"] + "+0000", "%Y-%m-%dT%H:%M:%S.%f" + "%z")
二分探索では検索範囲の拡がりに大きな影響を受けないため、start_idの設定では検索対象よりも過去であれば、大きく離れたidでもあまり問題ありません。
② 検索範囲が500件以下になるまで二分探索
検索範囲のstart_id、end_idより中央値(mid_id)を算出し、その約定履歴を取得します。
取得した約定履歴の約定日時(exec_date)と検索日時(target_date)を比較し、検索範囲が500件以下(1リクエストで取得できる範囲)まで絞り込みを行っていきます。
# 検索範囲が500件以下になるまで絞り込み
while end_id - start_id > 500:
# idの中央値を算出
mid_id = int((start_id + end_id)/2)
# 中央値の約定履歴を取得
params["before"] = mid_id + 1
response = requests.get("https://api.bitflyer.com/v1/getexecutions", params=params).json()
# 中央値の約定日時(exec_date)をdatetime(UTC)変換
mid_date = datetime.strptime(response[0]["exec_date"] + "+0000", "%Y-%m-%dT%H:%M:%S.%f" + "%z")
# mid_dateがtarget_dateの左右どちらかチェック
if mid_date < target_date:
# target_dateは中央値よりも右(未来)のため、start_idをずらす
start_id = mid_id
else:
# target_dateは中央値よりも左(過去)のため、end_idをずらす
end_id = mid_id
③ 絞り込んだ検索範囲から指定日時の約定履歴を取得
検索範囲が500件以下になったため、end_idまでの500件を取得し、最も過去の約定履歴から順に指定時刻を超えるまで検索します。
指定時刻を超えた最初のidが検索結果となります。
# 絞り込んだend_idまでの約定履歴を取得
params["before"] = end_id + 1
response = requests.get("https://api.bitflyer.com/v1/getexecutions", params=params).json()
# 約定履歴リストは新→古順のため、反転する
execs = response[::-1]
# 指定時刻後の最初のIDを検索
for ex in execs:
ex_date = datetime.strptime(ex["exec_date"] + "+0000", "%Y-%m-%dT%H:%M:%S.%f" + "%z")
if target_date < ex_date:
# 検索結果出力
print("[target id] {}".format(ex["id"]))
break
以上で二分探索を用いた効率的な約定履歴の検索の解説は終わりです。
以下の有料部では、これまでに解説した内容をまとめ、エラー処理やコンソール出力を加えて関数化したコードサンプルになります。
(コードの骨子はこれまでに解説してきたとおりです。)
コードサンプルに興味がある方、本noteに価値を感じてサポートしてくださる方はご購入ください。
ここから先は
¥ 500
Amazonギフトカード5,000円分が当たる
この記事が気に入ったらチップで応援してみませんか？