Bitflyerの板情報の差分から、板情報を構築する方法

ビットコインのシステムトレードについてです。
BitflyerのAPIで、板情報が取得できます。
システムトレードをする場合、板情報を頻繁に確認することになります。
そうした場合、Bitflyerでは、RealtimeAPIというものが用意されています。

WebScoketで、板情報の差分のみが流れてくるので、それを元に、板情報を再構築しないといけません。
まあ、どんなに遅くてもいいなら、なんとでもなるわけですがそういうわけにもいきません。
システムトレードは、速度が命です。1ミリ秒遅くなったら、命に係わるのです。しらんけど。

おなじみの環境はC#です。ええ、私は今はC#しか書きませんので。

さて、まず思いつくのは、Listあたりにデータを突っ込んでおいて、使うときに並び替える方法。
板情報は、ほぼ、Bid/Askの境目の中央部分しか使いません。
当然、毎回並び替えることになるので、結構無駄が多そうです。

とすると、並んだ状態で保持されるものになるので、SortedList,SortedSet,SortedDictionaryあたりでしょうか。
差分情報は、追加・変更と削除が混ざって飛んでくるので、頻繁な追加・削除が発生します。
SortedListは、途中の追加・削除は遅いので無理。
SortedSet,SortedDictionaryが候補になります。

SortedSetは、Keyのみ、SortedDictionaryは、KeyValueになるので、普通に考えるとSortedDictionary。
ソースコードを確認したら、SortedDictionaryは内部で、SortedSetを使っているのですね。

とりあえず、SortedDictionaryを用いたサンプルコードがこちら。
jsonの取得、Deserializeとかは割愛。

var bids = new SortedDictionary<long, double>(new ReverceSortLong());
var asks = new SortedDictionary<long, double>(new SortLong());

上で定義して

long price;
double size;
var bidsData = diff.Bids;
for (int i = 0; i < bidsData.Length; i++)
{
    (price, size) = bidsData[i];
    if (size == 0.0)
    {
        bids.Remove(price); // あったら消す、無くても問題ない(なにもしない)
    }
    else
    {
        bids[price] = size;
    }
}
if (bids.Any())
{
    var bidFirstPrice = bids.First().Key;
    while (true)
    {
        if (asks.Count == 0) { break; }
        var askFirstPrice = asks.First().Key;
        if (bidFirstPrice < askFirstPrice) { break; }
        asks.Remove(askFirstPrice);
    }
}

var asksData = diff.Asks;
for (int i = 0; i < asksData.Length; i++)
{
    (price, size) = asksData[i];
    if (size == 0.0)
    {
        asks.Remove(price); // あったら消す、無くても問題ない(なにもしない)
    }
    else
    {
        asks[price] = size;
    }
}
if (asks.Any())
{
    var askFirstPrice = asks.First().Key;
    while (true)
    {
        if (bids.Count == 0) { break; }
        var bidFirstPrice = bids.First().Key;
        if (bidFirstPrice < askFirstPrice) { break; }
        bids.Remove(bidFirstPrice);
    }
}

こちらで更新。

とりあえずこれで、ぼちぼちの速度で動きそうです。
ちょっと変なことしている部分を説明しておくと、通常、bidsの価格＜asksの価格なわけですが、bidsの最高値>asksの最低値となってしまったりするとまずいことが起きます。
普通は起きないはずでしょうが、昔そのようなことが起きる問題があったようなので、bid更新後に、asksの方が低いのがあればasksのその部分を削除。
ask更新後の逆も同じという処理を入れてあります。

実は、SortedDictionaryを使わずに、SortedSet+Dictionaryに分けた実装をしたらもっと速くなりました。
SortedDictionaryはCompare周りとか結構無駄が多いです。
さらに、SortedSetに、板情報を扱うとしたら不利な部分がいくつかあったので、SortedSetをコピー・改造したらもっと速くすることができるのですが、そちらについてはそのうち記事を書きますね。