Fisher-Yates shuffleを使ってシャッフルライブラリ作ってみました。 https://github.com/shogo82148/go-shuffle 標準ライブラリのsortと似たような感じで使えます。 デフォルトでintとfloat64とstringのシャッフルに対応していて、 他の型をシャッフルしたい場合はインターフェースを実装してね、って感じです。 実装が簡単なので、インターフェース定義する手間とシャッフルのアルゴリズム自前で書く手間ほとんど一緒ではという気もするけど、 まあライブラリ作成の練習ってことで。 で、ここからが本題。 Fisher-Yates shuffleの名前は以前から知ってたけど、 この前某プロジェクトで以下のようなshuffleの実装を発見。 package main import "math/rand" func shuffle(a []int) { for i := range a { j := rand.Intn(i + 1) a[i], a[j] = a[j], a[i] } } Fisher-Yates shuffleと似ているけど、なにかが違う。 ちゃんとシャッフルされているのか気になったので検証してみました。 検証 n個の数列をシャッフルすることを考えます。 シャッフルの後i番目の要素がj番目に移動する確率を $P_n(i, j)$ と定義します(golangのコードにあわせて0-originで考えます)。 完全にランダムにシャッフルされていれば、 元の数列のどの要素も0からn-1の範囲に一様分布するはずです。 つまり、以下の式がなりたてば「シャッフルされている」と言えそうです。 $$ P_n(i, j) = \frac{1}{n}　(i, j = 0, \dots, n - 1) $$ n=1の場合 n=1の場合は、必ず0番目と0番目の入れ替え(つまり順番変わらない)になります。 上で定義した確率を計算すると$P_1(0, 0) = 1/1$となるので、シャッフルされていると言えます。

木曜日の社内ISUCONにチームぽわわ3.5として参加してきました。 (今年のISUCON本番に4にアップデート予定) さきに結果だけ書いておくと、 1位はfujiwaraさんとacidlemonさんのチーム、 2位はチームぽわわ3.5、 3位はぴっぴ先輩率いるチーム例の青い紐でした。 オムライスと紐を倒したので僕は満足です。 簡単にやったことを書いておきます。 課題内容 Twitterみたいな短文投稿サイトです。 トップページにアクセスすると全ユーザの発言最新100件がみれて、 ログインすると発言したり自分の投稿履歴を確認したりできます。 僕が新卒で入ってきたときはPerlでしたが、今年の参考実装はGolang製です。 (Rubyもあったらしいけど使った人いたのかな) やったこと 僕自身は、相方になったたいがさんに「こんなことしてみては〜」と言ってみる係をやってました。 具体的な対応としては以下の通りです。 nginxにレスポンス吐かせる Nginxのレスポンスタイムをパーセンタイル値で計測するMunin plugin とかを参考にしてもらって、レスポンスタイムを吐くようにしてもらいました。 ログをテキトウスクリプトで集計したとろこ、トップページの全ユーザの発言最新100件みれるページが重いみたい。 高速化の第一ターゲットをトップページにしぼりました。 MySQLにSlowQuery吐かせる トップページが重いっぽいというのはわかったものの、 どのクエリが重いかまでは分からない(もちろんコード読んでたので検討はついてたけど)ので、 処理に0.1秒以上かかっているクエリを吐くようにしました。 インデックスの追加 既存のコードに触れずにお手軽ってことで、まずはDBにインデックスを張るところから。 workload10で、99583から101033にスコアアップ！ まあ、他のボトルネックを潰していない段階だとこんなもんでしょうね・・・。 ループクエリ・無駄クエリの削除 明らかに無駄クエリっぽいところがあったのでそこを修正しました。 投稿100件取得したあとに、100回ユーザ名の取得処理をしている JOINを使って書き換えました 実行計画が狂って逆に遅くなるという事態に陥ったので、IGNORE INDEXとかして頑張った ユーザの投稿を全取得してるのに、最新1件の情報しか使ってないところ LIMITをつけて制限 全投稿をCOUNTしているところ せっかくGolang使ってるんだから楽しようと、グローバル変数に突っ込んでcount++してみた 「グローバル変数に突っ込んでみた」対策みたいに、下手にアプリサーバで情報を保持すると DBとアプリサーバに差ができてしまうので、実運用では避けるべきテクニックですね。 あとになって考えると、ベンチ回す前にアプリサーバの再起動忘れてたのにベンチ通ってたので、 投稿数数えなくてもよかったのでは・・・。 nginxによる静的ファイルの配信 cssとかjsをGolangでかえしていたので、nginxで返すようにしました。 これで724338から802905(workload:100)にScoreアップ！ 画像の縮小 Twitterらしく投稿には100x100程度のサイズのアイコンが表示されるんですが、 元画像が1000x1000程度だったので縮小しました。 ただ、ベンチが画像にアクセスしにこないので、まったくの効果なし。 最終計測では結局元画像に戻しました。 実運用では確かに効果があると思うんですが、まずはログを見て判断しろという教訓ですね。 まとめ あとはworkloadの調整とかやって最終スコアは935519でした。 2位にはなったものの、インデックス追加とかループクエリの削除とか最低限のことが何とか出来たって感じです。 もっと精進します。 tech kayac へのポストまだかな〜

Perlで特定の文字列の出現回数を調べたくなって、調べてみたメモ。 ググるとすぐに見つかった。 perlで指定文字列の出現回数を取得する(正規表現) 指定文字列の出現回数は正規表現を使って $count++ while($str =~ m/$pattern/g); もしくは $count = (() = $str =~ m/$pattern/g); が、一瞬何をやっているのか把握できない・・・。 こういう意味なのかなーって予想はしてみたけど、あってるか一応調査。 whileを使った方法 //g をスカラーコンテキストの中でマッチさせると、 前回マッチした場所を覚えておいてくれて、次のマッチでその場所から検索を再開してくれるらしい。 (Using regular expressions in Perl - perlretut) マッチした場所は pos で取得可能。 my $str = "hoge fuga foo bar"; while ($str =~ m/[a-z]+/g) { say pos $str; } whileを後置にして、ループの回数を数えるようにすれば、最初の方法になる。 ループを使わない方法 これが一番謎だった。 //g をリストコンテキストで評価すると、マッチした文字列がリストになって帰ってくるらしい。 (Quote-Like Operators - perlop) 複数の変数に一括して代入するときに ($foo, $bar) = (1, 2) みたいな書き方をするけど、 () = ... の部分はこれの代入先の変数が一個もないケース。 要するに「リストコンテキストで評価してね」という意味のイディオムみたい。 まとめると、以下のような処理を簡略化して一行にしたのがループを使わない方法みたいです。

オーバーロードの優先順位付けが少しおかしくて、 名前付き引数とオプション引数と一緒に使うと死ぬ場合があるというお話。 ぴーちんが昨日言ってたやつ。 いんたーねっつにも乗っけておく。 問題となるのは以下のようなコード。 class MainClass { void Foo (int fuga) { } void Foo (string hoge, int fuga = 10) { } void Bar() { Foo (fuga: 20); } } このコードは以下のような例外を吐いて死ぬ。 Internal compiler error. See the console log for more information. output was: Unhandled Exception: Mono.CSharp.InternalErrorException: Internal error at Mono.CSharp.MethodGroupExpr.IsApplicable (Mono.CSharp.ResolveContext ec, Mono.CSharp.Arguments& arguments, Int32 arg_count, System.Reflection.MethodBase& method, System.Boolean& params_expanded_form) [0x00000] in <filename unknown>:0 at Mono.CSharp.MethodGroupExpr.OverloadResolve (Mono.CSharp.ResolveContext ec, Mono.

いつもテスト実行でお世話になっているtravisさんがC#をサポートしていました。 以前から C#をサポートして欲しいという要望はあったのですが、 2014年12月あたりからついに使えるようになってたみたいです。 以前はC言語のフリをして、設定ファルで頑張ってmonoをインストールする必要があったのですが、 ## Travis CI Integration language: c install: - sudo apt-get install mono-devel mono-gmcs script: - xbuild hogehoge.sln 今はlanguageにcsharpを設定して、solutionを指定するだけです。 ## Travis CI Integration language: csharp solution: hogehoge.sln MiniMeggagePack もこちらの設定を使うようにしてみました。 nunitを使ってテストする場合は結局sudo apt-get install nunit-consoleする必要があるみたいですが、 複数バージョンのmonoでテストできたりしていい感じです。 ただ、ドキュメントにはmono2.10.8もサポートしているとあるのにmonoのインストールが404で失敗したり、 他のバージョンでも時たまmonoのインストールにコケたり、 3.8.0でnunitのテストが上手く動かなかったり、不安定な感じがしてます。 徐々に改善していくといいなー。 参考 Building a C#, F#, or Visual Basic Project

ExcelやGoogle Spreadsheetを使って作ったデータをプログラムに取り込むのにcsv形式が便利でよく使っているんですが、 gitで履歴管理をしてもdiffが見づらい・・・。 gitのdiffがかなり自由にカスタマイズできることを知ったので、いろいろいじってみたメモ。 例として、以下のようなcsvファイルを編集することを考えます。 id,name,param_a,param_b,param_c,param_d,param_e 101,hoge,314,159,265,358,979 102,fuga,271,828,182,845,904 一行目は列の見出しになっていて、プログラムからは列番号ではなくparam_dの様に指定する、 という作りになってます。 id: 101の行のparam_dの数値に変更が入った場合、普通のgitだと以下のようになります。 diff --git a/hogehoge.csv b/hogehoge.csv index c8dbd17..37f4ff5 100644 --- a/hogehoge.csv +++ b/hogehoge.csv @@ -1,3 +1,3 @@ id,name,param_a,param_b,param_c,param_d,param_e -101,hoge,314,159,265,358,979 +101,hoge,314,159,265,359,979 102,fuga,271,828,182,845,904 二行目に何か変更があったことはわかりますが、 param_d だとはすぐにはわかりませんね・・・ YAMLに変換して比較する バイナリファイルであっても差分が確認できるよう、 git-diffを実行する前に変換ツールを実行する機能があります。 拡張子がcsvのファイルに対してこの機能が働くように.gitattributesに以下の行を足します。 *.csv diff=csv .git/config に変換ツールの設定を追加します。 key: valueの形式になっていると見やすそうなので、変換先の形式にはyamlを選びました。 [diff "csv"] textconv = csv2yaml ここで指定しているcsv2yamlは自前で用意する必要があります。 インターネット上をさまよえば同名のツールはいくらでもありそうですが、今回は自分でgoを使って書きました。 csv2yaml.goをコンパイルしてパスの通る場所においておきましょう。 csv2yamlは自分のよく使うcsvのフォーマットにあわせて以下のようなカスタマイズをしてあります。 idという名前のキーを必ず最初にする それ以外のキーはアルファベット順にソートする この状態でgit diffを実行すると以下のようになります。 diff --git a/hogehoge.csv b/hogehoge.csv index c8dbd17..37f4ff5 100644 --- a/hogehoge.csv +++ b/hogehoge.csv @@ -3,7 +3,7 @@ param_a: "314" param_b: "159" param_c: "265" - param_d: "358" + param_d: "359" param_e: "979" - id: "102" name: fuga これなら param_d が変更されたとすぐに分かりますね。

git で管理しているリポジトリの各ブランチの中身をそれぞれ個別のディレクトリにエクスポートする を読んで、 git-archive を使うともう少しシンプルに書けるんじゃないかと思ってやってみた。 git branch | sed -e 's/^[\* ]*//g' | xargs -n1 -I% sh -c 'git archive --prefix=%/ % | tar x' .gitconfig とかでエイリアスを設定しておくといいんじゃないでしょうか 以上

Go言語でポインタを使うべきか使わないべきか問題。 「ケース・バイ・ケースなので、状況に応じて使い分けましょう！」という結論が出るのは目に見えているので、 具体例について検証してみた結果を書いておきます。 背景 他の人のコードレビューを見ていたら、 レビュアーが「コピーをしないで済むのでstructの受け渡しにはポインタ使ったほうがいいと思います！」とコメントしていて、 そうなのか？と思ったのですがあんまり自信がなかったので検証してみました。 コメントがついていたのは以下のようなコード。 package hoge import ( "strconv" ) type Hoge struct { A int B int C int } func NewHogeMapStruct() map[string]Hoge { m := make(map[string]Hoge) for i := 0; i < 10000; i++ { m[strconv.Itoa(i)] = Hoge{i, i, i} } return m } ポイントは以下の点です。 受け渡すstructはintが3つ程度の小さなもの mapに入れて返す benchmarkを使って検証する ポインタを使わない版と使う版を両方作ってベンチマークをとってみます。 package hoge import ( "strconv" ) type Hoge struct { A int B int C int } // ポインタ使わない版 func NewHogeMapStruct() map[string]Hoge { m := make(map[string]Hoge) for i := 0; i < 10000; i++ { m[strconv.

GithubのIRCフックがgollum(Wikiページの変更通知)をサポートしました。 最近ぴーちんさんがWikiの編集業に精を出していて、編集の度にIRCに「変更しました！」とポストしてました。 「自動で通知してくれるとうれしいよねー」と話していたら、ある秘密を教えてもらいました。 acidlemon: githubのwiki編集のIRC通知、ここに秘密が隠されています https://github.com/github/github-services/blob/master/lib/services/irc.rb acidlemon: Blameおして黄色い変なアイコンを調べれば何をすれば良いかわかるはず おや・・・何処かで見た黄色いアイコンが・・・ 真似してgithub-servicesにプルリクエストをだしてマージしてもらった。 で、さっき対応イベント一覧見てたらgollum増えてる！ マージのときのコメントで「a few days」と言われたので2,3日かかるのかな？と思ってたけど、24時間経たないうちに反映されたよ！ 早い！！ さっそくGithub::Hooks::Managerを使って設定しておきました。 「[project-name] shogo82148 edited wiki page hogehoge」みたいに編集されたページが通知されます。 便利！！！ SEE ALSO github-services github の irc hook に幾つかの event type が追加されました - @soh335 memo GithubのHookについてのまとめとソリューション - おそらくはそれさえも平凡な日々

先日「Gitで作業ディレクトリの変更を破棄したのに差分が出続けて困った話」と いうのを書きましたが、より強力な敵が現われました。 このときは文字コードが原因で git checkout -- <file> しても差分が残り続けるというもので、git add してコミットし直すことで回避出来ました。 しかし、今度の敵は git checkout -- <file> しても git add <file>しても差分が残り続けます。 なんだ・・・このボスを倒したら新たなラスボスが現れた感・・・ acidlemon先生の手助けにより事無きを得たのですが、 ちょっと不明な点もあったので、その点もあわせてメモを残しておきます。 症状 git checkout -- <file> しても、git add <file> しても、git reset --hard HEAD しても、 何をしても差分が出続ける・・・なんだこいつ・・・ $ git checkout -- AwesomeFeature $ git add . $ git status On branch master Changes not staged for commit: (use "git add <file>..." to update what will be committed) (use "git checkout -- <file>.