午後から→オーバークロック

駆け出しハッカー()によるプログラミング・サービス開発備忘録。

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>

f:id:nemupm:20151204153114p:plain

CSSファイルについて

github.com

上記 CSSをお借りしました。 mime typeの関係でrawgithub.comを使っています。

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に変えましょう。

参考

https://tug.org/mactex/UpdatingForElCapitan.pdf

ISUCON予選を学生枠でギリギリ通過する技術

友人に書けと言われたので書きます。

僕(nemupm)は今回ISUCON5に、shiki,itkqと一緒にアジ・タコ・エンガワ!というチーム名で参加しました。
(チーム名は各々の好きな寿司ネタです。もちろん僕はエンガワ派です。)
結果、6566点で学生枠5位という滑り込み通過で、奇跡的に本戦に出場できることになりました。

実は僕は去年もshikiと二人で参加したのですが、予選であえなく惨敗したので、取り敢えずリベンジ出来て嬉しいです。
今回僕はインフラ側(アプリ以外)を任されていたので、準備したことおよび本番で行ったことなどをつらつら書こうと思います。

準備

去年ISUCONに出場してみて感じたことは、

  • チューニング手法について知識が足りなさすぎた
    • チューニングと聞いても、SQLの改善とかデータをオンメモリにするとかそういうことしか思い浮かばなかった
  • ボトルネックの分析が雑
  • 準備8割

ということでした。
そのため、最低限準備として以下のタスクはこなそうと考えました。

  • どんな問題に対しても使える一般的なチューニング手法は可能な範囲で網羅する
  • アクセスログ、スロークエリの分析はすぐ行えるようにする

そして、先人たちのブログを読みながらチームメンバーでISUCON4の予選問題を解きました。
結果わかったのは、

  • チューニング手法だと
    • カーネルチューニング大事そう
    • unix domain socket
    • my.cnfのチューニング
    • innodb_buffer_pool_sizeとか
    • nginxのチューニング
    • nginxでの静的ファイルの配信
    • nginxでSSI
  • my.cnfには読み込み順序とかあるらしいぞ、気をつけろ
  • ps auxして怪しいプロセスないか確かめろ
  • kataribeさんつよい
  • pt-query-digestさんもつよい
  • top!dstat!iostat!

ということでした。
あとはこれらをgithubwikiにまとめて本番を迎えました。

本番

僕の想定が完全に甘かったのですが、
サービスが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つに分けて考える。
    • 12345を321(123を逆順にしたもの)と45に分ける。
    • 前半:10000->10321を数え上げる。321-0+1=321。この後10321をreverseして12301を得る。
    • 後半:12301->12345を数え上げる。45-1+1=45。
    • よって、10000->12345を数え上げると321+45=366。
  • 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では言及されてないので大変そう。

参考

イヤホンが断線したので半田こて買って修理してみた

f:id:nemupm:20150211172334j:plain

イヤホンが聴こえなくなり、修理に出そうかと思ったのですが、
3000円くらい掛かるのと、半田こてに興味があったので、
半田こてセットを買ってD.I.Y.してみました。

準備

  • 半田こてセット
    • 最悪こてと半田があれば問題無いです

goot 電子工作用はんだこてセット X-2000E

goot 電子工作用はんだこてセット X-2000E

  • はさみ
  • ライター
  • イヤホン
  • 交換用ミニプラグ

作業

半田付けまで

  1. イヤホンの先をはさみで切り、さらに数cm分ケーブルのみをはさみで上手く取り除きます。
  2. ミニプラグのカバーを先にケーブルに通します。
  3. 赤・青・金の3本の線があるので、先をこねて解きます。
  4. 線の先をライターで炙って被覆を取り除きます。
  5. ミニプラグを音楽プレーヤーに挿して、音楽を流した状態にします。
  6. 3本の線をミニプラグに当ててみて、イヤホンが聴こえるかどうかを試します。
    • 3本の線がミニプラグのどの場所に対応するかは場合によって異なるらしいですが、自分は左(青)、右(赤)、中央(金)でした。
    • この時、線を当てる場所や角度が多少ずれても聴こえる状態でないと、完成した時ちょっとの衝撃で聴こえなくなる可能性があります。

f:id:nemupm:20150211173536j:plain

半田付け

  1. 線をミニプラグの穴に内側から通し、すぐ溶接できる状態まで安定させます。
    • ここはめちゃくちゃ苦労しました。中央を最後に通すと比較的やりやすかったです。
  2. 半田こてを温めます。台に置いておきましょう。
  3. (上の半田こてセットであれば)バネ状になっている半田の先5cmくらいを解きます。
  4. いよいよ溶接です。順番としては
    1. 半田こてを溶接箇所に先に当て
    2. 半田を当てて溶かし
    3. 十分溶かしたら半田を離し
    4. 半田こてを最後に離します。
  5. 3つ全部溶接し終わったらカバーを付けて完成です。

f:id:nemupm:20150211175532j:plain

感想

  • 面白い
  • 十分聴こえる状態まで回復
  • 机拭こう

参考