prime's diary

そすうの日々を垂れ流しちゃうやつだよ

RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい

ネタ 競技プログラミング

qiita.com

mattn.kaoriya.net

という記事を読んだのでアルゴリズムを改善して速くしました。

いわゆる行列累乗のテクニックを使うと（乗算部分を除けば）N番目のフィボナッチ数は{O(\log N)}で求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら{O(N^{1.585})}、高速フーリエ変換を使えば{O(N \log N)})。 単純な足し算のループでは足し算の桁数を考えると { O(N^{2}) } なのでそれよりは随分と速くなります。

40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。

こちらが元のソースコード

def fib(n)
  f0, f1, v = 0, 1, 0
  n.times do |x|
    if x <= 1
      v = x
    else
      v = f0 + f1
      f0, f1 = f1, v
    end
  end
  return f0 + f1
end

puts fib(1000000)

実行してみます。

$ ruby fib_naive.rb > /dev/null
ruby fib_naive.rb > /dev/null  9.63s user 0.87s system 100% cpu 10.499 total

行列累乗を用いたソースコード。行列を累乗するところで再帰を使っています。

def mat_mul(lhs, rhs)
  res = [[0,0],[0,0]]
  2.times {|i| 2.times {|j| 2.times {|k|
    res[i][j] += lhs[i][k] * rhs[k][j]
  }}}
  return res
end

def mat_pow(mat, index)
  if index == 1
    return mat
  else
    half = mat_pow(mat, index / 2)
    if (index % 2) == 0
      return mat_mul(half, half)
    else
      return mat_mul(half, mat_mul(half, mat))
    end
  end
end

def fib(n)
  return mat_pow([[1,1],[1,0]], n-1)[0][0]
end

puts fib(1000000)

$ ruby fib.rb > /dev/null
ruby fib.rb > /dev/null  0.10s user 0.01s system 97% cpu 0.106 total

さらに100倍ぐらい速くなりました！すごい！

【failに】ISUCON5の決勝に出たけど記録を残せなかった【人権はない】

ISUCON

お金が欲しいので（直球）、優勝賞金100万円のISUCONの決勝に出ました。予選については

primenumber.hatenadiary.jp

を参照。

当日起きれるか不安だったので前日入りしてカプセルホテルに泊まった。 人生初のカプセルホテルだったが、あまり寝られなかった。お腹の調子が悪かったのもあると思う。 少し早めに出てゆったり朝食を取って会場入りした。

コンテスト始まってとりあえず問題の内容を理解したりベンチ回してみたり実装を読んだりプロファイルを取ったりしたりしていた。 なぜかrack-lineprofがSEGVかなんかで落ちるのが辛かった。 とりあえず手元で実験して/dataが外部のAPIを叩くところが遅いことはわかって、どうにかしてキャッシュ出来ないかとか並列にリクエスト送れないかとかあれこれやっていた。 しかし、15時頃に一番遅いtenkiのAPIが単純にキャッシュしただけではダメになったので、八方塞がりになってしまって「なんか自分の知らないすごいからくりを使うとうまく行くみたいなやつでは」という気分になっていた。

結局15:30ぐらいまで全然わからず1000点ぐらいで止まっていたが、そこからどうせ殆どの時間外部からのレスポンスを待って暇しているのなら、すごい並列度を上げても捌けるのでは？ ということに気づいてnginxとunicornのworkerを20, 40とかに増やしてみたら8000点ぐらいに乗って、なるほどなぁと思ってそのあとworkerの数を微調整して、並列にリクエストを投げる（ただし、httpsのAPIを同じトークンのものを２つ同時に投げるとToo many connectionsとかで怒られるのでそこだけ同期を取って実行した)ようにしたりして13000点まで上がった。 「外部APIのレスポンスが遅い時は、並列度を上げてスループットを上げる」という戦略、私には自明ではなかったけど、多くの他のチームは早いうちから1万点を超えていたのでこういうことはWebサービスを作る人々にとっては自明なことで、この辺が経験の差なのだろうと思った。

この時点で1台しか使っていなかったので頑張って3台で動かそうとしていたけど何故かうまく行かず、最後もなんかうまく行かないかと試しながらやっていたら時間切れ、一度も成功していない3台に分散する方で提出したので当然failして0点だった。 学生賞は1位しか無いのでall or nothingの精神で賭けに出たが、結局全チームfailだったので「安全策で行っていればなぁ」と後悔が残るけど後から言っても仕方無い。

多くの知見を得られた、よいコンテストでした。運営の皆さん、お疲れ様でした。

ISUCON5の予選に出て学生枠1位で通過した(チーム名: 古典論理の犬)

ISUCON

お金が欲しいので（直球）、優勝賞金100万円のISUCONの予選に参加して、13609点、二日目全体で11位（？）学生枠1位で通過した（学生枠で登録した中では一般枠で通過したチーム学生自治についで2位）。

isucon.net

チーム

チーム名: 古典論理の犬

チームメンバー: @lastcat_ @nonylene @_primenumber

チーム名の由来

KMC内でISUCONに出るぞ！！ってなって6人集まったのでnotaで働いてる人(@nonamea774 @pastak @uiureo, チーム学生自治)とそうでない人でそれぞれチームを作った。 not notaなのでnot not a ⇒ aってなって二重否定の除去マンだ、古典論理の犬だ！！ってなって決まった。

流れ

予選まで

8月の末ぐらいからチームで何回か練習をした。

最初にISUCON1からやろうとしてAMIとかもないし流石に古すぎてそもそもアプリ起動まで辿りつけなかったので失敗。結局練習で物理的に集まれたのはこの一回だけだった。

反省を活かしてそれ以降はISUCON3/ISUCON4の予選問題を解いたり、各種テクニックを各自勉強したりしてた。

ISUCON4の予選問題を解いた時は実装をRubyからGoにしただけでかなりスコア上がったので、Goの勉強をしたり、GCPになれるためにGCP上で個人練習したりしながら予選本番を迎えた。

当日

予選二日目の方に参加した。一日目は開始が1時間遅れたりidobataが落ちたりして大変そうだったけど、二日目はそこまで大きな問題はなかった。 学生枠で出ることを考えると一日目と２日目を合わせた順位だけで本戦出場が決まるので、予選の日程によって参加者数とかが違うから有利不利がないし、1日多く練習出来たり運営の人たちが慣れたりして安定する二日目のほうが有利な気はする。

予選開始するとなんとGoの参考実装にバグがあるという話で、しかもコードを見ると800行弱もあって(Rubyだと400行弱)読む気を失ったので早々にRuby実装で行くことに決定。

前回の予選までと違って手元でベンチを回せない、チームあたりベンチキューに積めるのは１つまで、キューの消化が最初はかなり遅かったのもあり結構手間取る。 見た感じとにかく/が遅く、1クエリに2.5sかかってるSQLクエリとかあっておうおうみたいな感じ。 しかし、オンメモリにするにはあまりにも巨大だし、メモリもそんな無いし、真面目にクエリいい感じにしたいけどむずいなこれ…となってなかなかスコアが上がらない。

そうこうしてるうちに1時ぐらいになって、今のままだと絶望だし気分転換にみんなでコンビニ行くか、となって昼飯を書いにコンビニに行く。 ここで3人でいろいろ話して、全員で問題点や疑問点を共有したり出来たのは良かった。 もちろんそれ以前からクエリが遅いとか話してたけど、３人でちゃんと具体的にどういうクエリがどういう理由で遅いのか、今のところこういう解決策がありそう、とかをしっかり共有できたのが大きな前進だった。

いろいろ解決策はありそうだけど実装力がなくてなかなか進まず、16:30頃まではスコアが2000程度で絶望、って感じだったけど、そこからようやくfriendを取ってくるクエリとかも改善して、必要なところにインデックス貼ったりして3000点台→10000点台まで上がった。

その後は細かい調整をして11000点台になったあと、再起動試験をしてクエリキャッシュを有効にしたりカーネルパラメータをいじって13000点台になったところであと3分とかになって、まあ流石に学生枠ではいけるでしょ、お疲れ様でした、と言う感じになった。

その後はチーム学生自治、チームCAMPHOR-の人たちとお疲れ様でした打ち上げをした。

自分のやった作業

  • 都度スロークエリログを眺める
  • 自分の投稿へのコメントを取ってくるクエリはとりあえず自分の投稿のentry_id全部をサブクエリで取ってきてWHERE INで取ってくる実装に変更
  • footprintsのuser_id、relationsのone, anotherのそれぞれにインデックスを張った（oneに張る必要はなかった気がする、あとanotherは見なくてよかったというのを終わってから知った）
  • commentsのentry_id, created_atで複合インデックスを張ったけど効果があったかは不明
  • 「あなたの友達の日記エントリ」を取ってくる実装をfriend全部を取ってきたのを使いまわしてWHERE INの中に突っ込んで直接取ってこれるようにした
  • 「あなたの友達のコメント」のほうは自分に見れない記事へのコメントを弾くのをクエリに入れる方法を考える時間がなかったので、友達のコメント20件取ってきてそのうち自分の見れるものをRuby側で10件取ってくる場当たり的な実装になってしまった（もともとコメント1000件取ってきてRuby側で条件に合う10件取ってくるみたいなのだったので、同じようなもんだし妥協ということにした）

反省

  • 改善策が出てから実装できるまでにかなり時間がかかって、まともなスコアが出るのがかなり遅くなった
    • 実装力がまだまだ足りない、MySQLとかにももっと慣れないといけない
  • 結局Rubyでプロファイル取れてないので、改善すべき点がまだ結構残っている
  • 実はビューの方にもSQLクエリが書いてあったらしいけどビューとか全く見てなかった
  • 問題点とか疑問点はしっかりチームメンバーで共有すべき

感想

ボリュームがあるし面白い問題だった。 チームとしては結果として本選に行けたけど本選でまともに戦うにはまだまだ足りないのでちゃんと練習したい。 物理的に3人でホワイトボードのあるところに集まるとかなり捗ることがわかったので今後チーム練習するときはちゃんと物理的に集まって練習したい。

追記

本番で使ったリポジトリを公開しました。

github.com

mysqlの設定とかは置いてないです

gccでSIMD命令等のIntrinsicsを使う時のメモ

その他 コンピューターオセロ

やりたいこと

  • Intel Intrinsics Guideに載っている組み込み関数を使いたい
  • 具体的には今作っているオセロAIの高速化のため

調べた環境

使い方と注意

  • だいたいの(実際の実行環境で使用出来る)命令の組み込み関数は各関数で指定されたヘッダをincludeし、正しいコンパイルオプション(-march=native -mtune=nativeなど)を与えれば上手く行く
  • 一部の関数(_bswapなど)はx86intirin.hをincludeしないと使えない
    • x86intrin.hはコンパイルオプションに合わせて適切なヘッダを自動的にincludeするのでこれさえincludeしておけばOK
  • 更にごく一部の関数(_bittestなど)はそもそも使えない
  • /usr/lib/gcc/x86_64-unknown-linux-gnu/5.1.0/include以下を検索してなかったらなさそう

まとめ

  • #include <x86intrin.h>
  • それでダメだったらダメ
  • 間違い・環境依存等あるかも

AOJ 1351 Flipping Parentheses

ビット演算 競技プログラミング ネタ

問題文

ICPC Asia 2014 Tokyo G

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351

解法

想定解法と違うけど通ってしまった

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1174168#1

(を1、)を0とみなして01列として扱って、64bitまとめて操作する

各64bitごとに、予めdiffとdiffの下限(後述)を計算して持っておく。

ここで、diffとは1と0の数の差で次のようになる(例では16bit)

1 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1
diff 1 0 1 0 1 0 -1 -2 -1 -2 -1 -2 -1 0 -1 0
diffの下限 0 0 0 0 0 0 -1 -2 -2 -2 -2 -2 -2 -2 -2 -2

この場合はdiffは0、diffの下限は-2となる。

(を反転させるクエリでは、最初の)を反転させれば良いから、diffが64でない最初の場所から探せばよい。

)を反転させるクエリでは、配列の先頭から直前の要素までのdiffの合計+今見ている要素のinfが1以下になる最後の場所から探せばよい。

各クエリで変更されるのは高々2bitなので、高々2箇所についてdiffとdiffの下限を更新すればよい。

これで計算量が64分の1程度になって通る(平方分割に近そう)

計算量

O(NQ/(bit幅)+Q(bit幅))

本番は区間に加算、区間の最小値のSegmentTreeを書こうとして盛大にバグって解けなかったのに、こんなので通ってしまうとは…

Brainf*ck + リフレクション = BFmeta 【KMCアドベントカレンダー26日目】

難解プログラミング言語

おはようございます！！ KMC2回生のprimeです！！

この記事は今年もやります！KMCアドベントカレンダー！！ - KMC活動ブログの26日目の記事です。昨日の記事は、primeさんのお詫び 【KMCアドベントカレンダー25日目】 - KMC活動ブログでした。

はじめに

Brainf*ckというプログラミング言語をご存じでしょうか。ご存じの方はこの節を飛ばして「Brainf*ckでプログラミングする」に進んでいただいて構いません。
ご存知でない方に簡単に説明すると、Brainf*ckはなるべくコンパイラが小さくなるように設計されたプログラミング言語で、最低限の手続き型言語の機能を実装しており、わずか8命令だけ*1でプログラミングできるという、まさに手続き型言語のエッセンスを凝縮したプログラミング言語です。

Brainf*ckの言語仕様

プログラムは最初、0で初期化された無限長の配列*2が用意され、その先頭を指すポインタ(プログラム中に出てくることは無いですが、ここではptr呼ぶことにします)が用意されます。ポインタがわからない場合も、この場合は配列の添字だと思えばよいでしょう。

使用出来る命令

ソースコードの可読性が高まるように命令記号が選ばれています。

  • + : ポインタの指す値を1増やす。C言語の++(*ptr);に相当。
  • - : ポインタの指す値を1減らす。C言語の--(*ptr);に相当。
  • > : ポインタをインクリメントする(ひとつ進める)。C言語の++ptr;に相当。
  • < : ポインタをデクリメントする(ひとつ戻る)。C言語の--ptr;に相当。
  • [ : もしポインタの指す値が0なら、対応する]にジャンプする。C言語のwhile(*ptr){に相当。
  • ] : もしポインタの指す値が0でないなら対応する[にジャンプする。C言語の}に相当。
  • . : ポインタの指す値を文字として標準出力に出力する。C言語のputchar(*ptr);に相当。
  • , : 標準入力から1バイト読み込み、ポインタの指す場所に代入する。C言語の*ptr=getchar();に相当。

Hello worldは次のように書けます。

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.

Brainf*ckでプログラミングする

Brainf*ckには我々が普段使うような命令はほとんど用意されていないので実際にプログラムを書く際はちょっとした工夫が必要となります。
昨年私が作った資料がWeb上の資料では日本で一番詳しいんじゃないかと思います。（自画自賛）

Brainf*ckの問題点

実際にプログラムを書いてみるとわかると思いますが、Brainf*ckには関数がないので大規模なプログラムになるに連れ可読性が低下し、コード量が爆発的に増えてしまいます。
また、リテラル値をソースコード中に埋め込めないので、いちいち動的に生成しなければなりません。これはさらなるコードの増長とともに可読性の低下をもたらします。

既存のBrainf*ckの拡張・派生言語には主に2通りあります。

  • 命令記号の置き換え 可読性を上げる・下げるために命令記号を他の文字列に置き換える方法です。
    KQ Ook! ごちうさ
    挙げていくとキリがないし、Brainf*ckの命令を置換した言語を作るgemが存在しているので、詳しいことは省略しますが、どちらにせよ表現力は上がらないし可読性も大して上がりません。

  • 命令の拡充 表現力を増すために使える命令を増やす方法です。
    代表的なものとしてはBrainCrashがあります。
    私も以前Brainf*ck風言語Prime(ver 0.0.1)インタプリタ · GitHubというBrainf*ckに命令を追加した言語を作ったことがあります。
    BrainCrashではビット演算を行う4命令が追加されていますが、それでもまだまだ表現力は低いですし、Brainf*ckの持つ言語の美しさを損なってしまいます。

BFmetaという解決策

私はBrainf*ckのシンプルな言語仕様を損なうことなく、Brainf*ckに強い表現力を与えることを考えました。その結論がBFmetaです。

Brainf*ckからの変更点は2つだけ、「配列中にソースコードをマップし、命令の読み取りも配列から行う」、「プログラム終了条件は読み込んだ命令がヌル文字だったとき」です。

たったこれだけの変更ですが、これにより、プログラム実行中にプログラムを書き換える、リフレクションが可能になります。
また、プログラム中からソースコードの内容を参照できるので、文字列リテラルが簡単に使えるようになります。

しかも、Brainf*ckの特徴であるシンプルな命令体系と命令記号はそのままです。

詳しい言語仕様(といっても紙1枚に余裕で収まる程度ですが)はBFmetaのページを見てください。 処理系はhttps://github.com/primenumber/BFmetaから入手できます！

サンプル

Hello, World!

[>]<<<<<<<<<<<<<<[.[-]>]Hello, World!

Brainf*ckと比較すると相当短いコードになっていることがわかります。(このコードには最後に改行が必要です。ファイル末尾に自動的に挿入される改行に注意。)

Brainf*ckインタプリタ

[>],[>,]

Brainf*ckで実装するとこんなに長くなってしまうBrainf*ckインタプリタがなんと8バイトです！

実用的な例も見てみましょう。与えられた文字列中の指定した文字列を別の文字列に置き換えて、更にその結果生成された文字列をBFmetaのプログラムとして実行します！
（多少時間がかかります）

文字列置換により動的にコード生成を行うBFmetaプログラム

この例では、ソースコード中の一番最後の文字に囲まれた範囲で、最初の改行までの文字列(この場合はinc)を次の改行までの文字列(この場合は>)に置き換える、という事をその後の文字列全体(この場合は[inc]<<<<<<<<<<<<<<[.[-]inc]Hello, World!)に対し繰り返し適用します。 文字列置換部分は、http://www.slideshare.net/KMC_JP/brainfckで紹介したポインタ付き配列のイディオムを応用して実装されています。

文字列置換したプログラムの中でさらに文字列置換を行うネストもできます。しかし、2重にした時点で1時間半以上実行に時間がかかったので、実用するにはより高速な処理系が必要になるでしょう。

ソースコード置換を二重に掛けるテスト · GitHub

なんだかBFmetaでまともなプログラムが書ける気がして来ませんか？してきましたね！ぜひどんどんかっこいいBFmetaプログラムを書いて@_primenumberに送りつけましょう！！泣いて喜びます！！！

BFmetaインタプリタ・デバッガについて

GitHub - primenumber/BFmeta: Brainf*ckでリフレクションができるようにしたプログラミング言語BFmetaのインタプリタ・デバッガ

このBFmetaインタプリタ・デバッガはRubyで書かれており、デバッガモードではCursesを用いて、実行途中の配列の様子を見ることが出来るなど、詳しいデバッグを行うことができます。 デバッグモード時には入力をファイルで与えますが、名前付きパイプを渡すことができるのでインタラクティブなプログラムのデバッグも可能です。 まだ不十分な部分もあるのでPullRequest等どんどん募集しています！

KMCM

KMCこと京大マイコンクラブでは、難解プログラミング言語を通して自己を新たなステージに導きたい方を募集しています。KMCには入部制限はありません。年齢や学歴、人種、宗教、信条、性別、社会的身分、門地、国籍、経験などは不問です。また活動に関する制約もありません。IRCのチャット越しに会話に参加することだけでも大丈夫です。詳細は下記Webページを御覧ください。

これにてKMCアドベントカレンダーは無事（？？？）最終回を迎えました！皆さん有難う御座いました！！！

*1:Lazy Kは3関数、IotaやJotは2関数でプログラミングできるので最小ではありません

*2:実際に無限長の配列は用意できないので、十分大きな長さにするか、動的配列にして必要に応じて拡張する