フォローしました¥500データ分析やバックテストにおいて最も重要で基本となるデータの一つが約定履歴データ(executions)です。APIで取得することはできますが、取得条件としてid(約定履歴毎に付与される一意の連番)のみ絞り込みが可能となっています。一回のAPIリクエストで最大500件までしかデータ取得ができません。そのため、任意の時刻のデータを抽出するには、取得した約定履歴の時刻(exec_date)をチェックしながら、繰り返しAPIリクエストを行い、検索する必要があります。本noteでは約定履歴データの制約と特性から二分探索を用いて少ないAPIリクエストで効率的に指定時刻の約定履歴を検索する方法を解説します。[注意]・本内容は分析・検証などにおけるデータ取得を想定しており、リアルタイム性が重要なbotなどに活用する手法ではありません。APIの仕様に依存します。bitFlyerの約定履歴取得について】bitFlyerの約定履歴の概要を以下に示します。beforeの中で新しいデータからcount件数分が新→古順リストで取得されます。Documentation」を参照してください。Playground」にてAPIリクエストを簡単に行うことができますので、動作確認を行う場合はそちらも併せて参照してください。・idのみでの取得範囲の絞り込み(時刻ではできない)・1回のAPIリクエストで最大500件となります。上記を踏まえて、任意時刻の約定履歴を検索する最もシンプルな方法は現在の最新約定履歴から約定日時を順にチェックしながら該当データが見つかるまで繰り返しidを遡る方法(線形探索)です。上記の例では検索時刻が現在に近いため、APIリクエストは少ない回数で検索できていますが、これが1日前、3日前、1週間前・・・と過去になるにつれてさかのぼる約定履歴が膨大になり、APIリクエスト回数が飛躍的に増えてしまいます。2,000秒(約33分)※RateLimitや遅延などもあり、0.5秒では取得できない場合もあります。4,000回のAPIリクエストを30分以上かけて行う必要があります。これは時間的にも通信トラフィック的にも無駄や負荷が大きいです。そこで、この約定履歴の仕様と特性の中で検索を効率的に行う方法として「二分探索」を用います。参考比較のため、「線形探索」のコードサンプルを以下に示します。(サンプルのため、細かいエラー処理などは割愛してあります。二分探索とは、以下の説明のとおりソート済データを検索する手法です。中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。ウィキペディアよりポイントはソート済データであることです。並び順が保証されているため、データの中央の値に対して検索対象が左右どちらにあるかチェックすることができるので、探索する毎に範囲が半減していきます。二分探索では3回の探索で結果を求めることができました。それに対して、先ほどの線形探索で右から順に検索すると22→20→19→・・・→6で9回となります。(左から検索した場合は4回)上記の例では検索範囲が小さいため、差はあまり出ませんが先ほどの約定履歴200万件のように膨大な範囲になると差は歴然となります。約定履歴データは前章で解説したとおり、時系列にidでソートされており、その並び順は約定日時においても同様となります。そのため、idの中央値で約定履歴データを取得し、約定日時(exec_date)で左右の判定を行うことで二分探索を適用することができます。現在、約定履歴は1日あたり200~300万件のデータが作成されていますが、二分探索は検索範囲の拡がりが検索コストに与える影響は線形探索に比べてとても小さいため、効率的に検索が可能です。以下に1日前、1週間前、1ヵ月前を二分探索した結果を示します。上記の結果からわかるように検索範囲が膨大になっても二分探索のAPIリクエスト数や検索時間は大きくは変わりません。二分探索での約定履歴検索の流れ】それでは具体的にどのような手順で二分探索を行うか解説していきます。前章までですでにアルゴリズムの解説は終わっているため、コーディングに慣れている方は容易に自力で実装ができると思います。ここではなるべくシンプルに分かりやすさを重視して解説を行いたいと思いますので、実装例の一つとして参考になれば幸いです。大まかな流れは以下のとおりです。検索範囲の設定(指定日時からおおよその開始idを算出)まずは二分探索を行うデータ範囲をざっくりと設定します。範囲の末尾は現在の最新約定履歴idとなりますので、先頭(最も過去)のidを設定します。様々な方法があると思いますが、今回は現在と指定日時の時間差(hours)を求め、1時間あたりの約定履歴を平均12万件として最新約定履歴idから差し引いて設定します。平均12万件/時間と仮定するこれで二分探索の検索範囲(start_id~end_id)が求まりました。ここで設定したstart_idは概算で算出したため、範囲内に指定時刻が含まれていない可能性があります。そのため、start_idの約定履歴を取得し、指定時刻より過去になっているかチェックします。"%z")二分探索では検索範囲の拡がりに大きな影響を受けないため、start_idの設定では検索対象よりも過去であれば、大きく離れたidでもあまり問題ありません。検索範囲のstart_id、end_idより中央値(mid_id)を算出し、その約定履歴を取得します。取得した約定履歴の約定日時(exec_date)と検索日時(target_date)を比較し、検索範囲が500件以下(1リクエストで取得できる範囲)まで絞り込みを行っていきます。検索範囲が500件以下になったため、end_idまでの500件を取得し、最も過去の約定履歴から順に指定時刻を超えるまで検索します。指定時刻を超えた最初のidが検索結果となります。break以上で二分探索を用いた効率的な約定履歴の検索の解説は終わりです。以下の有料部では、これまでに解説した内容をまとめ、エラー処理やコンソール出力を加えて関数化したコードサンプルになります。(コードの骨子はこれまでに解説してきたとおりです。)コードサンプルに興味がある方、本noteに価値を感じてサポートしてくださる方はご購入ください。記事を購入する#python#BTC#ビットコインFX#BOT#BTCFX#bitflyer#BitMEX#アルゴリズム#API#Binary#SEARCH#REST#約定履歴#二分探索#executionsこの記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。サポートをする「スキ」を押してクリエイターを応援しよう!ありがとうございます!よろしければフォロー&シェアも頂けたら幸いです。17Nagi暗号通貨関連の投資、トレードを実践中。Twitterでも情報発信やってます。よかったらフォローしてください。CTO的な何かPythonによるWebスクレイピング2Google検索の結果から...76Daiすべてのプログラマ必見!リトライ処理の効率的な手法、...28Artriggerありがとうございます!よろしければフォロー&シェアも頂けたら幸いです。クリエイターへのお問合せnoteカイゼン目安箱クリエイターの。