AtCoderでPython使いが茶色になるまでにやったこと。
この記事では、AtCoderで茶色になるまでにやったことを紹介していきます。
目次:
- 自己紹介
- 競技プログラミングを始める
- 初コンテストに参加する
- とりあえずABCには参加する
- ABC142で四完を達成する
- きりみんちゃんを見る
- ライブラリをつくる
- AtCoderProblemsの新ABCを埋める
自己紹介
今回のABC148で無事茶色になれた名無しのマイナーです。 茶色になるのは思っているよりも高い目標で、ここに来るまで五ヶ月がかかりました。
ABC148では簡単な問題が多めでしたが、そうであるからこそ練習量が生きたとも思っています。
競技プログラミングを始める
もともと、仮想通貨関係のプログラムを趣味で書いており、プログラミングはある程度していたのですが、 競技プログラミングは名前を聞いたことがある程度で、本格的にしたことはありませんでした。
ですが、Twitterを見ていると
★競技プログラミング★
— Lillian (@Lily0727K) 2019年8月4日
AtCoder Beginner Contest 136
65分5完で221位
パフォーマンス：1991
レーティング：1569→1624
念願の青色に昇格しました！(≧▽≦)
とりあえずの目標だったので、無事に達成できて嬉しいです！ pic.twitter.com/m1i4ajO7qm
というTweetが目に入り、「五ヶ月で青色」という圧倒的事実に惹かれ、競技プログラミングをはじめました。（今思うと、5ヶ月で青色がすごいとなぜ五知っていたのかは謎）
初コンテストに参加する
今でもなんとなく覚えています。 初参加したコンテストはAtCoderBeginnerContest 136でした。
A問題とB問題を標準入力の方法をググりながらもACしました。 しかし、C問題が解けませんでした。
解説放送を見ながら納得したのを覚えています。
ちなみに、ついたレートはでした
とりあえずABCには参加する
とりあえず参加していました。 純粋に楽しいし、解けない問題が解けると気持ちいいからです。 この期間は解けなかった問題の解説を見る程度の勉強をしていました。
ですが、コンテストのために精進するほどモチベーションはなかったので、あまり精進はしませんでした。
ABC142で四完を達成する
D問題は整数に関する問題でしたが、初めてD問題をコンテスト中に解くことができました。 このあたりで、コンテスト中にググることの大切さを学んだ気がします。
きりみんちゃんを見る
バーチャル幼女プログラマー(７歳)として、AtCoderの過去問を解く配信をしているVtuberの「きりみんちゃん」という方がいるのですが、 彼女も当時の僕より少しレートが高いぐらいで、勝手にライバル認定していました。
配信を見ながら並走して解くと、自分が先に解こうとする競争心が働くのでいい感じです。 彼女はたぶん僕より実装力は高いですが、数学力は僕のほうが高いです。
また最近は数学的傾向の強いコンテストが多いので、僕がきりみんちゃんを抜かせたんだと思います。(といっても50も差はない)
ライブラリをつくる
Pythonはとくに、もともとあるライブラリなどが多いので(fractions.gcd()など)、C++を使っている方々よりは、ライブラリの必要性は下がると思うのですが、 それでもやっぱりライブラリがあると便利です。
具体的にあるライブラリを列挙すると
- 条件の二分探索(年齢あてゲームなどで使うアレ）
- 二次元リストの回転 (行と列をListでとれるようになる)
- bit全列挙
nCk mod p を素早くやるアレ 参考: よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
文字列から部分文字列を探し、その部分文字列が始まるindexを返す関数(AtCoderのPythonは3.4であるため、find関数がつかえない）
とかですね。 いわゆる「貼るだけ」問題もABCのB問題やC問題に存在したりするので、少しでもパフォを上げたい灰色の方にはおすすめです。
AtCoderProblemsの新ABCを埋める
AtCoderProblemsというAtCoderの過去問をまとめて見れるサイトがあるのですが、そこで新ABCの過去問を解いていました。 茶色を目指すだけだったら、新ABCのA,B,Cだけを埋めるだけで十分だと思います。
ちなみに、僕は最近やっと100ACいきました。
また、「攻めの精進」と「守りの精進」という考えたもあるようです。 自分が明らかに解ける範囲のDifficultyの問題を解いて、基礎や知識を固めることを「守りの精進」、 ギリギリ解けるかわからないラインの問題を解いて考察力などをつけることを「攻めの精進」とするそうです。
守りの精進をすることによって、コンテスト中のパフォーマンスが安定し、 攻めの精進をすることによって、パフォーマンスの最大値があがるそうです。
継続的な精進だけでなく、戦略的な精進が求められそうです。
日々是精進!
PythonとWebsocketを使ってMEXの板情報を高速に扱いたい コーディング篇
はい。 この記事では、僕がBitMEXの板情報(いわゆるOrderBook)を扱うときに困った点や、それを解決した方法について書きます。
追記:色々とバグを直したバージョンを公開しました:
なぜWebsocketを使って板情報を扱うのか
デイトレードレベルの頻度でAPIにアクセスするなら、実装ハードルも低いREST APIを使えばいいのですが、 HFTをしようともなると、いちいちアクセスしていてはAPI Limitが枯渇してしまいます。
そこで、では、僕がBitMEXの板情報(いわゆるOrderBook)を扱うときに困った点や、それを解決した方法について書きます。
なぜWebsocketを使って板情報を扱うのか
デイトレードレベルの頻度でAPIにアクセスするなら、実装ハードルも低いREST APIを使えばいいのですが、 HFTをしようともなると、いちいちアクセスしていてはAPI Limitが枯渇してしまいます。
そこで、Websocketを使うことで、API Limitを消費することなく、リアルタイムにOrderBookを高速に扱うことができるのです。 BitMEX先輩もそう言っています。
BitMEX ではリアルタイムデータを購読可能です。 このアクセスはいったん接続するとレートの制限がなくなるため、プログラムに最新データを取り込む最適な方法です。
https://www.bitmex.com/app/wsAPI
公式コネクタを使ってみる
このページにたどり着く皆さんは、BitMEXの公式コネクタの存在を知っていると思います。 ですが、それと同時に公式コネクタはとても遅いこともご存知だと思います。
それについては、よく検証されたnoteがあるのでそちらを参照してください。
公式コネクタが遅いことがよく分かると思います。
モッチオさんのnoteに貼ってあるものを試す。
モッチオさんのnoteには、公式コネクタをindexを記憶した辞書を使うことによって高速化されたコネクタのコードがあるのですが、 下記noteやコメント欄を見ると分かる通り、完璧なindex管理がなされておらず、時間がたつとorderbookの情報がズレてしまいます。
そこで、上記noteを書いたmatsuoさんのPuppetterというフレームワークはMITライセンスで公開されているため、 WebSocketコネクタのソースコードを覗いてみました。
puppeteer/inmemorydb_bitmex_websocket.py at master · o-matsuo/puppeteer · GitHub
想像以上に行数が多く、他のプログラムとも結合しているために、コピペは断念(そりゃそう)。
自分で作ることにしました。
自分で作る
そもそもなぜ公式コネクタが遅いのかは、配列の検索するメソッドにあります。 それをindex配列を作ることでモッチオさんは高速化をしていましたが、私はOrderBookさえとれればいいので、 OrderBookの情報をPandasのDataFrameとして扱うことによって、ライブラリの力で高速化しました。
import websocket import threading from time import sleep import json import urllib import sys import pandas as pd #おまじない from logging import Formatter, getLogger, StreamHandler, DEBUG class BitMEXWebsocket: max_table_len = 200 def __init__(self, endpoint, symbol): self.formatter = Formatter('%(asctime)-15s - %(levelname)-8s - %(message)s') self.logger = getLogger(__name__) self.handler = StreamHandler(sys.stdout) self.handler.setLevel(20) self.handler.setFormatter(self.formatter) self.logger.setLevel(20) self.logger.addHandler(self.handler) self.endpoint = endpoint self.symbol = symbol self.exited = False self.df = pd.DataFrame() wsurl = self.__get_url() self.logger.info('Connecting to %s' % wsurl) self.__connect(wsurl, symbol) self.logger.info('Connected to WS.') self.__wait_for_symbol(symbol) def __wait_for_symbol(self, symbol): while self.df.empty: sleep(0.1) def __get_url(self): symbolSubs = ["orderBookL2_25"] genericSubs = ["margin"] subscriptions = [sub + ':' + self.symbol for sub in symbolSubs] subscriptions += genericSubs urlparts = list(urllib.parse.urlparse(self.endpoint)) urlparts[0] = urlparts[0].replace('http', 'ws') urlparts[2] = "/realtime?subscribe={}".format(','.join(subscriptions)) return urllib.parse.urlunparse(urlparts) def __connect(self, wsurl, symbol): self.logger.debug('Starting thread') self.ws = websocket.WebSocketApp(wsurl, on_message=self.__on_message, on_close=self.__on_close, on_open=self.__on_open, on_error=self.__on_error) self.wst = threading.Thread(target=lambda: self.ws.run_forever()) self.wst.daemon = True self.wst.start() self.logger.debug('Started thread') sleep(5) def __on_message(self, message): message = json.loads(message) action = message['action'] data = message['data'] if action == 'partial': self.df = pd.io.json.json_normalize(data) self.df.to_csv('orderbook.csv') elif action == 'update': df_data = pd.io.json.json_normalize(data) indicies, Is = self.search_index(self.df, df_data) for i in range(len(indicies)): index = indicies[i] id = self.df.iloc[index]['id'] self.df.iloc[index] = df_data.iloc[Is[i]] self.df['price'].iloc[index] = -0.01 * id + 88000000 elif action == "delete": df_data = pd.io.json.json_normalize(data) indicies, Is = self.search_index(self.df, df_data) self.df.drop(index=self.df.index[indicies], inplace=True) self.df = self.df.sort_values('price', ascending=False) self.df.reset_index(inplace=True, drop=True) elif action == "insert": df_data = pd.io.json.json_normalize(data) self.df = pd.concat([self.df, df_data], sort=True) self.df = self.df.sort_values('price', ascending=False) self.df.reset_index(inplace=True, drop=True) def __on_error(self, error): if not self.exited: self.logger.error("Error : %s" % error) raise websocket.WebSocketException(error) def __on_open(self): self.logger.debug('Websocket Opened') def __on_close(self): self.logger.info('Websocket Closed') def get_orderbook(self): return self.df def search_index(self, a, b): # DataFrame a から DataFrame Bと一致する行を探す indicies = list() Is = list() # self.logger.debug(a) for i in range(len(b)): id = b.iloc[i]['id'] side = b.iloc[i]['side'] index = a.query('id == {} and side == "{}"'.format(id, side)).index[0] indicies.append(index) Is.append(i) return indicies, Is if __name__ == "__main__": bmw = BitMEXWebsocket(endpoint='wss://www.bitmex.com/realtime', symbol='XBTUSD') while True: sleep(1)
このクラスの関数get_orderbook()を呼ぶことでOrderBookを得ることができるのですが、 NaNが入ってしまうというバグに悩まされているため、現在調査中です
To be continued....
次回に続く...
追記:色々とバグを直したバージョンを公開しました:
