0x19f (Shinya Kato) の日報

主にプログラミング関連の話をします

9/10 PyCon JP 2017に参加してきました

9/8, 9に行われたPyCon JP 2017に参加してきました.
pycon.jp

正直あまりPython書いたことないのですが, 今年は思い切って行ってみることにしました.
というのも, なんと参加枠に早稲田大学生という枠があって, しかも参加費無料だったんですね.
おまけに開催場所は普段まさしく授業を受けている理工のキャンパスの63号館.
これは参加しない手はないということで即connpassから申し込みました.
決して懇親会のタダ飯が目当てではないです.


PyCon JP 1日目

申し込んだものの, 1日目は大学の夏期集中講座と被ってしまったので, 夕方のLTからの参加です.
(昼間は隣の建物で授業受けてました.)

LTの中で印象に残っているのは, 「built-in関数への代入はやめよう」という趣旨の発表です.
Pythonそんなに書いたことのない自分はこの時は初めて知りました.
listってbuilt-in関数なのかよ！
間違いなく今までにlistという名前にリストを代入した覚えがあります.
知らずにbuilt-in関数の人権を侵害してきたんですねぇ, 申し訳ない...

その他では, ギャル語翻訳も結構インパクト強かったですね.
togetter.com

PyCon JP 2日目

2日目は丸一日参加しました.
いくつか印象に残ったセッションの感想を書いておきたいと思います.

Opening Keynote

speakerdeck.com

pandasとDaskのコミッタである堀越さんのセッション.
OSSコミッタがどんな仕事をしているのか, これからOSS活動を始めたい人が何をすべきなのかという内容でした.
最近Pythonで機械学習をした時にちょろっとpandasを使ったので, 聞いていて話の理解はしやすかったです.

セッションを聞きながら, OSSに貢献はしたい一方で, バグっぽいものに遭遇した時に自分のミスなのか本当のバグなのかの切り分けが難しいよなぁと.
巨大なソフトウェアともなると, ドキュメントだけでも読み切れないぐらいあるので.
そういう状況でissueを書くってのもなかなか勇気がいるなぁなんて考えてました.
あぁいうのってどれぐらいのノリで書くものなんですかね.

Pythonで実現する4コマ漫画の分析・評論 2017

slideship.com

4コマ漫画を各コマごとの画像に変換, セリフを抜き出し, 登場人物を特定するという試みでした.
正直に感想を言うと, ゆゆ式の話が気になって肝心の機械学習周りの話があまり理解できませんでした！

今でも当時のアニメ放送時間になるとエア実況が発生
2017年9月5日(火) 24:30放送(?)分で18クール214話

ゆゆ式の何があそこまで人を狂わせるのか気になったので, そのうちアニメ見てみたいと思います.

理論から学ぶPythonによるサーバーレス開発

slideship.com

サーバーレスって聞いたことはあってもどういうものか全く知りませんでした.
「名前から推測するにサーバーがないということなんだろうか？？？」とか思ってたぐらいです.
とりあえず, セッションを聞きながら一般的なWEBサービスとは相性そんなによくないのかな？って思ったぐらいしか理解できませんでした.

PyConJPで彼女つくってみた(LT)

slideship.com

支離滅裂な文章を返してくるところがマルコフ連鎖の面白いところですよね.
素敵な彼女さんができることを祈っています(遠い目).

まとめ

今までPythonそんなに書いてきませんでしたけど, 今回でいろいろと便利そうなものがあるのもわかったのでちょっと勉強していきたいと思います.

こんな素晴らしいイベントの参加権をいただけで本当に幸運でした.
スタッフのみなさん, 登壇者のみなさん, ありがとうございました.

IMG_4875

8/21 サマーウォーズを見てRSA暗号について調べた

普段テレビはほとんど見ないのだけれど, 先日は金曜ロードショーのサマーウォーズを見てました.
相変わらずいつ見てもいい作品だなぁとか夏希先輩かわいいなぁとか思いつつ, Twitterでわいわいしてました.

サマーウォーズが放送されると必ず話題に上がるのが健二が解いているあの暗号の話.
解いている様子の描写からRSA暗号じゃないかと言われています.
RSA暗号というと素因数分解というイメージが強いのですが, あまり暗号化と複合の部分がどういう原理でできているのかについては理解できてませんでした.
というわけで, サマーウォーズを見ながらいろいろと調べて考えてみたことをまとめてみたいと思います.

公開鍵暗号方式

そもそも, RSA暗号は公開鍵暗号方式の一種で, 2つの鍵を用いて暗号化と復号を行います.
簡単に言うと, 以下の2つの性質を持つような暗号です.

1. 片方の鍵で暗号化したら, もう片方の鍵でしか復号できない.
2. 片方の鍵からはもう片方の鍵は(簡単には)推測できない.

RSA暗号の基本的な仕組み

RSA暗号の基本的な仕組みについてはWikipediaなどを参照してもらうと良いと思うのですが, 簡単に書いておきます.
RSA暗号 - Wikipedia

p, q: 任意の素数, n = pq
e: (p - 1)(q - 1)と互いに素な任意の正の整数(公開鍵)
d: ed = 1 \pmod{(p - 1)(q - 1)}を満たす正の整数(秘密鍵)
m: 平文, C: 暗号文

暗号化: C = m^e \pmod{n}
復号: m = C^d \pmod{n}

というわけで, 実は累乗が計算できれば暗号化と復号は簡単にできます...
ってほんまか？となるわけですね.
これってつまり, m^{ed} = m \pmod{n}が成り立つってことに他ならないわけです.
さすがに自明ではないよなぁ......と.

復号がうまくいくのはフェルマーの小定理で説明できる

『高校数学の美しい物語』の説明がわかりやすかったです.

mathtrain.jp

少し補足をすると, 合同式には以下の性質があります.

a = b \pmod{p}かつ a = b \pmod{q}ならば a = b \pmod{lcm(p, q)}
( lcm(p, q)は pと qの最小公倍数を表す.)

つまり, m^{ed} = m \pmod{n}を示すためには, m^{ed} = m \pmod{p}を示せば十分ということになります.

興味深いのは, フェルマーの小定理を用いているところです.
これを利用してうまく暗号化ができるようになっているわけですね, 賢い.

素因数分解の困難性が安全を保証している

公開鍵暗号方式なので, 公開鍵 (e, n)から秘密鍵 (d, n)が推測されると暗号を突破されてしまいます.
秘密鍵を推測するためには ed = 1 \pmod{(p - 1)(q - 1)}を満たす dを計算する必要があります.
つまり, nを素因数分解して p, qを求め, (p - 1)(q - 1)を計算する必要があるわけです.

素因数分解は p, qが十分に大きな素数であれば現実的な時間で解くことはできません.
逆に言えば, 素因数分解ができてしまえば暗号を解読することができます.

「RSA暗号 = 素因数分解」というイメージ

サマーウォーズを見ながら, 流れてくるRSA暗号についてのツイートを眺めていたのですが, 「素因数分解する暗号」という説明が結構多かった気がします.
まぁ確かに「ふたつの素数 (p, q)から積 nを求めるのは簡単だけれど, nから (p, q)を計算するのは困難」と言われると, なんとなくわかったような気がしてしまうんですよね.
「素因数分解が効率よくできない」って直感的なのでそういう説明が出てくるのはわかるのですが, それって誤解の原因になりやすいんじゃないかなぁと.

人間って直感的な事柄の次に非直感的な事柄が出てくると, なんとなく理解した気になってしまうところがあると思います.
やはりそういう説明で納得してしまうことのないように気をつけたいなぁと.

まぁ, そんなことを考えていたよ, というお話でした.
(余談ですけど, はてなブログってTeXの数式を書くとMathJaxでレンダリングしてくれるんですね.)

8/11 AtCoder Regular Contest 080

この前うっかり寝過ごしてで損ねたARC080を解いた.

  • C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder [解答]

    数列の要素を自由に並び替えて隣り合う要素の積が4の倍数になるようにできるか判定する問題. Aiが奇数, (4の倍数でない)偶数, 4の倍数で隣に置かなければならない数の条件が変わることに注目する. Aiが奇数なら, 隣には必ず4の倍数をおく必要がある. Aiが偶数なら, 隣には偶数をおく必要がある. Aiが4の倍数なら, 隣におく数はなんでも良い. ここから考えると, { 奇数, 4の倍数, 奇数, 4の倍数, ..., 4の倍数, 偶数, 偶数, ... }みたいな並びが作れるかを判定すれば良いことになる.

  • D: Grid Coloring - AtCoder Regular Contest 080 | AtCoder [解答]
    1, 1, 1, 2, 2, 3, 3, 3, 3, ...., N, N, Nと左上から順に要素数H * Wのマス目を埋めていき, 奇数番目の行だけreverseして表示すればOK.

  • E: Young Maids - AtCoder Regular Contest 080 | AtCoder [解答]
    辞書順で最小のものを構成するのは後ろから考えるとやりづらいので, 先頭から小さい数字を順に決めていくことを考える. 最初の状態からqの先頭2つの要素を決めるのには, 偶数番目の要素でもっとも小さい値とその要素以降で奇数番目の要素を取るのが最良. この二つの要素がpのi, j番目だとすると, pは[0, i), [i + 1, j), [j + 1, N)の3つの要素に分断される. qの次の2要素はこの3つの領域の偶数番目の値から最小のものを選ぶことになる. これを繰り返していけばO(N^2)でqを求めることができる.
    ここから計算量を落とすためには, 偶数番目/奇数番目の要素から最小を求めるのにセグメントツリー, 分割された領域からどれを選ぶかはpriority_queueを用いればよい. 具体的な手順としては,
    1. { [0, N), min_odd }をpriority_queueに入れる
    2. priority_queueから最小のものを取り出す
    3. 3つの領域に分割して, それぞれをpriority_queueに入れる
    4. priority_queueが空ならループ終了, そうでないなら2に戻る
    という感じ. 結構実装がしんどかった...

8/8 束の間の夏休み

8/3で無事に春学期の期末試験を全て終えて夏休みに突入した. しばらくは休養がてらアニメ見たりして過ごしてた. 昨日から大学の夏期集中講座でまた学校に来ている. なんだかオープンキャンパスで高校生がいっぱいいたり, 何かのイベントで小学生がいっぱいいたりして普段とはかなり違う雰囲気.

 

AtCoder

  • B: Colorful Creatures - AtCoder Grand Contest 011 | AtCoder [解答]
    スライムがN個あってそれぞれの大きさA[i]が与えられている. スライムは自分の大きさの2倍以下の大きさのスラムを吸収してその分大きくなることができる. こうしてスライムが吸収を繰り返して最後に残るスライムが1個になる時, 最後に残るスライムは何通り考えられるかという問題.
    とりあえず, 大きさの昇順にソートして考えてみる. 昇順に並んでいれば, i番目のスライムは1からi - 1番目までのスライムを吸収することができる. i番目のスライムがそれら全てを吸収すると大きさは, A[1]からA[i]までの和sumとなる. この時A[i + 1] <= sum * 2であればi番目のスライムがi + 1番目のスライムを吸収することができる. A[i + 1] > sum * 2であれば, どう足掻いてもi番目のスライムは全てのスライムを吸収することはできない. よって, A[i + 1] > sum * 2となる最大のiを探せば, 答えはN - iとなる. そのようなiが存在しない場合は答えはNとなる.
    実際の実装では降順にソートして, A[i] > sum(A, A + i - 1)となったところでループを抜けるって感じにしてます.

  • B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder [解答]
    光が2個めの反射点に辿りついた直後, 残っている正三角形の領域は平行四辺形になっていることに注目すると考えやすい. このあと何度か光が反射すると再び平行四辺形ができる. この時, 何回光が反射すると次の平行四辺形になるかは二つの辺の長さから計算できる. また, 次の平行四辺形の辺の長さも同様に計算できる. 具体的には辺の長い方をa, 短い方をbとするとa = b, b = a % bになる. これを見てわかる通り, 辺の長さはlogで減っていく. イメージとしてはユークリッドの互除法みたいな感じ. これをbが0になるまで繰り返す.

7/30 ISUCONの練習始めました

今年こそISUCONに出たい

前々からISUCONにチャレンジしてみたいなぁーと思っていたのもあって, 今年こそはちゃんと練習しようと思っています. 夏休みに入って時間も取れるようになってきたので.

とりあえず, Vagrant使って過去問を触ってみる. ISUCON過去問とほぼ同じサーバー環境をVagrantで構築するためのVagrantファイルを公開してくださっている方がいるので, それを使う. 圧倒的感謝.

d.hatena.ne.jp

github.com

環境構築の手順

リポジトリをgit cloneして立ち上げたい問題のディレクトリに移動, vagrant upするとサーバーが起動する. ちなみに, 起動には結構時間がかかるので注意. あと, なぜかISUCON6のqualifyはうまく立ち上げられなかった. というわけで, isucon5-qualifyを立ち上げてとりあえずベンチを取ってみるところまでメモしておきます.

1. Virtualbox, Vagrantのインストール
brew cask install virtualbox
brew cask install vagrant

すでにインストールしている場合は, バージョンが古いとエラーが出ることがあるようなので再インストールしておくといいと思います.

brew cask reinstall virtualbox
brew cask reinstall vagrant
2. Vagrantfileが入っているリポジトリをcloneしてくる.
git clone https://github.com/matsuu/vagrant-isucon.git
3. 立ち上げたい問題のディレクトリに移動してvagrant up
cd vagrant-isucon/isucon5-qualifier/
vagrant up

これが結構時間かかります. 気長に待ちます. 諸々の準備が終わるとimageというサーバーとbenchというサーバーが起動しているはずです. きちんと把握してないですが, imageは問題を解く用, benchは負荷走行用かなと思っています. おそらく, 予選本番ではimageの方だけが参加者には与えられていて, benchサーバーにはベンチマーク取ってくださいってリクエストをするだけなのかと.

もしかしたらstandaloneは両方立ち上げないのかも. そうだとしたらそっちの方が早く起動できる(？).

4. imageサーバーにsshで接続する
vagrant ssh image
5. ユーザーを切り替える

ログインするとvagrantユーザーになっていると思うので, isuconというユーザーに切り替えます.

sudo su - isucon

そこでlsしてもらうといろいろファイルがあるのがわかると思います. 基本的にはアプリケーションなどの中身は/home/isucon以下に置かれてます.

6. とりあえずベンチを取ってみる

/home/isucon以下にbench.shというスクリプトがあるのでそれを実行します.

./bench.sh

しばらく待っているとベンチが終わって, 以下のような結果が標準出力に出てきます. これがスコアになるようです.

...
Isucon5Checker
done
success
114.1
{"success"=>206, "redirect"=>81, "failure"=>1, "error"=>0, "exception"=>0}
アプリケーションが 3000 ミリ秒以内に応答しませんでした

ここからやること

基本的にはNginxとMySQLのログを見ながらボトルネックになっている箇所を探していくことになるかなぁと考えています. MySLQはベンチ取った時のログをざっと見る限りでは結構N+1クエリがありそう. 他にもいくつか時間かかっているクエリもあったのでそのあたりを中心に見ていくことになりそう. あと, 実際にブラウザからアクセスもしてみるとどういうお題なのかわかりやすくていいかなぁと.

チームメンバーに競プロerがいるので, C++でゴリゴリ書き直すみたいな戦略も面白いかなぁって思っている. ちなみに, 昨年はC++で予選を突破したチームが1つだけいた模様. と思って調べてみたらまさかのこのチームで爆笑してしまった.

ISUCON6予選をC++で参加して予選通過した話 - いもす研 (imos laboratory)

さすがに自前でC++のWebサーバーを作るのは険しすぎるのでC++でCGIとか作ってみるのはどうかなぁなんて考えているところ. どれぐらい速度出るか全くわからないけれど.

7/29 ARC079

AtCoder Regular Contest 079

C, Dを解いて2完. Eはにぶたんとかいろいろ試したけれどダメだった. Fは問題さらっとしか読んでないです.

  • C: Cat Snuke and a Voyage - AtCoder Regular Contest 079 | AtCoder [解答]

    島1から繋がっている島すべてに対して, Nと繋がっているかどうかを調べる.

  • D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
    K回操作を行った後に0, 1, 2, 3, ..., N - 1という長さNの数列になるような数列を作る. 1回操作を行ってこの数列が得られるような列の中にはN, 0, 1, 2, ..., N - 2という列がある. 同様に, 2回操作を行ってこの数列が得られるような列の中にはN - 1, N, 0, 1, ..., N - 3というものがある. これを一般化すると, A[i] = K / N + (N - i - 1) + (i < K % N)とすれば良い. Nはとりあえず50にしておいた.

  • E: Decrease (Judge ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
    最大になるものを選んでとあるが, 実は操作する順番を変えても答えは一緒になる. なので, A[i]がN未満になるまで減らして他の要素には+1をするというのを全要素がN未満になるまで繰り返せば良い.
    コンテスト中は二分探索をしようと思ったのだけれどどうやら, 解の付近で単調性が崩れるらしくて正しく答えが求められなかった. ちなみに, 解の範囲をある程度絞った後で範囲のしたから解を探すってことをしたら通った(提出コード).
    周辺まで見る二分探索をしているレッドコーダーの方もいたみたいで, その正当性をTwitterで話していたけれど正直よくわからなかった.

7/27 久々に.vimrcを整理したい

今までずっと補完というものを使わずにプログラムを書いてきた. なのだけれど, 英単語のスペルミスがあまりにも多かったり, 特定の単語を特定の間違い方することが多いので補完を使ってみることにした. とりあえず, vimの標準の補完機能(ctrl + p)を使ってみたけれど, 普通に慣れていないと押すのを忘れそう. というわけで, NeoCompleteというプラグインを入れてみた.

github.com

 

設定を.vimrcに書いておけば, プログラム書いてると勝手に補完窓が出てくるのでひたすらTabを押せばOK. これなら慣れてなくても使えそう. あとは言語ごとに辞書ファイルとか追加しておくと便利そう.

ちなみに, このプラグインはluaを使っているらしく, 自分の使っているvimにはluaを入れていなかったため, brewでインストールし直した. brew install vim --with-luaでlua付きでコンパイルされる. 途中pyenvと何かがコンフリクトしたっぽく, インストールするときだけ.bash_profileからpyenvのパスを通している部分をコメントアウトした.

 

他に最近ほしいなと思った機能が, vimでcsvファイルを開いた時にコンマで整列させるスクリプトとか. これないとさすがにデータの中身を覗くのがしんどいので. 今は普通にExcelでファイルを開いているけれど, csvの中身を見るためだけにいちいちExcel起動させるの面倒だし.

その他でvimrcをきちんと整理したいと思っているのが, quickrunの設定. 何かの言語を実行する時に非同期実行だと結果がうまく得られなくてオフにしているのだけれど, やっぱりほしいなと.