引っ越しました
以下のサイトに引っ越ししました。
HTML単体でMarkdownを表示させる
テンプレートファイル
marked.jsを使用。 以下のテキストを書き込んだhtmlを開けばすぐにマークダウンが見れます。
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <link href="https://rawgithub.com/jasonm23/markdown-css-themes/gh-pages/markdown7.css" rel="stylesheet"></link> </head> <body> <div id="container"> </div> <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.0.0-alpha1/jquery.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/marked/0.3.5/marked.min.js"></script> <script> var markdown = (function() {/* # First level header ## Second level header - あめんぼあかいな - あいうえお - **うきも**に`こえび`もおよいでる --- >かきのきくりのきかきくけこ */}).toString().match(/\/\*([^]*)\*\//)[1]; var md = marked(markdown); $("#container").append(md); </script> </body> </html>
CSSファイルについて
Pythonのstr.ljustが日本語だと左揃えにならないので日本語用メソッドを用意した
python（2.7.3）でfor文の中で複数項目を標準出力する場合がある。 例えば以下。
>>> for v in [["Column1","Column2"],["apple","1"],["programming","2"]]: ... print v[0],v[1] ... Column1 Column2 apple 1 programming 2
これだとcolumn1とcolumn2の内容が縦に並ばない（v[1]が左揃えに出力されない）ので困る。
これに抗ってタブ\tを使うときがある。
しかし今回の場合だと上手く表示されない。
>>> for v in [["Column1","Column2"],["apple","1"],["programming","2"]]: ... print v[0],"\t",v[1] ... Column1 Column2 apple 1 programming 2
そこでstr.ljustを使うと、指定した文字列長になるまで後ろを空白で埋めてくれる。
>>> for v in [["Column1","Column2"],["apple","1"],["programming","2"]]: ... print v[0].ljust(30),v[1] ... Column1 Column2 apple 1 programming 2
ここまではいいのだが、日本語が混じると上手く表示されない。
pythonは日本語1文字のlengthを3と認識するが、
出力される際の幅はTerminalだと日本語1文字と英数字2文字が等しいので、
このような現象が起きる。
>>> for v in [["Column1","Column2"],["りんご","1"],["プログラミング","2"]]: ... print v[0].ljust(30),v[1] ... Column1 Column2 りんご 1 プログラミング 2
そこで、以下のようなメソッドを用意する。
def ljust(string,length): count_length = 0 for char in string.decode('utf8'): if ord(char) <= 255: count_length += 1 else: count_length += 2 return string + (length-count_length) * ' '
>>> for v in [["Column1","Column2"],["りんご","1"],["プログラミング","2"]]: ... print ljust(v[0],30),v[1] ... Column1 Column2 りんご 1 プログラミング 2
正しく表示されてないorz、けどmacのTerminalのデフォルトフォントとかだと正しく表示されます。
OS X El CapitanへのLaTex環境のインストール
homebrewのcaskを使ってMacTex2015（include TexLive2015）を入れます。
インストール
brew install caskroom/cask/brew-cask brew cask install mactex echo "export PATH=/Library/TeX/texbin:$PATH" >> ~/.zshrc source ~/.zshrc sudo tlmgr update --self --all
bashを使っている人はbashrcに。
一応ミラーサイトによっては最新版になってない可能性があるので、
tlmgr info jfontmapsの結果が20151002以降であることを確かめる必要があります。
アプリケーションのPATHも/Library/TeX/texbinに変えましょう。
参考
ISUCON予選を学生枠でギリギリ通過する技術
友人に書けと言われたので書きます。
僕(nemupm)は今回ISUCON5に、shiki,itkqと一緒にアジ・タコ・エンガワ！というチーム名で参加しました。
（チーム名は各々の好きな寿司ネタです。もちろん僕はエンガワ派です。）
結果、6566点で学生枠5位という滑り込み通過で、奇跡的に本戦に出場できることになりました。
実は僕は去年もshikiと二人で参加したのですが、予選であえなく惨敗したので、取り敢えずリベンジ出来て嬉しいです。
今回僕はインフラ側（アプリ以外）を任されていたので、準備したことおよび本番で行ったことなどをつらつら書こうと思います。
準備
去年ISUCONに出場してみて感じたことは、
ということでした。
そのため、最低限準備として以下のタスクはこなそうと考えました。
- どんな問題に対しても使える一般的なチューニング手法は可能な範囲で網羅する
- アクセスログ、スロークエリの分析はすぐ行えるようにする
そして、先人たちのブログを読みながらチームメンバーでISUCON4の予選問題を解きました。
結果わかったのは、
- チューニング手法だと
- my.cnfには読み込み順序とかあるらしいぞ、気をつけろ
- ps auxして怪しいプロセスないか確かめろ
- kataribeさんつよい
- pt-query-digestさんもつよい
- top！dstat！iostat！
ということでした。
あとはこれらをgithubのwikiにまとめて本番を迎えました。
本番
僕の想定が完全に甘かったのですが、
サービスがsupervisordじゃなくてsystemdで管理されていて、
最初無駄な時間を食ってしまいました。（本当申し訳ない）
ここで他の二人がアプリのソースコードを読んでくれたところ、どうやらISUCON4予選の比じゃないくらいアプリが大きいようで、
事前に打ち合わせしていた策だとフレームワークを外す予定だったのですが、急遽予定を変更することにしました。
（訂正：あとで聞いたらそもそもフレームワーク使われていなかったというオチ）
その後なんとかアプリをGolangに変えて、Failするバグも直してベンチマークを走らせるとスコアが700くらい。
ここから、kataribe・pt-query-digest・topとかでボトルネックを調べながら作戦を立てていきました。
調べた結果、明らかにクエリがボトルネックだったので、アプリ側の二人が、relationsをオンメモリ実装することに決まり、 （Redisとかではなくて、DBのデータを初期化時にgoの変数に突っ込んで、SQLの処理を変数の処理に置き換える） その間はちまちまと準備した設定を反映させたりrelations以外のインデックスを作成したりしていました。
結果、700->1500くらいに。 （あんまりスコアを覚えていない）
途中my.cnf反映されない問題（結局かい）との格闘や、entries重すぎじゃね問題などで時間を食ってしまったため、
この時点で時間が半分は経ってた気がするので、ランキング上位陣がどんどんと点数を伸ばしているのを見ながら、
「全然スコア伸びねえじゃん。やべえよやべえよ、準備した策使い切っちゃったよ」と焦っていました。
ここで自分もソースコードを読んでクエリの書き換えなどができたら良かったのですが、
自分だけSkype参加だったこともあって他二人と密に連携を取れるわけではないため、
邪魔をしては本末転倒だということで、
オンメモリ実装が終わるまではMySQLのキャッシュの有効化とか圧縮テーブルの検討（結局やらなかった）とか
ちまちま設定を変えたりペヤングを食べたりしていました。
そんなこんなでいつの間にか17:30くらいになっていましたが、ついにオンメモリ実装が終わり、
その状態でベンチマークを走らせたところ、一気にスコアが7000台にアップ。
あまりに驚いたため思わずSkype越しに叫んでしまいました。
その後色々調整して、最終的にスロークエリログを見ても全て0.01s以下に収まっていたようなので、
SQLは大分改善されたかなという印象（もちろんクエリを書き換えたりしてもっと改善できるところは多々あったようですが）。
その後、再起動したらスコア下がる問題などでかなり焦りましたが
（innodb_buffer_pool_dump_at_shutdownとかOnにするべきだった？）
ベンチマークを繰り返してなんとか6566まで回復した時点で試合終了。
今回学生組が35組もいたこともあって予選通過は難しいかなーと思っていましたが、
本戦に行けることが判明してまたも驚き。
そんな感じで今に至ります。
反省
- アプリ側を他二人に任せすぎて、特に後半あんまり貢献できなかった
- gitも正直詳しくないから他二人に任せていた
- 後で他のチームがProfilerDrivenDevelopmentとかやってるのを知って、プロファイラとか本番前に使ってみたらよかったと思った
- SQLのこと知らなさすぎ
- そしてやっぱりボトルネックの把握が雑
今回は二人の実装のおかげでなんとか予選通過できたので、本戦こそは貢献したい！
（なおitkqとはSkypeでしか話したことがないので本戦で初顔合わせの予定）
Google Code Jam Round1B - Problem A. Counter Culture - in Python
Google Code JamのRound1Bで憤死（0完）しましたが悔しいので時間外でA,Bを解いてみる。
どうやらBは2パターンの市松模様を試せばそれで良いっぽいので、今回はAだけ書きました。
ProblemA. Counter Culture
full search
時間内ではいきなり最適解を出そうと頑張って、結局smallさえ通せなかったので、
とりあえず総当たりで解きます。
dp = [0 for i in xrange(1000001)] for i in xrange(1,1000001): if dp[i] == 0: dp[i] = dp[i-1] + 1 reverse = int(str(i)[::-1]) if dp[reverse] == 0: dp[reverse] = dp[i] + 1 else: if dp[i] > dp[i-1] + 1: dp[i] = dp[i-1] + 1 t = input() for _ in xrange(t): n = input() print "Case #%d: %d" % (_+1,dp[n])
総当たりといってもテストケース100個に対して毎回106を計算するのも微妙なので、
最初にDPテーブルを作ってから解きます。
optimize
時間内で解いた時に検討した解法は以下。
例えばInputが12345だとすれば、
- 1->12345をいきなり数えるのではなく、1->9,10->99,100->999,1000->9999,10000->12345に分けて考える。
- 10000->12345を解く時は前半と後半2つに分けて考える。
- 10->99,100->999,1000->9999についても同様にアプローチして、全てを合計すると解が求まる。（1->9だけは数え上げ）
この方針で解を出して、smallの出力とopendiffでdiffを取ってみると、
例えば990000の時にうまくいってないことがわかった。
確かに、100000->100099->990001->990000となり、reverseする前の手順で数えすぎなことがわかる。
仕方ないので、後半部分の数字が0の場合だけ、Input-1の答え+1を返すようにした。
（Inputが990000の場合は989999の答え+1）
最終的なコードは以下。
# return answer def answer(x): ans = 0 for i in xrange(1,len(str(x))+1): if i == len(str(x)): ans += count(10 ** (i-1),x) else: ans += count(10 ** (i-1),10 ** i - 1) return ans # return a number to change x to y(len(x) == len(y)) def count(x,y): leny = len(str(y)) if leny == 1: #print "x:%d,y:%d,ans:%d" % (x,y,y-x+1) return y - x + 1 # when y == 12345, front_half == 321 and back_half == 45 front_half = int(str(y)[::-1][leny/2:]) back_half = int(str(y)[(leny-leny/2):]) ans = 0 if back_half != 0: ans += front_half - int(str(x)[(leny/2):]) + 1 ans += back_half - int(str(x)[::-1][(leny-leny/2):]) + 1 else: return 1 + count(x,y-1) #print "x:%d,y:%d,f:%d,b:%d,ans:%d" % (x,y,front_half,back_half,min(ans,y-x+1)) return min(y-x+1,ans) t = input() for _ in xrange(t): n = input() #print "Input #%d: %d" % (_+1,n) print "Case #%d: %d" % (_+1,answer(n))
今回のケースで改めてsmallを先に解く戦法の重要性を知った。
（じゃないと990000などのうまくいかないケースを発見できなかったと思う）
Tシャツ欲しいので次がラストだけど頑張るしかない！！
今更OAuth1.0についてRFC読んで勉強してみた
OAuth1.0について発表する貴重な機会があったので、 RFCや色々な方のスライドなどを参考にさせていただき、まとめてみました。
補足
その他
- クライアントサイドがWebアプリの場合クライアントサーバ上にクライアントクレデンシャルが存在するので漏洩することはないが、モバイル・デスクトップアプリの場合はユーザの手元にクレデンシャルがあるので漏洩は避けられない。
- callback_urlはリクエストトークン取得時に任意に指定できるので、クライアントクレデンシャルが漏洩している場合、callback_urlを攻撃者のサーバのURLに指定することで攻撃者が検証コードを取得できてしまい、危険である。
CSRF攻撃（クロスサイトリクエストフォージェリ）
意図しないリクエストを発行させられることによって起こる攻撃。
インラインフレームを使うのが常套手段。
フィードバック
- Twitterは2010年頃まではBasic認証でAPIを利用させていた。まじですか。
- リクエストトークン取得プロセスは要るのか疑問だったが、実際にOAuth2.0では無くなっている。
- ただし、リクエストトークン自体は認可要求に対して承認をしたユーザと検証コードを送ってきたユーザが同一であることを見抜くために必要である。（参考URL）
- OAuth2.0ではリクエストトークンの代わりにstateが扱われている。
感想
OAuth1.0もクライアントサイドの実装は案外怖くない！ということがわかりました。
一方でサーバサイドはセキュリティ対策とかのベストプラクティスについてRFCでは言及されてないので大変そう。
