Signte ひろしまQuest2020#stayhome参加記
# ひろしまQuest2020#stayhomeというコンペに参加しました。
情報公開ポリシーからモデルや分析結果に関しては書けないので、コンペサイトから読み取れる範囲の内容でお気持ち程度に、今更ながらちょっと感想書きたいなと思ったので書きました。
## SIGNATEとは
SIGNATEという恐らく日本では最大手のデータ分析コンペを開催しているサイトです。
今回はタスクとして、各ピッチから球種かコースを予測するというタスクのテーブルデータコンペで、外部データも利用化という色々できそうな楽しいコンペでした。(実際できたと思います。成果発表会が9月上旬に開かれる予定となっているので、上位の解法について聞くのが楽しみです。)
## 自身の結果については以下のとおりです。
| コンペティション名 | 戦績 | 備考 |
|---|---|---|
| ひろしまQuest2020#stayhome【コース予測部門】 | 41 位 / 258人投稿 | 銀メダル |
| ひろしまQuest2020#stayhome【球種予測部門】 | 141 位 / 481人投稿 | 60%Line以上 |
## コンペでの感想について
初めて参加したコンペでした。
初参加で銀メダルを獲得できたのはすごく嬉しく思っていますが、初参加故に計算時間の見積もりやログの取り方のノウハウ的な面で試行錯誤が必要だった、コンペ終了間際はサイトが重くなるなどの予想が甘かった、学習が間に合わなかったため最終サブに本当に提出したかったモデルを提出できなかったなどなどなどがすごく心残りです。(コンペ終了1時間後に僕の考えた最強のモデルの学習が終わりました笑)
コンペ終了後のサブミットができないため結果がどうなるかは神のみぞ知るですが、もっといい結果が出てたのではないかとCVの結果から見ても思います。
初めてでも参加しやすいテーブルデータで初参加者的な目線からもかなり良かったと思います。
ただ一つ言うなら、時系列データのコンペはタスクとしてそもそもあまりよくないかもしれないですね。
今回は目的変数を説明変数に与えるような運用はできないと言う制約があったのですが、次に何が投げられるか予測するのにまず使いたい情報は前何を投げたかだよなーと何度も唸りました。(ついでに言うとそれに近い特徴量を何度も作っては、「あ、これ使えないじゃん」を繰り返しました。(間抜けか？))
実際考えてみてください。そうですよね？
実務上もそうだと思います。前は内角高めに速い球を投げてきたから、今度は外角低めに遅い球を投げるとか。(野球は詳しく知らないので実際の戦略は知らないのでここら辺は適当な予想ですが)まあ、コンペという形式だとここら辺仕方ないんでしょうね。
もう一つの反省点として、全くデータ分析についてのノウハウのない人を半ば無理やり、チームにひき込んだのですが、自分のタスクをやるのにいっぱいいっぱいで、何もわからなくて暗闇の中困ってるはずなのにあんまりフォローできなくて、結果としてただ時間を奪ってしまっただけになってしまったり、プレッシャーを与えてしまったりといった非常に申し訳ないことをしてしまったという気持ちはあります。少しでも何か学ぶところが彼にあったら幸いなのですが...
チームを組むならもう少し情報共有やコードの共有方法について考える必要がありそうです。
Githubだとあげれるデータ量に上限があって(確か1ファイル100MBまで)、データ分析のタスクだと、特徴量が100MB超えることもままあると思うので、ここらへん他のチームはどう解決しているのか少し気になるところではあります。教えてください。
Import Error: 'scipy.misc import imsave' on Google Colaboratory
macOSでのprophetのインストールに苦労したので解決法のメモ
# macOSでのprophetのインストールに苦労したので解決法のメモ
prophetという時系列予測に使われるFacebookが作ったライブラリがある。
これを使いたくてインストールを半年前とかにも何度も試していたのだが、これがどうしてなかなかうまくいかず毎回諦めて困っていた。
やっと解決したのだがいろいろ試してどれが結果的にきいたのかよくわからんので試したことを全部書いていく。
環境は
macOS Mojave ->(途中でアプデート) -> macOS Catalina
Python 3.6.4
# try:1
まずprophetのインストール方法として
pip install fbprophet
を行えば良いと書いてある。
github.com
しかしこれを行っても一向にインストールができない。(1敗目)
いろいろ試して、アプデとかで再起している間にエラー出力が消えてしまって申し訳ないが、どうもC++のコンパイル回りでうまくいっていっておらず、そのため依存関係のpystanの実行がうまくいかないらしいとエラー出力から判断した。
ここをどうにかできれば良さそうだ。
# try:2
エラー出力を読むとどうもpystanでC++のコンパイルがうまくいっていないらしい。
調べてみると、pystanのインストールが見かけ上うまくいってもC++コンパイラとのフックがうまくいかないという問題があるらしい。これを解決できればうまくいきそうだ。
Fail to install fbprophet:INFO:pystan:COMPILING THE C++ CODE FOR MODEL anon_model_861b75c6337e237650a61ae58c4385ef NOW. error: command 'gcc' failed with exit status · Issue #1057 · facebook/prophet · GitHub
このissueによるとpystanをダウングレードしてみてくれと書いてある。試してみたが失敗した。(２敗目)
# try:3
pystanでC++のコンパイルが本当にうまくいかないのか確かめるために、試しにpystanを使うテストコードを適当にコピペしてきて動かしてみた。確かに動かないことがわかった。なるほどね。
例によって失われたエラー出力から、gccのコマンドがうまくいかないというエラー出力が出ていた。
そういえば上のissueでも gcc-g++をインストールしてくれと書いてある。
いろいろ調べてみると、macOSでは、gccを使っているつもりが裏でclangが動いているらしい。C++では、メジャーなコンパイラにgccとclangがあって、細かいとこでの挙動が違うらしい。これは競プロで知った。うーん、ここが問題点なのか？？？
Xcodeのgccでコンパイルしているつもりで実はclangでコンパイルしていた事実を今更知りました - Qiita
ということで、
Macのgcc, g++をHomebrewを使って最新版にする - Qiita
これを参考にgccをインストールしてパスを通してみる。
これでどうやらちゃんとgccが動くようになったぽい。張り切ってpystanをインストールし直して、prophetをインストールしようとする。失敗(3敗目)
# try:4
なんかもうどうしたらいいかよくわからん。
そうだ！ macではc++コンパイラをどうこうするときにxcodeが絡んできたりする。
Can not install fbprophet on MacOS Mojave · Issue #643 · stan-dev/pystan · GitHub
こんなissueも見つけた。
大雑把に言って、C++のヘッダファイルがMojaveだと足りないのでxcodeをインストールして
xcode-select --install
しろ、という話だ。
この機会にxcodeもアプデしておくか...ということでxcodeを最新版にしようとしたら、xcodeアプデにはosのアプデが必要らしい。
...いいじゃねーか、この機会にosもアプデしてやるよ。ということでやたら遅い回線速度に泣かされながら、夜中ずっと通してCatalinaにアプデした。
起きてもアプデが終わってなくて泣いた。なぜかappstoreとかosとかmac関係のものとなると、やたら家のwifiのダウンロード速度が遅い、どういうことなの？
osアプデの次はxcodeのアプデ、しかしなぜか8GBのダウンロードに1日かかった。は？
xcodeのアプデも終わり、pystanのインストールからやり直した。ダメだった(4敗目)
# try:5
エラー出力を見ていると
今度はclang回りでおかしいらしい。どういうことなの。
error: command '/usr/bin/clang' failed with exit status 1 · Issue #115 · TokenMarketNet/smart-contracts · GitHub
ここを読むとopenssl周りの問題の可能性が示唆されていた。
そういえばopenssl周りで悩んだことが以前あったな...(遠い目)
メモが残されていないので、何したかは詳しく覚えていないがインストールしたり、パス通したりいろいろ面倒だった思い出ががが。...openssl周りの問題はすでに解決できていると考えたい。
そう考えながら、もう少し下を見てみると
So, you need to do this: env LDFLAGS="-L$(brew --prefix openssl)/lib" CFLAGS="-I$(brew --prefix openssl)/include" pip install -r requirements.txt
と書いてある。
これを試してインストールし直してみたら、なんとうまくいった。やったーーー！！！ ということで勝利
# 結論
prophetをインストールするために、
queue.Queueよりcollections.deque方が速いbfs書けますよというお話[AtCoder]
初めに
まず、キューとは何でしょうか？
有名なデータ構造として、キュー、そしてスタックというものがあります。
細かい点に関しては検索してもらうとして、キューは先に入れたデータを先に取り出す、先入れ先出しのFIFO(First In First Out)でデータを格納し、スタックは先に入れたデータを後に取り出す、先入れ後出しのLIFO(Last In First Out)でデータを格納するデータ構造となっています。
僕はキューは店の行列、スタックは山積みの本のイメージで覚えています。
このスタックキューは、競プロでは幅優先探索(BFS)や深さ優先探索(DFS)でおなじみです。
さて、Python ではスタックキューとして、queue.Queue(以下queue)とcollections.deque(以下dequqe)を使うことができます。
僕はqueueの方をよく使っていたのですがdequeの方が速かったので記事にしてみました。
実験
早速実行速度を確かめてみましょう。
from queue import Queue q=Queue() for i in range(10**6): q.put(i)
from collections import deque q=deque() for i in range(10**6): q.append(i)
この両方をAtCoderのコードテスト上で実行すると
| 実行時間(ms) | メモリ(KB) | |
| queue | 2314 | 46284 |
| deque | 160 | 45724 |
単純な末尾挿入でも実行時間にだいぶ差が出てしまうことがわかります。競技プログラミングにおいてはqueueは基本的に避けた方がよさそうです。
(queueが全く使えないかというとそうではなくて、マルチスレッドではqueueに分があるようです。詳しくは知らない)
という事で検証終わり！w
......なのですが、そもそもなぜdequeは速いのでしょうか...？
dequeとリスト
Pythonにはリストというものがあります。いわゆる配列みたいなやつです。(厳密には配列ではない)
このリスト、末尾に挿入するのは速いのですが、実は末尾以外に挿入しようとすると激遅です。末尾に挿入と先頭に挿入で速度を比べてみましょう。
ls=[] for i in range(10**6): ls.append(i)
ls=[] for i in range(10**6): ls.insert(0,i)
| 実行時間(ms) | メモリ(KB) | |
| append | 140 | 45080 |
| insert | 10504 | 12528 |
挿入だけでこんなに時間を食っているとお話になりませんね。
プログラミングをやっていると当然末尾以外に挿入したいときは出てきます。その時はどうすればいいのでしょうか
感のいい人なら気づいているかもしれませんが、そういうときに用いるのがdequeです。
定義見ながら書き下していくのもアレ(面倒)なのでドキュメントを引用します。
deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。
list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。
collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント
つまるところ、先頭に挿入するのが速いという事です。
from collections import deque q=deque() for i in range(10**6): q.appendleft(i)
| 実行時間(ms) | メモリ(KB) | |
| appendleft | 145 | 45740 |
appendleft()は先頭に要素を追加します。リストと比べてかなり高速にできるのがわかります。そういったわけで、スタックとキューを実装する際にもdequeを使用すると実行時間が短くて済むわけですね。
dequeすごい！
じゃあ、全部dequeでよくね？
といった気持ちがわいてきますがdequeでは、末尾と先頭以外に操作を加えようとするとむしろ遅くなるようです。残念。
AtCoder茶になった
はい。
タイトル通りAtcoderで茶になりました。
正直なところ茶になっただけで喜々としてブログ書いてもあまり書くことないなという気はしなくもないんですが、自分も他の近い実力の人の変色した記事見て結構モチベーションにつながってたので書かないのもなあという気もして書いてみました。
取りあえずやったこととかテンプレ書いてあとはABCとかレート感に思う事を書いていきたいかなと思います。
やったこと
ABCのAB全埋め
正直全部埋める必要は全くないですがモチベーションにつながるので割と悪くない気がします。
ABCのCくらいのレベル感の問題埋め
ABCのC問題半分くらい埋めていくとコンテスト中にCを解けるようになる気がします。
後でも書きますが、今は茶になるにはCをコンテスト中に10回中5回以上くらいの安定感で埋めれるようにならないと厳しい気がします。
やったアルゴリズム
bit全探索
幅優先探索・深さ優先探索
二分探索
ユークリッドの互除法とか公倍数・公約数とかの整数系のアルゴリズム
こんなもんかな、動的計画法はなんとなく苦手意識あってあまりやってません。
茶ぐらいのレベルなら、アルゴリズムうんぬんより数列の扱い方に慣れた方が良い気がする。
割と公倍数・公約数を使う問題が多い気がするのでここらに慣れとくとやりやすそう。
逆に幅優先探索・深さ優先探索は正直あまり問題としてはでない気がする。まあ再帰とかキュー使う練習にはなるので。
整数系の問題と組み合わせ・確率系の問題、三角形がうんちゃらみたいな問題が多い気がするのでそこらへん解けるように、高校時代の参考書、読もう。はい。
雑談
雑談です。
上にも書きましたが最近のAtCoderは茶になるのも以前より大変だと思います。
昔のブログを見るとAB早解きできれば茶にはなれるみたいに書かれていますが、今はC解いても灰パフォなことがあります。そうはいってもめっちゃ解くの遅かったりペナ出しまくった時ではありますが。
何はともあれ少なくとも本番中に簡単なCは解けるようにならないと茶になることを短期的目標にするのは難しくなります。
純粋な疑問なんですが最近のABCの難易度ってAtCoder側としてはどう思ってるんでしょうね？
どんどん易化していってCD問題に灰から水くらいまで一緒くたにぶち込まれている感じが初級者としては結構きついです。最近のABC143のCはB問題レベル（実際似た問題がBである）でコンテスト参加者がほぼ全員解いてますし、全員が解いてると早解きで頑張るしかないのが結構厳しい。反対にEFを解いてる人は少ないっていう二極化が進んでる感じがあります。AtCoder Beginner Contestという名前ではありますが、実際は初心者がC～Dで戦って中級者以上がE~Fで戦っているような状況です。（ABはだれでも解ける） もう少し難易度のバランスがうまいことならないかなあとユーザー目線で勝手なことを言ってみたり。人数が増えてるのも結構影響大きいんでしょうね。理想を言えばARCがたくさん開催されることなんでしょうが、ARCは問題作るのも大変そうですし、なかなか難しそう。
ともかく別に文句を言いたいわけではなくて今の茶～緑辺りになるのは昔よりも難しいと思うし、なかなか思うようなレートになれなくてもあまり気を落とす必要はないんじゃないかなと、自分を慰めつつ茶になれた自分を自画自賛したかっただけです。
よーしもっと強くなるぞーー！おー！！
Pythonでの文字とアスキーコードの変換
pythonでは文字に対する計算はできない。
基本計算する必要もないと思うのだけれど、文字をシフト値に応じて変換したかったり、何番目のアルファベットかという事を知りたかったりという事もたまにある。
そんな時はord()関数を使うと文字をアスキーコードに変換、chr()関数を使うとアスキーコードを文字に変換できる。ord()は長さ一文字の文字列しか扱えない。
例：
print(chr(ord('a')+2))c
ちなみにord()は長さ一文字の文字列しか扱えないので、こんな感じの関数を用意しておいても便利かもしれない。
def shiftchr(str,shift):
s=''.join([chr(ord(t)+shift) for t in str])
return s
s=shiftchr('abc',1)
print(s)bcd
(…そもそも探せば便利な関数ありそう)
ord()を使った問題。
atcoder.jp
おまけ、アルファベットの列挙。
chars=[chr(ord('a')+i) for i in range(26)]
AtCoderでPython使うときの小ネタ
はい。
AtcoderでPython使うときに小技、というか小さな注意点が必要になるときがあります。いちいち探すの地味に面倒なのでどこかにまとめておきたいと思ったのでちょいと書いてみます。思いつくたびに、更新して増やしていきたいと考えているんですけど、はてなブログで記事を後から更新しても見にくかったりするんですかね？
1. 入力が多いとき
入力の行がめちゃくちゃ多くなりそうなとき、Pythonデフォルトのinput()は実は結構遅い。入力だけでTLE出るときがごくまれにある。
import sys input = sys.stdin.readline
を書いておくことで、高速に入力を受け取れる。
実行時間の差についてはこちらの記事が勉強になる。
www.kumilog.net
注意点として、この方法で入力を受け取ると末尾の改行の有無でちょっと処理が必要になる可能性がある。
2. 有効数字
ABC139Dの苦い思い出
n=int(input()) print(int((n-1)*n//2))
これが通って
n=int(input()) print(int((n-1)*n/2))
が通らないでWAの悲しみを味わった人も何人かいるはず。
/ だと演算結果がfloatになって有効数字が10何桁しか保たない。完全に整数になる、したいときは//を使っておきたい。
/2を採用すると、double演算になっちゃって、doubleになった瞬間、有効桁数が64bitではなくなるので、精度が悪くなります＞＜https://t.co/g2HC9d5q9i
— chokudai(高橋 直大)🍆🍡 (@chokudai) 2019年9月1日
3. 配列のコピー
Atcoderに限らないけど、Pythonのリストコピーで配列の参照オブジェクトが同じってよくあるアレ。dfsやるときに、すでに通った場所のメモ用の配列を
reached=[[0]*w]*h
で定義して、はまったことがあるので一応メモ
reached=[[0]*w for _ in range(h)]
みたいな感じで定義しよう。
4.itertools
競プロやる上でめちゃくちゃ便利なライブラリ。便利過ぎてまだ全容を把握していない。この記事を参考にしよう。
qiita.com
5.fractions
最大公約数・最小公倍数を求めるときなど、gcdを使いたいときがある。バージョン3.5以降はmathにあるのだがAtcoderではpython3.4.3なので2019/9/29現在、mathは使えない。fractionsモジュールを使おう。これでWA出すと何とも言えない気持ちになる。
6. 再帰の回数
Pythonでの再帰のデフォで回せる最高数は結構少なめなので増やす。
import sys sys.setrecursionlimit(4100000)
7. for文でelse
他の人の提出コード見ててびっくりしたんだけど、PythonではWhile、forのループにelseを使えるらしい。コレほかの言語ではあまり見ない機能ですよね。
パッと思いつく便利な使い方は、ループの処理でbreakしたときにフラグ変数を使わなくてすむ。
ary=[False,False,True,False]
flag=False
for a in ary:
if a==True:
flag=True
break
if flag:
print('yes')
else:
print('no')と書いていたところを
ary=[False,False,True,False]
for a in ary:
if a==True:
print('yes')
break
else:
print('no')と書ける。スマートでいいですね。
使用例:
atcoder.jp
ただほかの言語だと見かけないので、そういう意味ではあまり多用しない方が良いのかもしれない。まだあまり使ってないけど for、if が入り乱れるとめんどくさそう感はある。
それにパッとググってもあまり使うなと書いてるものを結構見かける。
......いやーでもこれ、めっちゃスマートでいいぞ。競プロに関してはどんどん使っていきたい。
