ISUCON10予選にチーム「カレーおじさん」で参加して16位で予選通過しました
ISUCON10予選に「カレーおじさん」(@tatsumack, @sugaret, @masakingp)というチームで参加しました。
最終スコアは2608で、16位で予選通過することができました。
@sugaret の振り返りはこちら
sugaret.hatenablog.com
予選問題の解説と講評はこちら
isucon.net
チーム「カレーおじさん」
前職の社内ISUCONをきっかけに組んだチームです。昨年、本家ISUCONに初参戦したものの予選で惨敗していました。
事前準備
前回はチームで集まって練習したりしたものの、今回は特に練習する時間を取らずに当日を迎えてしまいました。
チーム練習はしませんでしたが、個人的には、前回のISUCONに参加するときに作っておいた秘伝のタレの見直しやツールの素振り、チームの役割分担の確認を前日の夜に行っていました。
GitHub - tatsumack/isucon-tools: ISUCON秘伝のタレ
こんな感じのスクリプトを用意していました。
- install.sh
- alp, pt-query-digestなどの計測ツールのinstall
- analyze.sh
- alp、pt-query-digestの実行
- ベンチマーク回したら、とりあえず実行する
使用言語
Go
当日の流れ
レポジトリはこちら
github.com
12:20~
13:15~
- ベンチが使えるようになった
- 初期スコアは371
- alpによるアクセスログの解析で /api/estate/search・/api/chair/searchのエンドポイントが支配的だということが分かったので、改修に取りかかる @masakingp
- 検索条件を組み立ててLIKE検索をしてるところが遅そうだから、正規化するなりして上手いこと回避したいですね、という話をしていた
- botからのアクセスを弾く実装もまあ必要でしょうということで、echoのMiddlewareで弾く処理を実装する @sugaret
- 実装したものの、botからのアクセスが少ないし、スコアがあまり上がらないなあという話をしていた
- のちに実装ミスがあることに気付く
- この頃のスコアは450前後
15:00~
- slow queryが吐かれない原因を突き止め改修する @tatsumack
- pt-query-digestで解析したところ、検索条件を組み立ててLIKE検索するクエリは全然なかったので撤退 @masakingp
- やっぱり計測は大事
- dstat, topコマンドを叩いて、CPUが100%に張り付いていてmysqlが支配的だったので、slow queryを潰していくところから着手することに
- indexを貼るだけで解消できそうなクエリがいくつかあったので、indexを貼って回る @sugaret
- 物件がpolygonに含まれるか判定するクエリはアプリ側で計算できそうだよねという話になり、実装に取りかかる @masakingp
- Prepareもそこそこ支配的だったので、interpolateParams=trueを入れて、アプリ側でプレースホルダ置換するように変更 @tatsumack
- order by popularity desc, id asc は昇順・降順が混在していてindexが効かない。実は id asc いらないんじゃね?っていう話になり、@sugaret が id asc を外した修正を入れてみるとなんとベンチが通る
- スコアが900まで伸びる
- 予選突破圏内に入ってテンションが上がって、スクリーンショットを撮ったりしていた
17:00~
- 椅子が物件のドアを通過できるかを判定するクエリが全然index効いてないので改修に取り掛かる @tatsumack
- (door_width >= ? AND door_height >= ?) OR (door_width >= ? AND door_height >= ?) OR ... となっていた条件を1つの (door_width >= ? AND door_height >= ?) で取得できるようにする
- 実装はすぐにできたがベンチでFAILして頭を抱える
- ベンチがFAILしたときに、エラーメッセージが何も表示されないという事象がしばしば発生する。 @sugaret が運営に問い合わせるとエラー内容を教えてくれた
- 以降も何回か表示されないことがあったので、問い合わせをした
- select count(*)系のクエリは、件数をカウントする別テーブルを作れば良さそうだよねという話になり実装に取り掛かる @sugaret
- この改修は結局取り込まれず
- @masakingp が実装していた物件がpolygonに含まれるか判定する改修が入ってスコアが1095まで伸びる
- 予選突破圏内に入ってテンションが上ってスクショを撮ったりしていた
- そろそろ複数台に分けた方が良さそうだよねという話になり、まずはweb1台・mysql1台の構成に変更する対応に取り掛かる @tatsumack
- 椅子がドアを通過できるか判定の改修は @masakingp にお願いする
18:00~
- web1台・mysql1台の構成に変更する @tatsumack
- スコアが1321まで伸びる
- ベンチが不安定になってきていて、もしかすると id asc を外したのが原因かもということになり、id ascを外した対応をrevertする @sugaret
- 椅子がドアを通過できるか判定の改修が終わる @masakingp
- ベンチでFAILしていたのは件数を絞り込む処理が抜けてしまっていたのが原因だった
- botを弾く対応が不十分だったことに気付いて、修正を入れる @sugaret
- スコアが1622まで上がるが、ベンチのステータスがCANCELLEDで終わってしまう
- その後何回かベンチを回すが、スコアは1200~1350で止まってしまう
20:00~
- mysql2台構成にしたものの、/initializeでベンチがFAILしてしまう
- 「この修正が間に合わなかったら確実に戦犯だな…」と思いながら、なんとか終了10分前に改修が完了する @tatsumack
- スコアが2608まで上がる!歓喜!
- ここからベンチガチャをして上振れを狙うか、ここで止めておくか議論になる
- ボーターは2000くらいだと予想して、ベンチを回さないという判断をする
- 結果的にはこれが正解だった。僕はベンチを回す方に傾いていたが、2人が冷静だった。感謝!
21:00~
- 競技終了
- 最終スコア的には通過していそうだけど、再起動試験を全くしていなかったのでとても不安
24:00
- 帰りの電車の中で予選通過したことを知る
感想
- めちゃめちゃ楽しかった
- 中盤からボーダー近辺をウロウロしていたので、もしかすると予選突破できるかもしれないという緊張感の中で競技を楽しめた
- 残り1時間は暗雲が立ち込めてたけど、終了直前にスコアが爆増して本当に気持ちよかった
- 心臓にはとても悪かったし、とても疲れた
- 良い問題だった
- 「何をしたらスコアが上がるか全く分からない」みたいなストレスフルな状況になることがなかった
- 愚直に計測して愚直に課題解決をしていくとスコアが上がっていったように思う
- タイムマネジメントは大事
- 今回はギリギリ間に合ったから良いものの、再現性のある勝ち方ではないと思う
- 競技終了の時間から逆算して、複数台構成への移行/再起動試験/ベンチガチャなどをいつから始めるかは整理しておきたい
ISUCON運営の皆様、ありがとうございました。
本戦もよろしくお願いします!
シュッとGoにコントリビュートした話
この記事は Go7 Advent Calendar 2019 の 19日目の記事です。
今年の7月に1ヶ月ほど有給休暇を取得し、時間があるのでせっかくだから何か大きめのOSSにコントリビュートしたいなと思い、Goにコントリビュートすることにしたときの体験談です。
それまでGoでがっつり開発した経験はなかったのですが、無事にGoにコントリビュートすることができました。
issueを見つける
コードを読み込んでバグを発見したり、新たな言語仕様を提案して取り込んでもらうのはハードルが高いので、 Goのレポジトリのissuesから自分でも直せそうなバグを見つけてみることにしました。
Issues · golang/go · GitHub
このとき、 help wantedとNeedsFixというタグのついたissueから探すようにすると、解決方針が比較的自明なissueを見つけることができます。
僕は↓のissueに取り組むことにしました。
github.com
バグを直す
Goのレポジトリをcloneするなりにして、手元でコードを読みつつ、バグを直します。
このとき、issueのタイトルに x/... と記載されている場合、Go本体のレポジトリではなく、サブレポジトリにコードが置かれています。
僕が扱っていたissueは x/website と記載されていて、 https://github.com/golang/website にコードが置かれていました。
手元で環境を構築し、バグを再現することができたら、あとは直します。
今回のバグfixの差分は これ だけでした。
差分が小さいのでめっちゃ簡単な修正だったかというとそうでもなくて、この差分で問題ないか確認するために周辺のコードをそこそこ読み込む必要があるので、時間はそれなりにかかった記憶があります。
パッチを送る
手元でバグの修正が確認できたら、パッチを送って、レビューをしてもらいます。
アカウントの登録やレビューツールが必要になるので、 Contribution Guide - The Go Programming Language を読みつつ、用意します。
今回はサブレポジトリへのコントリビュートでしたが、cloneするレポジトリが異なる以外は、通常のフローと同じで問題ありませんでした。
パッチを送るには、GithubもしくはGerritを使う必要があります。今回はせっかくなので普段使わないGerritを使ってパッチを送ってみましたが、特に詰まることなくスムーズにレビューに出すことができました。
https://go-review.googlesource.com/c/website/+/187897
パッチを送ると、 botから「Congratulations on opening your first change. Thank you for your contribution!」というコメントがついて、ちょっといい気分になります。
Goのプロジェクトはsix-month development cycleを採用しており、7月はDevelopment Freezeの期間だったのでマージされるのはもう少し先になるかと思いきや、レビューに出した翌日にはレビュワーにOKを貰い、パッチを取り込んでもらいました。
後日談
Goのレポジトリには CONTRIBUTORS というファイルがあり、コントリビュートした方の名前が掲載されています。
今回直したバグはサブレポジトリの小さいバグだったので名前が載ることはないかなと思っていましたが、2ヶ月後くらいの更新のタイミングでCONTRIBUTORSに自分のアカウントが掲載されました。
Goのコントリビュータになった! pic.twitter.com/E2PB4p3d5A
— tatsumack (@tatsumack) September 4, 2019
プログラミング言語へのコントリビュートはものすごく高いハードルがあると思っていましたが、思っていたよりも簡単にコントリビュートできました。
この体験談がGoにコントリビュートしてみたいけれど手が出ないと思っている方の参考になれば幸いです。
CLionの競技プログラミング用プラグイン「JHelper」の紹介
最近、競技プログラミング界隈でCLionユーザーが増えてきている気配を感じたので、CLionのJHelperという競技プログラミングに特化したプラグインを紹介しようと思います。
plugins.jetbrains.com
JHelperは、
・サンプルケースの取得
・取得したケースに対するテストの実行
といった競技プログラミングをする際の典型作業をCLion上でいい感じに自動化してくれます。
使用例
1. 問題ページを開いて拡張機能のボタンをポチっと押す
2. CLion上で問題のConfigurationの作成&cppファイルの作成が自動で行われる
3. Runするとサンプルケースのテストを実行することができる(もちろんデバック実行もできる)
上記の使用例はAtCoderですが、Codeforcesなど主要なコンテストはだいたい対応しています。
対応コンテスト一覧
その他の機能
Configurationの自動切り替え
CLion上で開くファイルを切り替えるとConfigurationも自動で切り替わります。
複数の問題を解いているときに、Configurationを切り替え忘れていて別のファイルを実行してしまった、というありがちなミスを回避することができます。
コンテストごと丸っとダウンロード
コンテストページ上で拡張機能ボタンを押すと、そのコンテストに含まれる問題すべてをパースしてくれます。
自作テストの追加
もちろん自身が定義したテストケースを追加できます。
自作ライブラリの埋め込み
わざわざコピペしなくても、自作ライブラリをソースコードに埋め込んでくれます。
(私自身あんまり使っていない機能なので使い勝手はよく分からない)
他にもいろいろな機能があるので、興味がある方は JHelperのWiki を見てみてください。
インストール方法
1. JHelperプラグインをインストール
JHelper - Plugins | JetBrains
2. ブラウザの拡張機能をインストール
Chrome
Firefox
3. ToolBarにJHelperのアクションを追加
Preferences > Appearance & Behavior > Menus and Toolbars > Main Toolbar
を開いた状態で +ボタンを押して、
Add Action > Plug-ins > JHelper
で表示されたアクションをすべて追加します。
↓のようにツールバーにJHelperのアクションが追加されます。
4. サンプルプロジェクトのダウンロード
GitHub - AlexeyDmitriev/jhelper-example-project: Example project for JHelper
git cloneするなりして、上記のサンプルプロジェクトをダウンロードしてください。
簡単にディレクトリ構成を説明すると、
library/ ... 自作ライブラリを置くディレクトリ
tasks/ ... 問題ごとのcppファイルが追加されるディレクトリ
testrunnner/ ... テスト実行用のファイルが生成されるディレクトリ
output/ ... 提出用のファイルが生成されるディレクトリ
となっています。
tasks/配下の問題ファイルにコードを書き、Runすることで testrunner/配下にテスト実行用ファイル、output/配下に提出用ファイルが生成される、という仕組みになっています。
ディレクトリ構成はJHelperの設定から変更することも可能です。
5. お好みでテンプレートを修正
task.template ... 問題ごとのcppファイルのテンプレートです。私はよく使うマクロを定義しています。
jhelper-projects/task.template at master · tatsumack/jhelper-projects · GitHub
testrunner.template ... テスト実行ファイルのテンプレートです。私は出力結果に色をつけたりしています。
jhelper-projects/run.template at master · tatsumack/jhelper-projects · GitHub
submisiion.template ... 提出用ファイルのテンプレートです。私は特にいじってません。
6. 実際に使ってみる
上記で作ったプロジェクトをCLionで開いて、AtCoderやCodeforcesの問題ページを開いた状態でブラウザの拡張機能のボタンを押してみてください。
CLion上にConfigurationが生成されて、問題のファイルが生成されます。
ファイルには↓のようにclassとsolveメソッドが定義されています。
solveメソッドにコードを書いていきます。
入出力はsolveメソッドの引数で渡されたものを使う必要があるので注意してください。
実装ができたら、 ボタンを押してテストケースを実行します。
問題なければ、output/配下に生成されたmain.cppファイルを提出します。
ここまで問題なくできれば、設定完了です。
あとは簡単にツールバーの各アクションの説明をすると、
… Configurationの削除を行う
… テストケースの編集を行う
… Configurationの追加を行う(ブラウザの拡張機能から追加できるのであんまり使わない)
... JHelperの設定を変更する。生成ファイルの出力先を変更できたり。
… 提出用のファイルをクリップボードにコピーする。
… コンテストごと丸っとパースする(AtCoderは未対応。ブラウザの拡張機能から実行できるのであんまり使わない)
といった感じになっています。
まとめ
JHelperはいいぞ。
ちなみにCLion自体は有料の製品です。(学生は無料)
サムライズムというJetBrainsの公式代理店で購入する場合、↓の紹介リンク経由で購入すると少し安く買えるので良かったらぜひ。
JetBrains製品 紹介リンク
2018年に読んだ技術書たち
年の瀬ということで、日々の往復2時間の通勤時間を活かして読んできた技術書たちを備忘録としてまとめておく。
プログラミングコンテストチャレンジブック
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る
購入したのは2014年くらいだったと思うけど、途中で挫折して積んでいた本。
今年競技プログラミングを始めたこともあり、また気合入れ直して読んでみた。
読むには読んだけど、理解できていないところも結構ある。
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
- 作者: 碓井利宣,竹迫良範,廣田一貴,保要隆明,前田優人,美濃圭佑,三村聡志,八木橋優,SECCON実行委員会
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/09/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (4件) を見る
CTF出てみたいなーと思って買った本。CTFビギナーが雰囲気を掴む上でとても参考になった。
ということで、今年は夏にあった初心者向けのCTFにも参加してみた。
picoCTF、1万点超えた pic.twitter.com/SWsZ5t6oie
— tatsumack (@tatsumack) October 7, 2018
http://blog.hatena.ne.jp/tatsumack/tatsumack.hatenablog.com/edit#preview
プログラミングC# 第6版
- 作者: Ian Griffiths,Matthew Adams,Jesse Liberty,鈴木幸敏,首藤一幸,株式会社情報技研
- 出版社/メーカー: オライリージャパン
- 発売日: 2011/11/29
- メディア: 大型本
- 購入: 2人 クリック: 14回
- この商品を含むブログ (11件) を見る
C#を書くことになったので、とりあえず体系立てて学びたいと思って買った本。
リファレンスとしてたまに読み返したりしている。
Unityゲーム プログラミング・バイブル
- 作者: 吉谷幹人,布留川英一,一條貴彰,西森丈俊,藤岡裕吾,室星亮太,車谷勇人,湊新平,土屋つかさ,黒河優介,中村優一,牙竜,コポコポ,かせ,hataken,monmoko,佐藤英一
- 出版社/メーカー: ボーンデジタル
- 発売日: 2018/05/01
- メディア: 大型本
- この商品を含むブログを見る
Unityの実践的な知見がまとまってる書籍ってあまりないので、発売前から気になっていた本。たしかUniteかCEDECの物販で買ったと思う。
各章独立しているので、気になるところをつまみ食いする感じで読んだ。
ふつうのLinuxプログラミング
ふつうのLinuxプログラミング 第2版 Linuxの仕組みから学べるgccプログラミングの王道
- 作者: 青木峰郎
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2017/09/22
- メディア: 単行本
- この商品を含むブログを見る
最後の章のhttpサーバーを作るところが面白かった。
これを参考にしつつ、自分でも簡単なhttpサーバーを書いてみた。
github.com
[試して理解] Linuxのしくみ
[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識
- 作者: 武内覚
- 出版社/メーカー: 技術評論社
- 発売日: 2018/02/23
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
Twitterで話題になっていたので読んでみた。
説明が丁寧なのと図も分かりやすく、エンジニア初心者の方にも読みやすいと思う。
社会人1年目くらいにこの本が欲しかった。
詳解UNIXプログラミング
- 作者: W. Richard Stevens,Stephen A. Rago
- 出版社/メーカー: 翔泳社
- 発売日: 2014/06/05
- メディア: Kindle版
- この商品を含むブログ (7件) を見る
[試して理解] Linuxのしくみを読んだあとに、Unixに関して体系立った深い知識を得たいなと思って読んだ本。
900ページ超あり、読み終わるのに3ヶ月くらいかかった気がする。
プログラミング言語Go
プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
- 作者: Alan A.A. Donovan,Brian W. Kernighan,柴田芳樹
- 出版社/メーカー: 丸善出版
- 発売日: 2016/06/20
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (2件) を見る
Goを書くことになったので買った。
練習問題を全部解くかーと思ったけど、結構問題数が多くて途中で飽きてしまった。
github.com
とりあえず全体をサラーッと読んで、Goを書いていて気になることがあれば読み返したりしている。
みんなのGo言語
- 作者: 松木雅幸,mattn,藤原俊一郎,中島大一,牧大輔,鈴木健太,稲葉貴洋
- 出版社/メーカー: 技術評論社
- 発売日: 2016/09/09
- メディア: 大型本
- この商品を含むブログ (4件) を見る
Goを書く上での実践的な知見を知りたくて買った。
Goプロジェクトのディレクトリ構成とか、マルチプラットフォームのツールを作る上で気にすべきこと、テストの書き方あたりが参考になった。
やってみようGoでISUCONパフォーマンスチューニングーISUCON7の予想問題を試してみる本ー
技術書典5に行けなかったのが悔しくて、後日電子版を買い漁ったときの本。
ConoHaでisucon環境がサクッと生成できること、pprof, alpあたりの使い方を知れたのが良かった。
今年は社内ISUCONに参加して非常に楽しかったので、来年はぜひ本家のISUCONにも参加してみたい。
Ryzen SEGV Battle
https://www.dlmarket.jp/products/detail/619213
これも技術書典5の電子書籍を買い漁っていたときの本。
このレイヤのバグを検証するのはめちゃめちゃ大変そうで読み応えがあり、かなり面白かった。
DNSをはじめよう ~基礎からトラブルシューティングまで~
この本も電子版を買い漁っていたときに見つけた本。
そういえばDNSってちゃんと知らなかったし、説明が分かりやすかったのでとても良かった。
コンパイラ: 作りながら学ぶ
- 作者: 中田育男
- 出版社/メーカー: オーム社
- 発売日: 2017/10/25
- メディア: 単行本
- この商品を含むブログ (3件) を見る
Turing Complete FM を聞いたりしていて、僕もCコンパイラ書いてみたいなと思って、買ってみた本。
思ったよりもとっつきやすくて、初学者でも読みやすかった。
で、これを読んでCコンパイラを書こうと思ったけど、競技プログラミングにハマったこともあり、四則演算を書いたくらいで頓挫している。。
低レイヤを知りたい人のための Cコンパイラ作成入門
Turing Complete FMのRui Ueyamaさんが書かれているCコンパイラ作成入門本。
まだ執筆途中だけど、読みやすくて僕でもセルフホストCコンパイラがかけそうなので、完成版が本当に待ち遠しい。
Go言語でつくるインタプリタ
- 作者: Thorsten Ball,設樂洋爾
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/06/16
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
Goの勉強しつつ、インタプリタもかけるなんて最高じゃんと思って買った本。
Goに関しての言及はあまりなかったけど、簡単なものであればインタプリタって意外と作れるもんだなと思えた。
github.com
自分で構文を追加してみたりもした。
qiita.com
同じ作者によるコンパイラ本も買ったので、早く読みたい。
Writing A Compiler In Go (English Edition)
- 作者: Thorsten Ball
- 発売日: 2018/07/29
- メディア: Kindle版
- この商品を含むブログを見る
マスタリングTCP/IP 入門編
- 作者: 竹下隆史,村山公保,荒井透,苅田幸雄
- 出版社/メーカー: オーム社
- 発売日: 2012/02/25
- メディア: 単行本(ソフトカバー)
- 購入: 4人 クリック: 34回
- この商品を含むブログ (37件) を見る
そういえば、体系立ててネットワーク周りの勉強をしたことがないなと思って買った本。
淡々とプロトコルの仕様を説明するのではなく、どういう経緯で今の仕様になっているのかをきちんと説明している点が良かった。
実践パケット解析
実践 パケット解析 第3版 ―Wiresharkを使ったトラブルシューティング
- 作者: Chris Sanders,高橋基信,宮本久仁男,岡真由美
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/06/16
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
Wiresharkを使いながら、パケット解析を実践してみる本。
深い知識を得られるかと思いきや、結構浅い感じだった。ネットワーク入門本としてはアリだと思う。
エンジニアのためのマネジメントキャリアパス
エンジニアのためのマネジメントキャリアパス ―テックリードからCTOまでマネジメントスキル向上ガイド
- 作者: Camille Fournier,及川卓也(まえがき),武舎広幸,武舎るみ
- 出版社/メーカー: オライリージャパン
- 発売日: 2018/09/26
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
今はマネジメントから離れているが、またマネジメントとしてのキャリアを考えることもあると思い買ってみた本。
まだ自分にはピンと来ない部分もあったので、マネジメントに軸足を置く機会があれば、また読み直したい。
エンジニアリング組織論への招待
エンジニアリング組織論への招待 ~不確実性に向き合う思考と組織のリファクタリング
- 作者: 広木大地
- 出版社/メーカー: 技術評論社
- 発売日: 2018/02/22
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (2件) を見る
個人的には2018年に読んだ本の中で一番良かった。
特にこの一年は新規開発をしていたこともあり、不確実性を減らす動き方ができているか自問自答していた。
一見エンジニア向けっぽい本に見えるが、企画職やプロダクトマネージャーにもオススメ。
ドラゴンクエストXを支える技術
ドラゴンクエストXを支える技術 ── 大規模オンラインRPGの舞台裏 (WEB+DB PRESSプラスシリーズ)
- 作者: 青山公士
- 出版社/メーカー: 技術評論社
- 発売日: 2018/11/14
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
長期運営かつ複数プラットフォームを対応する上で、意外と泥臭い問題解決をしている点があるところも包み隠さず書かれていた点が良かった。
コラムも面白くて「TCPのチェックサムは合っているけど、データが壊れていることがあった」とかそんなことあるのかーという感じ。
まとめ
来年も気の赴くままに技術書を読み漁っていきたい。
AtCoderの拡張機能を3つ作った話
これは AtCoder関連サービス Advent Calendar 2018 - Adventar の9日目の記事です。
今年の3月くらいから競技プログラミングにハマり初め、精進していく過程で、AtCoderの拡張機能が3つ生まれたので紹介します。
AtCoder-ACer
これは、AtCoderの問題一覧ページにコンテスト中にACした人数を表示する拡張機能です。
AtCoder-ACer【Chrome拡張】
なぜ作ったの?
たまに配点の高い問題の方が多く解かれていることがあり、Codeforcesのように問題一覧ページに現在ACしている人数が表示されていると、コンテスト中の立ち回りを判断する上で役立つだろうなーと思って作りました。
作った後に、順位表の最下部に同じような情報が出ていたことに気付いたのですが、どうせ作ったのだからということで、公開しました。
ありがたいことに、40人くらいの方に使っていただけているので、公開して良かったですね。
AtCoder-Video
これは、AtCoderのコンテストページに解説放送へのリンクを追加する拡張機能です。
AtCoder-Video【Chrome拡張】
AtCoder-Video【UserScript】
なぜ作ったの?
YouTubeで解説放送を探すのが面倒だったので作りました。
どうやって作ったの?
YouTube APIを使って、AtCoderチャンネルの動画の一覧を取得しています。YouTube APIを使うために必要なAPI keyはクライアントに置くことはできないので、サーバーを用意する必要がありました。
が、真面目にサーバー管理するのが面倒だったので、今回はGoogle Apps Scriptを使用しました。サーバーレスな感じで開発することができ、今回のような用途では非常に便利でした。
Cronのように定時実行することもできるので、10分毎にYouTube APIを叩き、取得した動画情報をスプレッドシートに保存しています。
あとは、このシートからデータを取得しjsonとしてレスポンスを返すAPIを用意して、拡張スクリプト側からはそのAPIを叩いています。
Google Apps Scriptは無制限に呼び出せるわけではないので、クライアント側では一度取得した結果をlocalStorageに一定期間保存するような実装にして、APIを呼ぶ回数を抑えるようにしています。
ちなみに、YouTubeの放送タイトル名にtypoがあったりすると、うまく動きません。
今回の解説放送のタイトルが前回のままになってて、昨日公開した拡張動かないぞーって焦った
— tatsumack (@tatsumack) 2018年8月5日
あと、現状、企業コンには未対応です。
今後、企業コンが増えてきそうな流れなので、ぼちぼち企業コンにも対応しないとなーという気持ちはあります。
[2019/05/17追記]
AtCoder本家のサイトに解説放送へのリンクが追加されるようになったので、AtCoder-Videoは削除しました。
AtCoder-TestCase-Extention
これは、AtCoderのテストケースへのリンクを追加する拡張機能です。
個人的には一番気に入っている拡張機能で、今回作った3つの拡張機能の中でも一番利用者が多いです。(160人くらい)
AtCoder-TestCase-Extention【Chrome拡張】
AtCoder-TestCase-Extention【UserScript】
なぜ作ったの?
AtCoderはテストケースを一部Dropboxに公開しているのですが、Dropbox上で探すのが面倒だったので作りました。
また、ABCとARCが同時開催された回は、ABCのテストケースがARCのディレクトリ配下にまとめて格納されているので、ABCがどのARCに対応するのか調べる必要がある、という点も面倒でした。
どうやって作ったの?
開発当初はサクッと作れると思っていたのですが、なかなか骨が折れました。。
各テストケースへのURLを取得する必要があり、DropboxのAPIからサクッと取得できると楽だったのですが、ドキュメントを調べた限りそれは難しいようでした。
そのため、Dropboxのページをスクレイピングする必要がありましたが、DropboxのページはJavaScriptで動的に生成されているページだったので、単純にレスポンスをパースするだけではうまくいきません。
そこで、PhantomJs Cloudを利用しました。スクレイピングしたいURLをパラメータとしてPhantomJs CloudのAPIを叩くと、JavaScriptで動的に生成した後の結果を返してくれます。
公開されている全てのコンテストの情報をスクレイピングしようと思うと、無料枠だと3ヶ月ほどかかる計算だったのには頭を抱えましたが、諦めて課金しました。
また、AtCoderのテストケース名から公開されているファイル名を判定する必要があるのですが、コンテスト毎に規則が異なっていたことにも困りました。
当初、テストケース名にファイル拡張子がついていない場合は、.in / .out 拡張子で保存されていると決め打って実装していたのですが、いくつか例外があったことが後ほど発覚しました。
めっちゃニッチな要望ですが、AtCoder社におかれましては、今後公開するテストケースのファイル拡張子を.txtに統一していただけると大変ありがたいです。。
— tatsumack (@tatsumack) 2018年10月7日
(dropboxのプレビュー表示が有効になるのと、拡張機能のスクレイピングがちょっと楽になる) https://t.co/q8uicj4UkB
あと、この拡張機能もサーバーサイドはGoogle Apps Scriptを使用しています。
サーバーを用意せずにやりたいことに集中できるのは楽ですね。
こちらも現時点では企業コンは未対応です。
まとめ
今年作ったAtCoder便利拡張機能を紹介させていただきました。
ちなみに、今回作った拡張機能のソースコードは公開しています(Google Apps Scriptのコードも)
GitHub - tatsumack/atcoder-acer: AtCoder問題一覧ページに正解者数を表示するChrome拡張機能
GitHub - tatsumack/atcoder-video: AtCoderのコンテストページに解説放送へのリンクを追加する拡張スクリプト
GitHub - tatsumack/atcoder-testcase-extension: Extension for test cases of AtCoder.
何か不具合や質問があれば @tatsumack にお気軽にお伝えください!
AtCoder Beginner Contest 102 振り返り
3回連続で400点問題を落として水色チャレンジに失敗していたので、今回は久々の4完でホッとした。
初めて600点問題でACできたので、解説記事でも書こうかと思ったけど、他の方の非常に分かりやすい記事があったのと、他の人の思考過程を知りたいと思うことがよくあるので、今回は自分が解答に至るまでの思考過程を記してみようと思う。
今回のABCの配点は100-200-300-600で、明らかにC速解き勝負だったので、なるべく早く解くことを意識した。
A - Multiple of 2 and N
パッと問題文を読んだときは2*Nを出力すれば良さそうだと思ったけど、サンプルを見て、Nが2で割り切れるときはNを出力すれば良いことに気づく。
Submission #2765392 - AtCoder Beginner Contest 102
B - Maximum Difference
問題文を読んだ時点で、配列要素の最大値と最小値の差を引く、という方針が浮かんだので、そのまま実装する。
Submission #2765973 - AtCoder Beginner Contest 102
C - Linear Approximation
問題文を読んだ時点では、方針が全く浮かんでこなかったので、「C速解き失敗」が脳裏をよぎる。
落ち着いて、問題を簡単に考えることはできないかと、式を眺める。
は、とすると として考えることができることに気付く。
よって、配列内の各要素からの距離の総和が最小となるようなを考えれば良くなり、少し単純になる。
まあそれでもまだ分からない。
簡単に考えるために、要素数が2のケースで考えてみる。すると、は2要素の間にあれば良いことに気付く。
次に、要素数が3のときを考えてみる。このとき、真ん中の要素とが一致すれば良いことが分かる。
ということで、は配列の要素の中央値を選べば良さそう、という気配が濃厚になったので、実装してみる。
サンプルがすべて通ったので、ちょっと不安はありつつも、提出してみる。
ジャッジサーバーが詰まっていたのか、なかなかジャッジが走らなくてそわそわしたが、無事ACが出たので、一安心。
Submission #2767475 - AtCoder Beginner Contest 102
目標がC速解きだったのと、Dの600点問題は解けるわけないと思っていたので、ちょっと集中力を切らしてtwitterを眺めたりする。
D - Equal Cut
この時点で順位表を見ると、1位だったのでびっくりした。(スクショ取っておけば良かった)
Dも頑張って解いてみるかと思い直し、問題文を読み始める。
部分和を求める必要があるので累積和を使いそうだなーとは思ったが、方針は全く浮かんでこない。
簡単に考えるために、切り口を1つだとして考えてみる。
このときは、配列内のすべての切り口の位置を調べれば、で簡単に切り口の位置を求めることができる。
ということで、「切り口1つの位置を考えれば良い」という状況にどうにかして落とし込めれば、この問題は解けそうだと思い始める。
ここで、切り口3つのうち真ん中の切り口を固定すると、左右の切り口の位置は切り口1つの問題に落とし込めることに気付く。「3つあるうち真ん中を固定すると、残りが決まる」というのはよくある形だったこともあり、気付くことができた。
無事にサンプルが通ったので提出するも、TLE。
Submission #2771181 - AtCoder Beginner Contest 102
計算量を落とせる場所がないか考えてみる。
真ん中の切り口の位置を更新するたびに、左右の切り口の位置を全探索して調べるのは無駄なことに気付く。
よくよく考えると、左右の切り口の位置は右にずれていくだけなので、真ん中の切り口を移動する際に、前回の左右の切り口の位置を覚えておいて、そこから計算すれば良さそう。(尺取法的なアプローチ)
Submission #2771925 - AtCoder Beginner Contest 102
サンプルが通ることを確認して、提出して、祈る。。
AC!初めて600点問題を通すことができた。
Dの提出直後は3位だったが、1WAだったこともあり、最終的な順位は4位だった。
ABC102、4位でしたー🎉 pic.twitter.com/ln5DW6Cfdh
— tatsumack (@tatsumack) July 1, 2018
振り返り
C問題もD問題も、パッと見よく分からないので、問題を簡単にして考えてみる、というアプローチが上手くいった。直近のコンテストで400点問題が解けないときは難しく考えすぎていたので、その反省が活かせたと思う。
1120 → 1186 (+66) perf 1600
— tatsumack (@tatsumack) July 1, 2018
分かっていたけど、水色には届かず。安定してこのパフォが出せるように頑張ろう
次こそ水色!
はりぼてOSをNASM・GCCで動かす(Mac OSX)
「30日でできる!OS自作入門」を読んだ。
- 作者: 川合秀実
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2006/03/01
- メディア: 単行本
- 購入: 36人 クリック: 735回
- この商品を含むブログ (301件) を見る
この本で開発する「HariboteOS」は作者の独自ツールを使って動かしているが、GNUのツール群で置き換えてビルドできるようにしてみた。
環境
Mac OSX El Capitan(10.11.2)
NASM(Netwide Assembler)に置き換える
作者独自ツールのNASKをNASMに置き換える。
主要なアセンブラとして、NASMの他にGAS(GNU Assembler)が挙げられるが、GASの構文はNASKと大きく異なるので、NASMで置き換えることにした。
参考: Linux のアセンブラー: GAS と NASM を比較する
下記のページに記載のある通り、置き換えをすればアセンブラできるようになる。
http://hrb.osask.jp/wiki/?tools/nask
対応コミット
Replace nask with nasm · tatsumack/HikariOS@877ec9d · GitHub
GCC
C言語で実装されたファイルも作者の独自ツールを使ってコンパイルされていたので、GCCに置き換えてみた。
GCCのビルド
hrb形式のファイルを作成するためには、リンカスクリプトを作成しリンカに渡す必要があるが、
Mac OSXのデフォルトのリンカ(ld)はリンカスクリプトを受け付けるオプションがないので、クロスコンパイラなGCCをビルドする必要がある。
ビルド手順についてはQiitaにまとめた。
qiita.com
その他にやったことの箇条書き
・nasmの出力形式をwin32からelfに変更
・.hrb形式のリンカスクリプト作成
・naskfunc.nasの関数のシンボル名のprefixの_を削除
・色々とライブラリがないので、自作OS本付属のomake/tolsrc/go_0023s/golibcから静的ライブラリを作成し、リンクする
・__builtin_stdarg_startを__builtin_va_startにrename
対応コミット
Replace gocc with gcc · tatsumack/HikariOS@ab4b5d4 · GitHub