AtCoder Beginner Contest 151
今回は A から C まで。ランクも下がった。
どちらかというと今回は解けたという話でなく、どうして解けなかったか?という話になる。 普段は競技プログラミングで点が取れなかった話は振り返ってみても役に立たないので書かないが、 今回は教訓を見出したので自戒を込めてブログ記事にしている。
で、
その解けなかったのは D で、与えられた迷路に対して適当な始点と終点を与えて最短パスを最長にする、というような問題だった。
問題サイズは割と小さかったので、総当りで始点を設定して BFS で最も遠い点を出せばいいかと考えた。 ただ実行時間はなるべく短くしたかったので、始点からは次の条件を満たすものを除外することにした。
- 上下の点が通行可能
- 左右の点が通行可能
要するに通路のあたるような点は始点終点から外そうとした。 これは割ともっともらしい。最短パスが最長になる始点終点はなにかしら端のほうになりそうだ。
ということで実装をして提出してみたのだが、最後の1ケースだけ WA になるという残念な結果になってしまった。 コンテスト時間中はなにかしら問題文で見落とした箇所があったのかとか、特殊なケースがあったりするのか、など考えていたが、 なんのことはない、上に述べた除外している箇所を外すだけでうまく動いたのだった。
これに気付いた後で、そのケースを考えてみると次のようなものがあった。
■■■■■ ■□□□■ ■□■□■ ■□□□■ ■■□■■ ■□□□■ ■□■□■ ■□□□■ ■■■■■
このような8の字型の迷路だと、8の上側の通路と下側の通路を指定すると最短経路が最長になる。
なにが悪かったか?
明らかに余計な条件を加えたのがよろしくなかった。
高速化の鉄則として、
まず正しく動くものをつくり、それから最適化する
というのがある。これこそなにより自分が気を付けなければいけなかったことで、競技プログラミングであってもこの鉄則に従わなかったのは申し訳がたたない。
「高速化する」というのは競技プログラミングの上でももっともらしく聞こえるが、まず正解を出すのが最優先だ。 そもそも速くなるケースは限られるという時点で、最も時間がかかるテストケースが投げられてくる競技プログラミングへの解答としては不適切であったし、今回のようにパッと思いつかないようなレアケースに足を引っ張られることもある。
教訓としては、総当りでいくと決めたら変に高速化を目指さない、ということになるか。TLE になってから考えればよいし、焼け石に水的な高速化はおそらく間違いの場合が多い。
PyTorch と自然言語処理
AtCoder Beginner Contest 145
今回も A から D まで解いた。
ようやく上の方に青が見えてきたがまだまだ遠い。
良かった点
A-D までは継続して解けている。
C は全経路のコストに何かしらの値をかければ良さそうだとわかった(すべての組み合わせなので、どの枝も同じ回数だけ出現するはずである)。
全ての枝のコストが 1 だった場合は、明らかに n! が全経路のコストの和になる。
なのでここから計算すると、全枝のコストの和 x (n-2)!/2 が解答になる。
反省点:
C のケアレスミス
解答に精度の設定がある問題だったが、その設定を忘れていたので、 WA をもらってしまった。
すぐに終わるはずの問題だったが、終了間際になるまで気づかなかった。
入力例 1 で気づいていてもおかしくなかったのだが、急ぐあまり見落としていたようである。
D の組み合わせ数
D は本質的に組み合わせの数 = nCr を計算する問題。
頻出の問題なので、こういうのこそ前もって準備しておくべきなんだろうが、それができていなかった。
ただやり方自体は Qiita の次の記事を見た覚えがあったので、時間内に調べてなんとか間に合わせた。
https://qiita.com/ofutonfuton/items/92b1a6f4a7775f00b6ae
結局時間内に AC は出せたがぎりぎりになってしまい E には進めなかった。
知っていれば簡単に回答できる問題なので、こういうのはしっかり抑えておきたい。
退職記事を書きたかったが書けなかった話
ここ最近 Google の採用プロセスを受けていたのだが、結局パスすることが出来なかった。
退職記事で書けばいいかと思っていたが、会社の現時点での作業からの現実逃避がしたかったのでさっさとまとめる事にした。 会社の人が誰か見ているかもしれないが、ちょっと自暴自棄になっているのでそうなってもまあいいや。
そもそものきっかけとしては LinkedIn 経由で Google のリクルータの人から接触があった。最初はスパムかな?と思っていたのだが、メールアドレスが @google.com になっていたのを確認して本物なの?という事で返信。 もちろんスカウトではなく、こういう風に採用をやっているので受けてみないか?というぐらいの話をこの時はした。
実はこれが 2 月ごろで、その後自分の方でも色々準備したり Google I/O に参加したり英語メール書くのに躊躇したりがあってしばらくコンタクトを取っていなかった。 この期間中にも他の会社の採用面接を受けてみたりもしたのだが、やっぱり Google のが保留になっている状態だとよくないなという事で、失敗するにしてもちゃんと採用プロセスを進めておこうという気になった。 で結局は次のステップに進むのは 8 月ごろになってしまった。
再度リクルータの人に連絡を取って簡単なインタビューを英語でやらしてもらった。この時は内容的にはいい部分はあったが英語頑張ってね、という事で数週間ぐらい英語を見直してから実際の採用プロセスに進んだ。
採用プロセスは次のような感じ:
- リモートでのインタビュー
- オンサイトインタビュー 1 回目
- オンサイトインタビュー 2 回目
- 以下進めなかったプロセス
オンサイトインタビューでは必ず 1 回は英語での物を含むらしい。
まずリモートでのインタビューはうまくいった。難易度でいうと、多分 AtCoder でいう C くらい?
で、次のオンサイトインタビューには進めたのだが、そこでコケた。
フィードバックによると、アルゴリズムやデータ構造については問題なさそうだったが、コーディングやコーディング速度があまりよろしくなかったとのこと。
この点で反省点としては、多分実施日を金曜にして、かつ前日まで仕事で使っていた言語でインタビューに臨まなかったのはよくなかったと思う。インタビューの際に Go だか C++ だか Python だかが混じったような物を書いてしまって結構まごついてしまったのがみられたんだとは思う。
本来自分が得意だと思っていた部分でしくじっていたのはかなり残念。 なのだが、振り返ると思い当たる節は結構ある(会社への愚痴になりそうなので具体的な例は避けておく)ので、その点に気づけただけでも儲けものだったと思いたい。
足りてない部分としてやっぱりコーディング量が足りてないというのはあるので、なんとか増やすようにしたいところではある。
またせっかく Google の新社屋でランチをいただく機会だったのに出来なかったのが残念。 オンサイトインタビューの時にインタビュアーの人に聞いたら伝えておけばランチ食べさせてもらえそうだったので、次のオンサイトインタビューに進めるんだったらその時に行っておきたかった。 これから受ける人はオンサイトインタビュー受ける際にランチも食べたい旨を伝えておくといいかと思う。
他の Google の採用プロセスを受けた人も書いていたが、リクルータの人はかなり親切に採用プロセスの説明とか、不足している部分とかを指摘してくれるので非常にありがたかった。
他のよくなかった点としてはかなり時間がかかってしまった事。最初にコンタクトを受けた時に急がなくてもいいと言われたのに甘えたのもあるが、Google の引っ越し時期と重なったのと、インタビューのために午前休とか1日休みとか設定しないといけなかったので、なかなか進まなかった。年度末が近づいてきてしまってキリのいいところでの転職を狙うのが難しくなったのはよろしくない。次があるとしたら早めに終わらせるようにしたい。
次チャレンジする機会があるとしたら1年後か。その時の状況にもよると思うが、またチャレンジするかも。
PyConJP 2019 に参加してきたメモ
今年も PyConJP に参加してきた。
今年のテーマは「Python New Era」で Python の新時代の話をしようということだったが、 内容的にはやはり機械学習関連の話が多い。
1 日目は機械学習中心。 2 日目はそれ以外のテーマを中心に見ていくことにした。
Why Python is Eating the World
1 日目オープニングは最近和訳された「独立プログラマの作者」Cory Althoff さんによる Python がどうして流行っているかと、Python 習得してどのように職歴を積むとよいのか、という話。
発表者は特に数学などの成績が良かったわけでもなく、大学で Java を諦めたくらいだが、 Python を始めたおかげで今では高給をもらって豪邸に住むまでになったとのこと.
Python が世界を席巻している理由として挙げられていたのは以下の 3 つ: 1. 初心者が受け入れやすい 2. 企業からの需要がある 3. 良いコミュニティがある
Python でフリーランス始める場合に最初にやるおすすめの仕事は Web スクレイピングで、 比較的簡単は作業で高評価をもらってそれを足がかりに実績を積んでいくといよいらしい。 経験したことは LinkedIn に登録してそこからよい職を取るといよいという話だった。
フォローすべき Pythonista として次の人たちが紹介されていた。
- Mike Grouchy: a founder at Pycoders Weekly
- Julian Sequeira: a founder of PyBites
- Mariatta Wijaya: a core python develope
- Takayuki Shimizukawa: Python author and Sphinx contributor位
また Python 学習におすすめのサイトも紹介されていた。
感想
これから IT 業界に飛び込もうという人にはかなりいいんじゃないかと思える。 またこの言語を学ぶことで得られる恩恵がかなり具体的に・実体験付きで話されているので説得力高い(日本でも同じかどうかは 微妙だが…)。
Python と AutoML
サイバーエージェントの AI ラボの芝田 将([c_bata https://twitter.com/c_bata])さん Automated Machine Learning in Python
機械学習の自動化の話。 AutoML は Google のサービスでなく、機械学習自動化全般のことを指すみたい。
自動化のレベル分けと AutoML の要素技術
自動化は 3 つの観点 * ハイパーパラメータ最適化: 少ない試行回数でよりよいハイパーパラメータを得る * 特徴量エンジニアリング: 適切な特徴量を選択する * アルゴリズム選択: 適切な機械学習アルゴリズムを選択する
ハイパーパラメータの最適化
- ベイズ最適化: Gaussian Process, TPE, SMAC
- 早期停止: Successive Halving, Hyperband
おすすめライブラリ
- Optuna: TPE, SuccessiveHalving に対応
- scikit-optimize: GP に対応
特徴量エンジニアリング
特徴量エンジニアリングはすごく重要で、時間がたくさんかかる。
現在あるライブラリはどれも基本的なものだけ対応(ex, 欠損値保管、次元削減)
- 特徴量生成
- 特徴量選択
アルゴリズム選択
機械学習のアルゴリズムはチートシートがあるくらいに煩雑だが、 かといって自動化して嬉しいかどうか議論の余地ある。
機械学習におけるハイパーパラメータ最適化の理論と実践
こちらも機械学習の自動化の話。
- ハイパーパラメータ最適化
- Black-box 最適化
- Gray-box 最適化
おすすめソフトウェア
- Optuna
- defin-by-run スタイル
- ログも綺麗で使いやすい
- BoTorch -> AX
- from Facdbook
- adaptive experiment platform
- HPO より幅広いプラットフォームらしい
- バンディットアルゴリズムなども提供
- Ray
- 強化学習の RLib と相性がいい
- 分散環境得意
Python による日本語自然言語処理
nagisa をつかった日本語自然言語処理の話。
- 自然言語処理のよくある流れ
- コーパス→ 前処理 →データ →学習→モデル→評価
- nagisa
- feature
- BLSTMs による単語分割と品詞タグ付け
pip install nagisa
ですぐ使える- 単語、品詞推定、“語形変化の処理“ はない
- feature
- BLSTMs = Bidirectional LSTMs
- 前向き LSTM と後ろ向き LSTM を計算
- 入力全体の情報を各時間で考慮できる NN
- nagisa メソッド
- 実施
nagisa.tagging(text)
- 単語の抽出
tokens.words
- 品詞の抽出
tokens.postags
- ユーザ辞書への追加
new_tagger = nagisa.Tagger(..., single_word_list=[“あたらしい単語”])
- 実施
Python ウェブアプリケーションのためのプロファイラの実装 by Yusuke Miyazaki
- wsgi_lineprof
- line-by-line profiler for web app
- アーキテクチャ
- capture request/response
- get infromation on execution
- measure exec time per line
- WSGI middleware
- Implementing WSGI Middleware
- tracing
- wsgi perf では
PyEval_SetTrace
を使う
- wsgi perf では
- measuring time
- C 拡張を用意してプラットフォームごとに使い分け
- 使ったもの
- POSIX: clock_getitime()
- masOS: math_absolute_time()
Introduction to FEM Analysis with Python
Python で有限要素法を行う話
Python で切り開くあたらしい農業
TensorFLow の利用例としてきゅうり仕分け機が有名だが、 その開発時の試行錯誤の話などを聞けて興味深かった。
初期バージョンでは仕分けまでをコンベアを使ってやっていたが、きゅうりに傷がつく、結局どこかで人手がいりそう、なども問題があって完全自動化から人間の手助けをする方針に切り替えた。
他やってみてわかったこと:
- 熟練者のノウハウ継承の可能性
- ノウハウの継承 (熟練者→ AI → 初心者)
- 半年ぐらい使っていると、AI の助けがなくてもできるようになる
- 自動化だけじゃない DL の可能性
- 障害者も働きやすい環境作り
- 人間同士のコミュニケーションの支援
Inside a companion robot belm0
Lovot 内部の並行処理の話。
スピーカーの人はビブリボン!の開発にも携わっていたとのこと。
Lovot は 人間とインタラクションしながら表示を行ったり音をだしたりと、 並行処理の塊で、 GroovX社ではいろいろ工夫して生産性を上げていた。
並行処理で気をつけた点として以下が挙げられていた:
- 開発を妨げない
- 低レイヤを担当しないチームも含めて並行処理で患わせないようにする
- 適切な言語を選択する
- これは Python を使えば解決
- 並行処理の導入で不明になるような処理・わからなくなるような処理を出さない
- とりわけ mutable な状態・副作用とか
- プログラム内部を外部から観察・インタラクト可能にする
- 自家製のヴィジュ荒いぜーションツールを用意した
- (たぶんプロダクト or OSS に対する)
- Trio の開発者とコンタクトを取り、チームが変更を恐れずとれるようにした
上記の 3. のために、次のような戦略でシンプルな並行処理にする最適化をおこなった:
- 明確なコンテキストスイッチ/シングル OS スレッド
- 統合されたキャンセル処理
- 構造化した並行処理
- async/await
- コルーチン
このうち、「統合されたキャンセル処理」と「構造化した並行処理」のために TRIO
を採用した。他は Python ネイティブの機能で対応している。また TRIO の採用で並行処理のテストも簡単にできるようになった。
例えば次のようなコードで
async with trio.open_nursery() as nursery: await pause(1) nursery.start_soon(turn, pi/2) nursery.start_soon(play_sound)
turn(pi/2)
の処理で例外が起こった場合は、他の子(ここではplay_sound
)がキャンセルされ、また親れ例外が伝播するようになっている(統合されたキャンセル処理)。
婚活・恋活領域における Python を使ったマッチング最適化 Morioka Takashi
婚活のマッチングアプリ開発の話。 ほぼ Python の話でなく、婚活アプリでの苦労話とか。
- マッチング最適化への道
- 安定結婚問題
- -> Gale-Shapley法をベースに開発
- O(n2) で安定マッチング
- マッチング手順の改善
- 全対象→グループごとに並列実行
- 計算量を制御できるが、マッチング精度の低下・少数派への悪影響がある
- 全対象→グループごとに並列実行
- 環境の改善
- A/Bテストの実施
- 改善のための基盤を準備
- ユーザをタグ付けし、これを元にスコアリング処理を切り替える
- 改善のための基盤を準備
- 機械学習の適用
- 安定結婚問題
When AI meets 3000-year-old Chinese Palmistry Kai Hsu
手相を機械学習してみた話。
Chinese Palmistry = 手相学になる模様。
機械学習の話としてはかなりベタだった。 健康、恋愛、仕事の 3 つの項目を手のひらの画像で学習していた。 手相学の方が新鮮だったくらい。
メディアが運用すべき持続可能な VTuber をつくる技術 @hirosaji
Vtuber とタイトルにあるが、音声に関する機械学習の話が中心だった。 1 人の Vtuber の中の人が変わっても問題ないようにするには声質変換処理が良いだろうとのこと。
pytestによるCIレボリューション あべんべん
pytest と CircleCI の話だった。
builderscon 2019 に参加してきたメモ
去年に続き今年も builderscon に参加してきた。
builderscon 2018 - giantneco’s blog 去年のメモ。
今年の builderscon 2019 は 8/29(木)の前夜祭から から 8/31(土) までの開催で、 元々なにか特定の技術にフォーカスするという集まりではないので、 セッションの傾向も前回とはかなり異なっている。
去年の発表がかなりよかったので今回も期待していたが、 思ったとおり色々な分野の話が聞けたので楽しかった。
前回も思ったけど運営はすごくよくやっていて、ネームカードの準備とかすごくしっかりできているので助かる。 ただ今回は前回と会場が変わったからか列管理がいまいちだったかも。次回には改善されているはず。 後はフィードバックに書き忘れたが、初心者向けとかわかりやすくしてもらえると助かったかな。
前夜祭
今年は 8/29 のカンファレンスの前夜祭にも参加してきた。
- Hololens とドローンの(まちがった)活用法
- MySQL でケーキを焼きました
- 面白いダジャレを言うと、リアルに布団が吹っ飛ぶ装置を作った
- CROSS ME で黒髪の眼鏡女子とマッチングするデバイスを AI と IoT を駆使して作った話
ゆるい感じのセッションではあったが、技術的には機械学習、AR・VR、IoT といったレベル高いものが使われている。
機会学習でリアルに「布団」が吹っ飛ぶ装置を作ったという話が一番印象にのこったかな。 まさに技術の無駄遣いという感じで、機械学習と Raspherry Pi を使って実際に動作するプロトタイプをつくるというのはやっぱりすごい
1 日目
Open SKT: メルペイ開発の裏側
Open SKT: メルペイ開発の裏側 / builderscon tokyo 2019 Open SKT - Speaker Deck
メルペイにおけるアーキテクチャの話で、 内容としては新しいメンバー向けのキックスタートや、メルカリとの方針の違い、金融を扱う上でどういうところに気を付けたか、などを聞いた。
お金が絡むと気をつけないといけない法律も増えるので、結構○○ Pay は大変そうなイメージがあるが、メルペイではうまくやっているようだった。
キーボードは好きですか?
キーボードは好きですか? / Do you like keyboards? - Speaker Deck
ランチセッションでは自作キーボードの話を聞いてきた。 内容としてはキーボードの部品の解説や、どういう魅力があるか、また自作キーボードの最近の流行とかの話があった。
なお自作キーボード関連のセッションは2つあって、かなり流行っているのかも知れない。
個人的にはそれほどキーボードにこだわりはないし持ち歩く物が増えるのは避けたいところだが、 やっている人たちは相当楽しそうなので時間と資金に余裕ができたら試してみたいのはある。
コンパイラをつくってみよう
コンパイラをつくってみよう / How to make a compiler - Speaker Deck
ライブコーディングでコンパイラを作ってみるセッション。
簡単な式を読み込んで、対応するアセンブリを出力するまでをライブコーディング実演した。すごいね。
使用した言語は Go で、 コンパイラ作るのにはそれほど向いてないんじゃないか?とも思う。 とはいえ Go でコンパイラやインタプリタを書く書籍も出ているし、発表者のいう通り好きな言語でやるのが重要なのかもしれない。 コンパイラをセルフホストしたいのであれば、やっぱりその対象言語で書くことが必要になるだろうし。
非同期処理の歴史から見たコンピューティングの進化
非同期処理の歴史から見たコンピューティングの進化 - Speaker Deck
主に Java 界隈の非同期処理の話。
Java というか JVM の話が中心になるので仕方ないが、より低レイヤや軽量スレッドとかに踏み込んだ内容ではなく、 どちらかというと初心者向けだったかも知れず自分にはちょっと物足りなかった。
Optimizing Ruby with JIT - 最速の言語を目指して
Optimizing Ruby with JIT - Speaker Deck
単純にアセンブリに下だけではほぼ速度向上がなかったのはちょっと驚いた。 効果を出すには Ruby VM の仕組みを理解した上で、最適化したアセンブリを出す必要があるようだったので、結構大変そう。
なお発表された JIT よりも速い実装はあるとのこと。その実装では組み込みメソッド以外のメソッドを呼び出そうとすると Seg fault するようにメモリを保護しておいて、メソッドが上書きされていた場合は割り込みハンドラで処理するようにしているらしい。 確かにメソッドが上書きされてない場合にはそのまま通って速いのだろうが、かなり黒魔術だなあ。
2 日目
ウォレットアプリ「Kyash」の先 〜「Kyash Direct」のアーキテクチャ〜
ウォレットアプリKyashの先 〜 Kyash Directのアーキテクチャ - Speaker Deck
Kyash でのアーキテクチャの話。
電子決済の話はメルペイのセッションでも聞いた。マイクロサービスを採用しているのは同じだったが、Kyash Direct の方は DDD を使って設計を行なっている。 マイクロサービスにしろ CQRS にしろ採用理由が明確になっているのが聞けたのでよかった。
HyperLogLog sketchは面白い
HyperLogLog is interesting - Speaker Deck
ビッグデータ界隈ではよく使われるらしいが、今回聞いた話では一番知らなかったことかも。
やりたいことは数え上げなのだが、統計的な処理を行うことで濃度 N のデータセットについて、濃度推定をO(1)でやってしまえる。 統計処理はたまに思っても観なかったことができるのですごい。
Elixir を支える技術 -「落ちない」システムの秘密に迫る
Elixir: Under the Hood - Speaker Deck
Elixir の話。 Elixir の基礎に加えて、最近の改良の話とかもあった。 最近はネイティブにコンパイルしたり、 JIT を入れようという動きもある様子。
スーパーカミオカンデの開発と運用
http://www-sk.icrr.u-tokyo.ac.jp/~hayato_s/20190831_Super-Kamiokande.pdf
スーパーカミオカンデの話。
前半がニュートリノなどの物理の話で、後半はスーパーカミオカンデを支えるソフトウェア・ハードウェアの話。 ソフトウェアではまだ Fortran を使っているとのこと。科学計算なら珍しいことではないか。
物理の話だったが、すごくよく噛み砕いて話していただいたので非常にわかりやすかった。
Peddle the Pedal to the Metal
Peddle the Pedal to the Metal (おそらく発表に使われたのと同じ資料)
C での高速化の話。今回の builderscon ではわりかし低レイヤーの話だった。
高速化のテクニックで紹介された主なものは:
- 文字列処理
- malloc 関連
- スレッド関連
など。最近 C は書いていないが、文字列処理周りは参考にできそう。
しかし C++ 嫌いという人は初めてみたな。
Oxygen Not Included: Making a Game That Inspires Science
資料は見つからず。
ゲーム「Oxygen Not Include」のデザインの話。 今回のセッションのなかでは一番変わっているかも。
今回の話を契機に積んでいたゲームに手を出してみたが、最初の部分から何をやったらいいかわからずに結局ゲームを積み直した。
その他
GMOさんがやっていたビルコン川柳で最優秀賞をいただいた。商品は Amazon ギフトカードで、ちょうど Kindle の IT 本セールがやっているのでこれに使わせてもらう予定。ありがとうございました!