Competitive Programming (その2) Advent Calendar 2016 6日目
Competitive Programming (その2) Advent Calendar 2016 - Adventar
Competitive Programming (その2) Advent Calendar 2016 6日目の記事です。
万年灰色コーダーの nise_nabe です。
今回は思い出ポエムを書きます。ちょっとアルゴリズム以外の競プロ役立ち事例のような何かも入っています。(万年灰色コーダの書く記事なので、レッドコーダーや div1 などの上位陣向けではないということはわかっていただけるかと思います。)
おまえはなんなのか
競技プログラミング歴 2009年 〜 らしいです。 最初に出たコンテストは Topcoder SRM 450 のようです。
Codeforces min 751 max 1657
min がひどいですね。実際当時は堪えていましたが結局作り直したところでそういう実力なら同じ結果になるだろうと同じアカウントで続けています。某レッドコーダーの方には自分の SRM のグラフをみて「数だけはやってるね」という評価を頂いております(又聞き)。
まあ見たとおりまったく良い成績でないです。高い所がまあ時間が合った時期です。時間があるので問題を解けます。掛ける時間が多くなるとレートが上がります。時間がなくなると問題が解けません。掛ける時間が少なくなるとレートが下がります。
ICPC には出たことがありません。というより競技プログラミングを初めた時点ではそういったイベントに参加するにはいろいろと遅すぎたようです。 tomerun さんとはじめて会ったときには社会人になってから初めたことについて伺い、興味深く聞いた覚えがあります。
初めた当時の微笑ましい姿
Div1/2どっちもトップはJavaなんだな.よし,がんばるぞ!
— nise_nabe (@nise_nabe) 2010年1月4日
自分の競技プログラミングは基本的に一人でした。複数人で競技プログラミングをやるという話はよくみますが自分にとってはよくわからない世界という感じがします。周りの人を誘ってみましたがまあ興味がなかったり長続きしなかったりという感じですね。 twitter をやっていた理由も、 当時 twitter 上にたくさん競技プログラマがいたからです。彼らのリプライを見ながら、自分もこういう話ができるようになりたいと思ったものです。
昔話、あるいは役立ち事例。
昔話です。あるいはどのようにして役に立てるかという話ではなくいい成績を持たない競技プログラマでもそれを通じて得たなにかみたいなものです。
初めた当時は貪欲に参加できるものに参加していたので下記のようなサイトに参加していました。(よくみると tanakh さんや nodchip さん、 tsukuno さんがいますね)
http://www.itmedia.co.jp/news/articles/1003/31/news004.html
まあこれ単に なんか文字列が与えられて Excel のセルの範囲内かどうかを出力するという感じの div2 easy よりちょっと下ぐらいの難易度の問題1問だけが出されたものですね。
nise_nabe は 4 位にいますが、これ単に正規表現とか使って 2, 3 行で書いただけの簡単なやつです。これ自体は本当に大したことないですが、実はこのサイトの参加を通じて、(このサイト直接経由ではないけど)インターンシップに行ったりしています。まあなんでも参加してみるもんですね。最近だといろいろな企業がちゃんとコンテストを開いているようなのでとりあえず参加したらいいと思います。思わぬ繋がりができるかもしれません。
そして就職に関しても基本的には nise_nabe という名前でやっていました。実は他にもいろいろプッシュできる内容を持っていたんですが、試しに競技プログラミング一点で突破しようとしてみました。基本的にはレートが高い低いということは話題にはならず、コードを書いているという点が評価されました。 一部「お金にならないコードを書いて意味があるのか」と言ったような意見ももらいました。当時は何を言っているのかわからなかったですが今はちょっと分かる気もしなくもないです。本当にちょっとだけ。
下記のものは非常に遠回しな言い方をしていますが、まあそういうことです。
知ってる競技でないプログラマの人の一人からは「金にならないプログラムを書きたくない」ということで興味がないらしいということを聞いたことがある気がする.
— nise_nabe (@nise_nabe) 2011年6月8日
また、実は有名な某サイトを使った転職の事例でもあります。これも実際にはランクとかそのとき書いたコードなんかはあまり参考にはされていなかったらしく、基本的には貼っていた ブログの URL に書いてあるコードを見て、コードが書ける人間と判断してくれていた感じらしいです。
まあ以上のように、実は総じて競技プログラミングを通じて仕事にありついている現実があります(実務で競技プログラミングが直接影響してるかどうかとは別の話)。 そのような経験から書くと、別に 上位陣でなくても競技プログラミングをやっていることは評価されることはされます。ただし競技プログラマだからというよりコードをかいているからという点でです。なので、書いたコードはやったらとりあえずブログに貼っとけばいいです。いつかプログラミング関係の仕事をしようとしたときに自分が書いたコードが有ることがアドバンテージになることがあります。上位のコードかどうかは関係なく、コードかいたものが見える位置にあるというのが評価対象になると思います。まあ、逆に言うと自分ぐらいのレベルの競技プログラマならばコードが書けるかどうかという点ぐらいしか評価できないのかもしれません。書ける人は先日の chokudai さんの記事 を参考にしましょう。
あとは、レートが低くてもイベントにはいろいろ参加できますね。UTPC の懇親会 とか 診断人さんの Topcoder 飲み会とか。主催者側がどう思ってるかはわからないですが、とにかく行っても大丈夫です。行きましょう。
そしてこれから
自分はここ数年はプログラミングコンテスト関連の活動は殆どできていません。これは競技プログラミングが原因ではなく心身の不調により気力がなくなったことが影響しています。今はだいぶ普通です。ただし優先順位がいろいろと変わったためやはり手をつけられてはいないです。なのでやるかもしれないしやらないかもしれません。まあ、それとは関係なく下記の事はずっと考えています。
競プロは老後の趣味
— nise_nabe (@nise_nabe) 2012年12月19日
願わくば老後の趣味として競技プログラミングの楽しみが残っていますように。
以上です。
debian ベースの ディストリ上で openvpn が起動しない場合
ubuntu や debian で openvpn をインストールしたときに service restart などが全く効かなかった時の話。
バージョン確認
$ docker run -i -t ubuntu # cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=16.04 DISTRIB_CODENAME=xenial DISTRIB_DESCRIPTION="Ubuntu 16.04.1 LTS"
$ docker run -i -t debian # cat /etc/debian_version 8.6
起動してみる
# service openvpn start [ ok ] Starting virtual private network daemon:.
起動したように見える…が、実際には起動してない。
/etc/systemd/system/multi-user.target.wants/openvpn.service を見ると下記のようになっている。
# This service is actually a systemd target, # but we are using a service since targets cannot be reloaded. [Unit] Description=OpenVPN service After=network.target [Service] Type=oneshot RemainAfterExit=yes ExecStart=/bin/true ExecReload=/bin/true WorkingDirectory=/etc/openvpn [Install] WantedBy=multi-user.target
ExecStart などが 起動につかうコマンドになるはずだが /bin/true になっている…。成功したように見えるのはこのコマンドのせいのようす。とにかく起動したいので下記のように openvpn を直接起動するように変更してみる。
ExecStart=/usr/sbin/openvpn --daemon ovpn-server --status /run/openvpn/server.status 10 --cd /etc/openvpn --config /etc/openvpn/server.conf
$ sudo systemctl daemon-reload $ sudo systemctl start openvpn
一応これで起動するようになった…はず。フラグは不明だが systemd のファイルがいつのまにか巻き戻っていたり、 /usr/sbin/openvpn が起動しなくなったりするのでよくわからない。
Docker for Mac 起動中には Android Emulator (HAXM) が動かない
下記のようなエラーが出た場合で virtualbox そのものを使っている覚えがない場合で Docker for Mac を使っている場合は Android Emulatror の HAXM ありの場合に起動しない可能性がある。
Hax is enabled Hax ram_size 0x40000000 HAX is working and emulator runs in fast virt mode. emulator: Listening for console connections on port: 5554 emulator: Serial number of this emulator (for ADB): emulator-5554 Failed to sync vcpu reg Failed to sync vcpu reg Failed to sync vcpu reg emulator: ERROR: Unfortunately, there's an incompatibility between HAXM hypervisor and VirtualBox 4.3.30+ which doesn't allow multiple hypervisors to co-exist. It is being actively worked on; you can find out more about the issue at http://b.android.com/197915 (Android) and https://www.virtualbox.org/ticket/14294 (VirtualBox) Internal error: initial hax sync failed
https://forums.docker.com/t/cant-using-docker-for-mac-with-android-emulator-haxm/8939
対処方法は Docker for Mac を停止させるぐらいしか思いつかない。
ISUCON6 予選参加記
ISUCON6 予選 9/17 土曜日に「応答5マイクロセカンド」で take4、Takky と参加していました。
参加当日からずっと風邪引いてたりしてたのでまともな振り返りはしてないですが記録として書いときます。 (箇条書きで同列っぽく書いてますが事実と主観が混在してます)
準備編
やったこと
- 過去問練習会
- Azure 環境の確認
- newrelic のアカウント準備および使い方の確認
準備での雑感
- azure の初期セットアップおよびリカバリで時間がかかる場合があるのでリストアはしっかりできるようにする
- newrelic は CPU やメモリは確認できたが MySQL のクエリおよびアプリケーションについては使い方が確認できなかったので当日は使わないことにした
- 3人のスキルセットから php を使うことを検討したが php.ini のチューニングに時間がかかりすぎる場合があるので Go に変更
- ここで Go を書ける人が1人しかいないのでアプリ担当が1人になる
当日編
午前
- 準備を完了する
- アプリデプロイ
- メトリクス収集用設定
- アプリに一通り触れて使用感を確認する
- アプリやSQLを眺める
- 方針の決定
わかったこと
- isuda, isutar, isupam の3つのサービスがある
- isuda がメインサービスで isutar は http で通信 isupam は外部プロセス呼び出しで連携する
- newrelic の結果より
isuda > mysql >> その他
で CPU を消費している - MySQL の slow query は出ていない
- MySQL の general log から一部 SELECT の間隔が遅い
- 初期状態は fail で 0 points
以上より
- ボトルネックはアプリケーションとして作業する
- 最も遅い所は / や /keyword で基本的に
htmlify()
があるのでこれを何とかする - その他こまごまとしたものは最後にまとめて対応か暇になったら都度対応
午後
- keyword の完全オンメモリ化
- initialize 時にロードする実装
- 追加およびソートの実装
- (削除処理は実はすっかり忘れてた)
- htmlify のキャッシュ化
- matcher のキャッシュ
- アンカータグのキャッシュ
- キーワード毎の htmlify のキャッシュ
- キーワード追加時の htmlify キャッシュのパージ
- SQL の不要なデータの取得をなくす
上記対応後でもずっと 0 点だったためどれがどの程度効果があったかは不明です。
雑感
- メトリクス収集してアタリをつけられるようにするのはやはり必要と思った
- チーム構成にもよるかもだけど 午前方針ぎめ、飯食いながら相談、1時間前まで作業、30 分まえまでに落とし所に収束させる、30 分で再起動確認という流れで考えてたけど間違ってはいないかなと思う。
- 点数が正の数になって景気つけようとしてたけど Fail 0 だった
- いつの間にか 307 点ぐらいとったけど気のせいレベル
- ボトルネック部分把握した所で「競プロ勢有利な問題じゃん」と叫んでいた。
- 実際にどうかは知らない(競プロ雑魚勢の感想)
- 途中というか最初から make 叩くだけでは Go アプリのビルドが成功しなかった
- 今回は複数環境を用意したり linux 上のユーザをわけたりはしなかったが特に不都合はなかった
- 以前参加したときのように個々で修正して個々でベンチマーク実行などを行うようなことをしなかったため?
- 秒速5センチメートルは未視聴です(君の名は。は先週観ました)
道に迷ったおばあさんを待ち合わせ場所にデプロイしていた #isucon
— nise_nabe (@nise_nabe) 2016年9月17日
さくっと newrelic 入れて動かしたら アプリが大体 CPU 使ってたからこれクエリ勝負じゃねーなと思ってた pic.twitter.com/KOQoAdFzbX
— nise_nabe (@nise_nabe) 2016年9月18日
コミットログです #isucon pic.twitter.com/u520RWnqVU
— nise_nabe (@nise_nabe) 2016年9月18日
昼食
260 円
とりあえず MySQL Connector/J 6.0 をビルドする
MySQL :: MySQL Connector/J 6.0 Developer Guide :: 4.4 Installing from the Development Source Tree
$ git clone -b release/6.0 git@github.com:mysql/mysql-connector-j.git
lib というディレクトリがあるので、最低限必要なものとして hibernate4 を ダウンロードしてきて展開して、中にある lib の jar を含むディレクトリをそのまま lib 以下に設置する。ant dist するだけなら hibernate4 だけがあればよさそう。(動くかは知らない)
$ tar zxvf hibernate-release-4.2.21.Final.tgz $ ls hibernate-release-4.2.21.Final/lib envers jpa optional osgi required $ mkdir /path/to/mysql-connector-j/lib/hibernate4 $ mv hibernate-release-4.2.21.Final/lib/* /path/to/mysql-connector-j/lib/hibernate4
ちなみに mysql-connecotor-j/lib 以下に直接展開すると関係ないファイルが邪魔してビルドに失敗する。
そして以下のように実行する。JAVA_HOME は設定されてなければ自分で設定する。
$ ant dist -Dcom.mysql.cj.build.jdk=$JAVA_HOME
Intellij IDEA 上で Ant の Run Configuration から起動する場合はなぜか文字コードが変になるので下記のように javac のところに encoding="utf8" が必要になる。
diff --git a/build.xml b/build.xml index a6ba44c..beffab7 100644 --- a/build.xml +++ b/build.xml @@ -814,7 +814,8 @@ See also com.mysql.cj.core.conf.PropertyDefinitions.SYSP_* variables for other t fork="yes" executable="${com.mysql.cj.build.jdk.javac}" compiler="modern" - includeantruntime="false"> + includeantruntime="false" + encoding="utf8"> <include name="**/*.java" /> <exclude name="testsuite/**" /> <exclude name="com/mysql/cj/jdbc/integration/**" />
とりあえず 5.1 とは違ってちゃんとビルドできる。すばらしい。以上。
MySQL Connector/J 6.0 の Service Provider について
下記 記事は Connector/J 5.1 についての記事。
6.0 の場合は
$ curl -L -O https://dev.mysql.com/get/Downloads/Connector-J/mysql-connector-java-6.0.3.tar.gz $ tar xvf mysql-connector-java-6.0.3.tar.gz $ cd mysql-connector-java-6.0.3
build.xml を確認してみると下記のようになってます。
592 <!-- JDBC 4+ support of service provider mechanism. --> 593 <mkdir dir="${com.mysql.cj.build.dir.driver}/META-INF/services/" /> 594 <echo file="${com.mysql.cj.build.dir.driver}/META-INF/services/java.sql.Driver" 595 message="com.mysql.cj.jdbc.Driver" />
じゃあどのドライバを使うかというのはどこで決めてるかというと ConnectionString クラスらしい。
src/main/java/com/mysql/cj/core/ConnectionString.java 55 SINGLE_CONNECTION("jdbc:mysql://") { 58 LOADBALANCING_CONNECTION("jdbc:mysql:loadbalance://") { 70 FAILOVER_CONNECTION("jdbc:mysql://") { 82 REPLICATION_CONNECTION("jdbc:mysql:replication://") { 144 FABRIC_CONNECTION("jdbc:mysql:fabric://") { 155 X_SESSION("mysql:x://") {
ちなみに 5.1 では下記のように場所がばらけているうえにわりと力技っぽく解決してるので 6.0 でだいぶ綺麗に書きなおされているらしいということがわかる。
src/com/mysql/jdbc/NonRegisteringDriver.java 63 private static final String REPLICATION_URL_PREFIX = "jdbc:mysql:replication://"; 65 private static final String URL_PREFIX = "jdbc:mysql://"; 67 private static final String MXJ_URL_PREFIX = "jdbc:mysql:mxj://"; 69 public static final String LOADBALANCE_URL_PREFIX = "jdbc:mysql:loadbalance://";
src/com/mysql/fabric/jdbc/FabricMySQLDriver.java 97 if (!url.startsWith("jdbc:mysql:fabric://")) {
DragonFlyBSD + letsencrypt インストールログ
環境
- DragonFly v4.4.3-RELEASE
ログ
letsencrypt 日本語ドキュメント certbot ドキュメント
ものによっては certbot-auto とか letsencrypt-auto とかよくわからんのでまずは検索。
$ sudo pkg search letsencrypt letsencrypt.sh-0.2.0 Pure BASH/ZSH Lets Encrypt client
https://letsencrypt.org/docs/client-options/
中身から察するにおそらくこれらしい https://github.com/lukas2511/letsencrypt.sh
$ cd /usr/local/etc/letsencrypt.sh/
とりあえず下記のものがサンプルとしてあるので .sample を消したものを設置
config.sh domains.txt hook.sh
今回の場合はすでに nginx + php-fpm で動いてるドメインに対して 証明書が欲しいので既存の server ディレクティブに letsencrypt.sh が作るファイルが読めるような設定を追加します。 nginx についてそんなに詳しくないので、今回は .well-known/acme-challenge 以下に来るアクセスをそのまま letsencrypt.sh が生成するディレクトリのパスにしてしまう設定にします。
# for letsencrypt location ^~ /.well-known/acme-challenge/ { default_type "text/plain"; root /usr/local/etc/letsencrypt.sh/.acme-challenges/; }
/usr/local/etc/letsencrpyt.sh/config.sh
#WELLKNOWN="${BASEDIR}/.acme-challenges" WELLKNOWN="${BASEDIR}/.acme-challenges/.well-known/acme-challenge"
一応 nginx を再起動などしたあと、下記コマンドを実行して取得する。
# /usr/local/bin/letsencrypt.sh --cron
取得した後は下記のように設定すると良いと思います。最低限の設定しかいれてないのでもっと安全にするにはググッてください。
listen 443 ssl; ssl_certificate /usr/local/etc/letsencrypt.sh/certs/example.com/fullchain.pem; ssl_certificate_key /usr/local/etc/letsencrypt.sh/certs/example.com/privkey.pem;
ここまででとりあえず https でアクセスできるようになると思います。
証明書の更新についてですが、インストールしたときに下記のように表示が出ますが、この通りに /etc/periodic.conf に設定を追加すると勝手に更新されるようです。まだ動作確認まではしてません。
To use this script you should copy the examples in /usr/local/etc/letsencrypt.sh/ and at least add a domain and a contact mail address. You should also copy the openssl.cnf.sample file in /usr/local/openssl so you won't get warnings about it missing. In order to run the script regularly to update the certificates add this line to /etc/periodic.conf weekly_letsencrypt_enable="YES" Additionally the following parameters can be added to /etc/periodic.conf To run the certification renenewal as a different user weekly_letsencrypt_user="_letsencrypt" To run a script after the renewal (as root) weekly_letsencrypt_deployscript="/usr/local/etc/letsencrypt.sh/deploy.sh"