ISHOCON1をScalaで書いたお気持ち

アジェンダ

ISHOCON1の初期実装にScalaを追加したよ!

github.com

目次

ISHOCON1にScala実装を追加した

goryudyuma.hatenablog.jp

これの第二弾としてScala実装を追加してみました!

やっぱり、新しく学ぶ言語でなにか作ってみるのは本当に勉強になります。しかもできあがるものがもう仕様が決まっているので、ただただ実装すればいいだけというすごく楽な点がやはり魅力的です。

実装はRubyのものを参考に、フロントエンドはGoにあるテンプレートを参考に実装しました。前回のCrystal実装ではRubyのERBのテンプレートと実装はGoを参考にしたので、今回は入れ替えてみた感じですね。

開発環境

今回、このScala実装はWindowsのWSLとVSCodeを使って書いてみました。前回書いた記事は実は伏線でした。

goryudyuma.hatenablog.jp

簡単なアプリを書くには特に問題なく書けることがわかりました!

VSCodeでターミナルがだせるのもすごく良い点です。

ただ、やはり大規模なアプリになってくると、IDEによる支援がほしくなるなーって思いました。使い分けは大事ですね。

技術スタック

今回、Scalatraっていうフレームワークを使いました。ScalaSinatraっぽく書けるやつですね。Ruby実装がSinatraで実装されていたので、同じように書ける物を選びました。ドキュメントが少し分かりづらいと感じた点以外は、概ねすごくいい感じに使えました!ドキュメントが分かりづらいと感じたのは、単に僕のScala力が低いだけな気がしてます。

テンプレートエンジンにはTwirlってのを使いました。普通に使いやすかったです。

他の言語による実装と合わせるため、O/Rマッパーは使わず、PlainSQLで書ける必要があると考えているので、データベース接続にはPlainSQLが書けるSlinkってやつを使いました。

それからこのscalatra.g8を使ってプロジェクトを立ち上げました。最初に必要なものを用意してくれるのですごく楽でした。

github.com

実装について

Rubyの実装を参考に書いたんですけど、実は少し後悔しています。結果としてすごく遅い実装になってしまったのはいくつか理由があるんですけど、そのうちの一つが動的型付け言語と静的型付け言語の違いです。

Rubyって普通の変数の顔をしながら平気でnilが入ってたりします。別にこれは悪い点ではなく、その特徴により非常に書きやすくなっているのですが、全く同じ動きをしたアプリケーションを静的型付き言語で書こうとすると問題が起きます。すべての変数をScalaで言うOption型にする必要が出てきます。

確実にnilが入っていないと確信できる時以外はすべてnilが入っているかもしれないと仮定しながら書くのは本当に辛いので、一部アレンジとして(ロジックは変えずに)改変しましたが、やりすぎて実装が別物になってしまうのも問題だというところが本当に難しいところです。

例を示します。

gist.github.com

Ruby実装のloginのPOSTの処理だけを抽出しました。

  1. まず、authnticate関数に、nilかもしれないparams['email']とnilかもしれないparams['email']を渡す。
  2. authnticate関数のなかでは、nilかもしれないemailを用いて検索をかける。nil.to_sが""となるのでエラーにはならない。
  3. ユーザーを探すが、見つからなかった場合userはnilとなる。
  4. userがnilでなく、パスワードが入力されたものと正しければ次にすすめるが、だめならIshocon::AuthenticationErrorとなる。(仕様でパスワードが平文保存なのはISUCON的には本質ではないので見逃す)
  5. sessionにuserのidを入れる。
  6. current_userを呼び出す。このときのsession[:user_id]は、この関数だけ見ればnilかもしれないが、authenticate関数を通ってきているので確実にuser[:id]が代入されているのでおそらくnilではない。(が、それをこの関数を見ただけでは保証できない点が怖いといえば怖い)
  7. つづいて、update_last_login関数に、おそらくnilではないuserのidを渡す。
  8. そのユーザーのlast_loginを、現在時刻に更新する。
  9. redirectで/に飛ばす

と、こんな感じの処理になっています。うまくやってますが、nilが出てくる可能性が結構高いです。

Scalaでこれを実装する

さて、Scalanilっぽいことをやろうとしたら、Option型を使ってやる必要がありますが、先程述べたようにいちいち全部の変数をOption型に入れては取り出しってやっていくのは非常に辛い。

アルゴリズム的にNoneになるかもしれないuserは仕方ないとしても、私の実装では最初にauthenticate関数に渡すemailとpasswordはOption型でない普通のString型で渡すように変更したりして、うまく解決を図っています。

ここから少しネタバレになりますけど、authenticate関数でemailからuserインスタンスを作ったあと、user[:id]だけをsessionに保存したあと、userインスタンスを一度破棄し、その後でcurrent_userで先程保存したsessionの中のuserのidからまた同じuserインスタンスを作り出してるんですよね。ここ、authenticate関数がuserインスタンスを返せばそれだけでcurrent_user関数はいらなくなって、Scala実装的にもきれいに書けるんです。だけど、ISHOCON的には「ここでSQLを二回呼んでuserインスタンスを二回生成するのは無駄な処理なので、競技時間中に無くしましょう」的な意図も感じるんです。(深読みしすぎですかね?)。なので、ここのロジックを変えるわけにはいかず、Ruby実装に忠実に二回のSQL文とUserインスタンス生成をScala実装でもやっています。

ここが本当に重要なポイントで、今この実装になっているのは、作問者が意図して遅くしようとしてこの実装になっているのか、それとも普通に実装したらこうなってしまっただけでもっと早くしてもいいのか、区別がつかないんですよね。

普通のアプリケーション開発ではこの問題は起こりえないでしょう。というか問題にすらなりません。読みやすくもなり、無駄なインスタンスを生成しなくもなり、さらに高速化にもつながる、やらない理由はない案件ですから。しかし、ISUCONのクローンを用意している状況となると、意図してこの状況にしている可能性があり、その可能性が排除できない以上、無駄な実装をせざるを得ないです。

かといって、いちいち細かいところまで作問者に問い合わせるのも大変ですし、所詮は遊びでやっているので、自分の思ったとおりにやっています。

実装した結果

Scala実装が書けたあと、普通にベンチマークを回すと、ベンチマーカーの並列度が1と2の時は正の点数になりましたが、並列度を3以上にすると負の点数になってしまいました。ベンチマーカーのデフォルトの並列度は3なので、普通にベンチマークを取れば負の点数になっちゃいます。

例に上げたpostのloginの処理以外にも、Scala的でない実装になっているポイントがいくつかあって、それらを改善することで、(ロジックをそんなに大きく変えなくても、)並列度3でもおそらく正の点数が出るようになると思います。もちろんISHOCON的に遅くなっている部分を直せばもっともっと点数がのびるはずです!ぜひ頑張ってください!

終わりに

今回は気分が乗ったので、Scalaで実装してみました!これからも不定期に気分が乗ったときに、他の言語も追加していきたいと思います。

ISHOCON2も結構楽しみにしていて、最初にあったRuby実装に加えて最近Python実装も増えたのですが、まだGo実装がなくて試せてない感じです。やっぱり競技者として出る時は得意な言語で出たいですしね。じゃあお前が実装しろよって話ですけど、競技者として一度やってから書くほうが絶対にいいんですよね。あとから気付く、「ああ、あの時ああすればよかったのか」感が好きなので。なのでGo実装待ってます!(笑)

最後になりましたが、作問者の@showwinさん、楽しい問題をありがとうございました!

WSLとファイルパーミッションとVSCodeの話

アジェンダ

WSL(Windows Subsystem for Linux)により、Windows上でもLinuxが動くようになった。しかし、本格的に用いるにはまだまだ怖い点がいくつか残っており、その一つのファイルパーミッションの問題を解決しようとしてみた話。VSCodeでSSHFSを用いてWSL上のファイルを編集する。(何番煎じだろう?)

キーワード

WSL, SSHFS, VSCode

目次

はじめに

 WSLにより、Windows上でLinuxが動くようになった。しかし制約はもちろんあり、最も大きな問題の一つとしてファイルパーミッションの問題がある。元々Windows側にはLinuxのようなファイルパーミッションのしくみはないので当然といえば当然なのだが、WSL側でパーミッションを指定して作ったファイルをWindows側に持っていくとその時点でパーミッション情報が失われ、またWSL側に戻してきても情報は失われているのでファイルは正しくない状態のままとなる。

例を示す。

WSL上でtest.txtを作り、パーミッションを確認すると、ファイルはパーミッション666で作られていることがわかる。

f:id:Goryudyuma:20180606032901p:plain

とりあえずパーミッションを644に変更してみた。無事通る。

f:id:Goryudyuma:20180606032909p:plain

WSL上では、Windows側のフォルダは/mnt/c/などにある。ので、Windows側にファイルを動かしてみる。

f:id:Goryudyuma:20180606033154p:plain

ファイルパーミッションは777になってしまった。

元の場所に戻してみる。

f:id:Goryudyuma:20180606033307p:plain

無事、もとに戻りませんでした\(^o^)/

問題点

このマシンだけで個人開発するのなら、ファイルパーミッションが壊れてようがそんなに問題は大きくないが、他人や他のLinuxのマシンでも開発する場合はファイルパーミッションをいちいち壊されても困る。git update-indexみたいな機能もあるみたいだけど、それはなんか違う気がする。

やりたいこと

Windows側にあるVSCodeでファイルを編集したい。WSL上で例えばVimとか使って編集すればいい話ではあるが、GUIエディタを使いたいときもある。

そこでVSCodeで開くために、編集したいファイルを/mnt/c/に持ってきたところ、ファイルのパーミッションがだめになっていた。

解決策

SSHFSで繋げば思っていたことが実現できた。

手順

  1. WSLにopensshを入れる。

    Bash on Ubuntu on Windows で sshd を使用する

    (memo:公開鍵認証を用いる場合は/etc/ssh/に用いる形式の鍵がないと通らない。)
  2. VSCode SSH FSを入れる

    SSH FS - Visual Studio Marketplace

  3. configを書く
    SSH FS Create a SSH FS configurationから、設定ファイル名入れると、勝手にjsonの雛形ができる。必要な情報を入れるだけ。私の場合はRSAを使ったのでこんな感じ。

    f:id:Goryudyuma:20180606040248p:plain

    (memo:秘密鍵の改行は\nに置換する必要がある。これもVSCodeなら秘密鍵VSCodeで開いて「Ctrl-F」で正規表現モードで「\n」を「\\n」に置換すればよい。)

    (memo:VSCodeが使っているSSH FSがSSH2に依存していて、そのSSH2はopensslがnodeに依存していて、nodeがOpenSSL1.1.x系にまだ対応していない。そのためed25519は使えないみたい。おとなしくRSAで。)

  4. WSL側でSSH Serverが動いている状態でconnectしてやると、VSCode上でWSLのファイルが見え、編集できる。ここで編集しても、パーミッションは壊れない!

というわけで、WSL上のファイルをWindows側のVSCodeで編集できるようになった。

TODO:

  1. SSH ServerをWindows起動と同時に実行するようにする(まだやってなかった)
  2. WSLでファイルやフォルダを作ったとき、それがVSCodeには即座に反映されない。更新ボタンを押すことにより反映される。自動で更新したいが、更新するためには「workbench.files.action.refreshFilesExplorer」を呼べばいいことはわかったが、呼び出してしまうとフォーカスがエクスプローラーに移ってしまう。定期的にフォーカスがエディタから取られてしまうのは非常にストレスだった。だけどなにか書いているときにも、ファイルやフォルダが変われば自動で反映してほしい。

終わりに

ちょっとだけWindowsで開発できる環境に近づいた、ような気がする。

(もう少し使いやすくなってほしいな。)

あとがき

このブログでまともな技術記事書いたの初めてな気がする、こういうのはQiitaに上げたほうがいいのだろうか。

ISHOCON1をCrystalで書いたお気持ち

アジェンダ

  • ISHOCON1にCrystal実装を追加したよ!Crystal書ける人はぜひ挑戦してみてね!
  • Crystal強い人のレビュー、お待ちしています!

 

目次

ISHOCON1にCrystal実装を追加した話

新しい言語を覚えるには

新しい言語をどんどん覚えていきたい欲はあるのですが、どのようにすればいいでしょうか。一番は、その言語で何か物を作ってみることだと思います。

まずは定番、「HelloWorld」から始まり、「FizzBuzz」書いてみたりします。標準入出力を学んだあと、ループや条件分岐を学ぶ感じですね。この後は競技プログラミングの簡単な問題で、文字列の扱いや配列の扱い、classの扱いまでやって、木構造なんかを作ってみるって感じで僕はやっています。

今回新たなルートとして、ISHOCON1に実装を追加するってフェーズを付け加えました。

ISHOCONとは

ISHOCONとは Iikanjina SHOwwin CONtest の略で、ISUCONと同じように与えられたアプリケーションの高速化を競うコンテスト(?)です。  

github.com

ISUCONクローンとして有名なプロダクトとして、pixiv社のpixiv isuconYahoo! Japan社のY!SUCONなど共に挙げられるのがこのISHOCONです。特にISHOCONは企業としてではなく、個人プロダクトとして公開されている点が特徴です。

なぜISHOCONを選んだのか

ISHOCONは、本家ISUCONや他のISUCONクローンプロダクトに比べて、コード量が少ないことが特徴的です。その分初心者向けで、コードの全容を把握してからISUCONする(最適化していく)って感じでも、全然行けるようになっています。8時間あれば、僕一人でだいたい改善したいところは改善しきることができる分量です。本家ISUCONでは三人がかりでもこんなこと絶対に無理です。なので、参考実装を作るのは、比較的楽な方だと思います。

また、作者の人と会ったこともあるってのが、心理的な障壁を大きく下げてくれました。

なぜCrystalを選んだのか

まず、Crystalとの出会いは、AtCoderで提出できる言語一覧にあった事でした。

crystal-lang.org

とりあえずWebページ行ってみると、「C言語のように速く、Rubyの書き味を持つ」(Crystal-jpのSlackより引用)ってなってて、なかなか面白そうな言語があるなーって思いました。

AtCoderで何問かCrystalを使って解いてみて、いい感じで使えたので、もうちょっとこの言語について詳しくなりたいと思いました。

CrystalのWebページには、最初にWebサーバーでHelloWorldを返すやつを立ててみるところから始まっています。これはWeb向きの言語なのかなって思いました。なので、深く学びたければ、Webサイトを作ってみるのが良さそうだと思いました。

なぜISHOCON1のCrystal実装を作ろうと思ったのか

CrystalでWebサイトを作れば、Crystalをよく学べるかなと思ったのはいいのですが、じゃあどんなWebサイトを作ればいいのってなります。僕はアイデアマンではないです。そうぽんぽんいいアイデアなんて浮かびません。また、普通のプロジェクトを別言語で書き直したところで、メンテナンスが面倒になるだけですし、一つのプロジェクトで複数の言語の実装があるなんて意味がわかりません。ですが、特殊例として、ISUCONに関してだけ言えば、複数言語による参考実装がないと困ります。

主催者が考えるに、スコアが出せるかどうかは言語の問題ではない、と思うからです。どの言語だろうと勝つ人は勝ちます。速い言語遅い言語で勝負がつくようなつまんない問題は過去一度も出されませんでした。

tagomoris.hatenablog.com

ISUCONに関して言えば、言語差はあまり関係ありません。競技プログラミングでもC++は強いけど、でもC++でないと絶対に勝てないかと言われればそうではないですよね。

ISUCON的には参考実装言語が多ければ多いほどいいと思います。その分、「あの言語なら詳しいけど、参考実装にはないから、普段使い慣れていない言語を使わざるを得なくなって、点数伸びなかった」みたいな人を減らすことができます。もちろん作るのにそれだけコストがかかる上に、その言語の実装を誰も使わない事態が起こりうるので、本家ISUCONでは参考実装される言語がメジャーな言語に絞られるのは当然のことだと思います。

しかし、ISHOCONに関して言えば、いつ始めても何時間やってもいいプロジェクトですので、いくつ参考実装があってもいいと思います。誰かが使ってくれたら嬉しいですけど、使ってくれなくても用意するだけで意味があるかなと思います。もしかしたらここからCrystalを勉強するユーザーが増えるかもしれませんしね。

というわけで、ISHOCONの参考実装を増やそう、面白そうなCrystalって言語を使ってみようってなりました。

ISHOCON1のCrystal実装の作り方

基本的にはロジックはGolang、テンプレートはERBがあるRubyを参考にしました。

ERBライクなテンプレートを使えて、ルーティングとか基本的なことをやってくれるCrystalのWebフレームワークとしてKemalを使いました。

kemalcr.com

方針としてはGolang実装を見ながら、そのままCrystalに起こしていく感じですね。関数名とか変数名とか、なんとなくCrystalっぽそうな感じに変換しながらやっていきました。僕はCrystalでWebサイトを書くのはこれが初めてなので、変換ルールとかはかなり適当です。もし気に入らないところとかあれば、プルリクとかIssueとかを大歓迎しています。

そんな感じで一気に実装していき、ベンチマークを通ればプルリクとして送ります。いくつかレビューで直す点があったので直した結果、マージされて、晴れてISHOCON1の参考実装にCrystalが加わることになりました!

今後

今後もISHOCON1に新しい言語実装を増やしてみたりしたいなーって考えてます。リクエストパラメータとかデータベースアクセスとか、AtCoderではできないような所をしっかりと学べますし(←そもそもAtCoderはそんなことを学ぶ場ではないですけどね)、何より作ってる時がとても楽しいです。

一度Crystal実装のISHOCON1を試して欲しいですし、もしもうCrystalをマスターした方なら是非「ここはCrystalの流儀だとこうする」なんか送りつけてもらえるとありがたいです。

また、参考実装を増やしてくれる人が増えたらなーって思います。色々な言語で実装されたWebサイトとか、なかなかユニークで面白いですよね。勉強にもなりますので、是非オススメします。

最後になりましたが、こんなに面白いコンテンツを作っていただいた上に、レビューまでしていただいた@showwinさんにはとても感謝しています。ありがとうございました。これからもよろしくお願いします!

github.com

競技SQL部 MISQUERY ONLINE WriteUp

MISQUERY ONLINE

「競技SQL部 MISQUERY ONLINE」というページがあります。

NKHR.MOE

競技プログラミング」×「SQL」という、競技プログラミングは一般的にC言語などのプログラミング言語を用いるのに対して、SQLのみを用いて競技プログラミングを行う一風変わったサイトです。

この度作者様からWriteUpを書く許可が得られましたので、書き残しときます。

 

 

注意:ここから先はネタバレになります。まずは自分の力で解きたい、などの方は見ない方が良いかと思います。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

制約

まずは制約の確認を行いましょう。競技プログラミングにおいて、制約の確認を怠ると、とてもひどい目に遭います。

制約はそれぞれ問題文に書いてあるので、しっかりと目を通しておくこと。

それから全体的な制約として、実行環境は「PostgreSQL 9.2.18」が使われています。PostgreSQLにない関数や、このバージョンより新しいPostgreSQL加わった関数などは使えません。もうEOLを迎えてしまっているので手元に環境を用意するのは少し難しいかもしれません。

PostgreSQL: Versioning policy

該当バージョンは既に無くなっていましたが、PostgreSQLを用意するだけならDockerが便利です。

https://hub.docker.com/_/postgres/

SQLの文法ミスでも、9.2.18の時点ではなかった関数を書いても、サイト上では「SQL ERROR」と出るだけなので、エラー文を見るためにできるだけ同じ環境を手元に用意した方がやりやすいとは思います・・・。試行錯誤もしやすいですしね。

ここから本格的にネタバレ 

続きを読む

CodeThanksFestival2017参加記

はじめに

この記事はkstmアドベントカレンダー2017 7日目の記事として書かれました。

qiita.com

目次

行く前 

まずは予選から。CodeFestival2017本戦は、人数が去年に比べて大きく減ったのでボーダーが上がったのと、仮に通っていてもISUCON通っていればISUCONに行くと決めていたので、Thanks行ければいいやーって感じの低いモチベでした。

予選Aは例年通り、かなりボーダー高めで通すのは難しそうでした。三問といて879位(日本人452位)。

予選Bはカプセルホテルでやりました。三問解いて289位(日本人119位)。

予選CはISUCON7予選終わった直後から始まった地獄でした。めっちゃしんどかった・・・。三問解いて350位(日本人145位)。

BかCのどちらかで通ったんでしょう。

前日

夕方ごろ、新幹線で東京まで。池袋で少し遊んでから、株式会社Aimingさんのオフィスに遊びに行ってました。

aiming-inc.com

寿司食べながら駄弁りながら飲みながら競プロしながらボドゲするというよくわからない会でした(笑)。キーボードの変態配列の話、とても面白かったです!ありがとうございました!

この後から結構大変でした。電車で上野駅まで。

新幹線の中で予約した、一泊1500円の見るからにヤバそうな宿に行きました。

宿は四人部屋で、僕含めて三人で使いました。いびきとかうるさい人でもなく、めんどくさい絡みしてくる人でもなく、平和に過ごしました。

宿は良かったんですけど、スマホが壊れました。OSがうまく起動できない?みたいな感じでした。出先で宿のWi-Fiもかなり不安定でしたが、スマホ使えないと色々お話にもならないので、復旧を決意。OSをクリーンインストール?とりあえずBIOSからいけるResetを全部して、Androidのインストールバトルをやりました。一番困ったのが、Googleアカウントの2段階認証をやってる端末を吹っ飛ばした状態で、かつ非常用パスコードを保存している端末には出先のためアクセスできない状態だったってことですね。粘った末に電話認証に気づいてうまく行ったんですけど、かなり時間使いました。

OSのアプデ、アプリのアプデを不安定なWi-Fi環境で行いました。かなり辛かったけど、サークルのインフラ班のあーちゃんとふぉのさんが普段言っていたことが、ものすごく役立ったりと、様々なファインプレーが重なった末、朝8時半頃に復旧。ホテルを出て(本当に1500円しか払わなかった、東京すごいですね)、地下鉄で豊洲を目指しました。途中、銀座一丁目銀座駅が同じものだと思ってたっていうミスがありましたがうまく有楽町駅にたどり着けたためセーフ。豊洲からゆりかもめで会場に向かいました。

当日

会場ついて、交通費精算して、TシャツGetして、周りに挨拶して、お弁当Getして、コンテスト開始。1800点以上でパーカーと聞いてテンションMAX。

A:Sortするだけ

B:回文となる文字列の文字数は奇数個と思い込んで1WA。しょーもないWAは無くして行きたい・・・。すぐ直してAC。

C:PriorityQueueで管理するだけ。AC。

D:ぱっと見でわからなかったので飛ばす

F:同じ数ずつまとめて、Combination計算してやろうとしたが、どこかでバグって1WA。mapでdpしてやるとなぜか正解した。

D:戻って見るとGCDとるだけと気づく。AC。

E:6^5<10000に気づく。6個ずつ確定していけば終わりそう。書いてAC。パーカーゲット。

G:PriorityQueueで適当なコード書いたけどTLE。ダメダメ。

H:H+M個のメモリをとってやり、うまく飛んでいくような感じで書いたけど二ケースTLE。

これで終わる。6完34位でした。

コンテストおわって、パーカー受け取ってからchokudai先生のライブ解説。

その時のF問題の指摘で、

 と、最悪ケースでTLEになるかもしれないとの指摘。理屈で考えてもダメだし、手元でやって見ると確かにTLEになる遅さ。

 出題者曰く想定外の解法だったらしく、まぐれで通ってしまった。パーカーボーダーラインだったので、助かったというかなんというか。もしこの回答がTLEときちんと判定されてたら、ちゃんと時間内で解けたかは謎・・・。

そのあと、交流会。一つ質問を決めて、参加者に聞いて回るってイベントがあったんですけど、僕は単純に思いついた「好きな数字」っていう大雑把な質問をして回りました。面白いことに、40人弱聞いて回りましたが、かぶった数字は2と17だったかな、意外とみんなバラバラな数字書いてくれました。πとか1e9+7とかeとかもあって、ああ競プロの集まりなんだなあと思いました。

回答集めるのそこそこ早かったっぽくて、タンブラーもらいました。今回はいいものばっかりもらった!そのあとは、肉食って寿司食ってサンドウィッチ食ってジュース飲んでってやってました。競プロ疲れたのと、スマホのせいで少し寝不足なのもあって、めっちゃ食べた。

表彰式があって、解散したあとは、すぐに長野へ帰りました。途中ゆりかもめから花火が見えて、綺麗だったなあ。

終わりに

信州大学ものづくりサークルkstmでは、競技プログラミングに興味ある学生も募集しています。ちょっとでも興味あれば、ぜひよろしくお願いします!

部員募集 | kstmについて | 信州大学公認サークルkstm

SQLで円を描く技術

はじめに

この記事はkstmアドベントカレンダー2017 1日目の記事として書かれました

qiita.com

 

目次

 

まずは見てくれ!

gist.github.com

SQLで円が描けた!

コード解説

検証、実行環境はPostgreSQL10.0です。

基本方針としては、まず方眼紙を用意して、次に条件判定で塗るべきところを*で塗っているだけです。SQLなので、再帰でごにょごにょします。

まず、limitxyで表示する大きさを決めています。

そして、formulaでnを1ずつ増やしていく過程で、x,yをうまく回しながらCASE WHENで条件判定を行い、どこを塗るのかを決めています。

最後にくっつけて出力するところを書きます。

それを呼び出すと、SQLだけで円を描くことができます!

ギャラリー

条件式を変えると、他にも色々描けます。

gist.github.com

gist.github.com

書いた動機

とある就活関連のイベントで企業の人と話していた時、

僕「ボクSQLチョットデキル」

企業戦士「へー。うちの会社にSQLで円とか描いてる人いるけど」

僕「なにそれすごそう」

帰ってきた後

僕「あれ?よく考えたら結構簡単にできるのでは?」

カキカキ〜

僕「できた!なんだ簡単じゃん!」

 みたいな感じでした。

最後に

信州大学ものづくりサークルkstmは、技術に興味のある信州大学生を募集しています。面白そうだと思っていただけたら、是非見学に来て下さい!

部員募集 | kstmについて | 信州大学公認サークルkstm

あと僕、就活中です。こんなSQLを書ける(描ける?)新卒エンジニアを募集してる企業さん、是非お声がけください!

馬 (@Goryudyuma) | Twitter

ISUCON7本戦で惜敗してきた

どうも、馬です。

今年もISUCONの本戦に行ってきました!

運営の皆さん、関わった皆さん、本当にありがとうございました!とても楽しかったです!

チームメイトの記事

あーちゃんの記事

bgpat.hateblo.jp

ふぉのさんの記事

ISUCON7本戦惜敗記(学生枠)

今回のコード

github.com

あーちゃんがブランチ分けたりGitのテクを駆使して、ソースコード管理オペレータをやってくれたので、依頼すると「この時点までこのコードだけ切り戻し」とかやってくれました。さすが。

あと、Closeされてますけどやることリストを今回も作ってます。

github.com

前も書いた通り、これは次にやることがわからなくなった時に使うものなので、あまり使わなかった感じですね。

ちょっと縁あって株式会社scoutyさんのオフィスでこのやることリストを作りました。ありがとうございました!

scouty.co.jp

前日まで

ISUCON7予選、ISUCON5本戦、ISUCON4本戦をやろうとしたのですが、結局ISUCON5本戦はうまく動かずでした。コードを見ると、もうaptで配布されていないgradle2.8をバージョン指定で入れていたので、2.8の部分を削ってビルドが通るようにしたり、PHPのいくつかのライブラリのがおかしかったので直したりしてみたのですが、ちゃんと動いているかよくわからない状態でした。二年も前のアプリケーションだとよくあることかもしれませんが、ISUCONは動かすところからだ!と言われると・・・って感じなので、なんとかしたさがあります。だけど今の環境でも動くようにするということは、スコアに影響があったり、二年前より楽になるor辛くなることがあるので、本番と全く同じ状態ではなくなってしまうところが、難しいところですね・・・。割り切りが必要そうです。

ISUCON7予選とISUCON4本戦は楽しんでやれました。もう三年も前のISUCON4本戦が普通に動いたことは、本当にすごいことだと思います。

やったこと

今回はあまり仕事できなかった感じですね。

チームではいつものごとくDB担当でしたけど、テーブルは綺麗なもんで、いじるところとか特になかったです。slow queryになるまで行けなかったです。

強いて言えばトランザクションのところが遅いと言えば遅かったですけど、かなり触りづらい感じになっていた上、AppのCPU使用率が高すぎて、ボトルネックになっていました。

不変値であると判明したm_itemをinitialize時にメモリに読み込む処理をサクッと書いたあとは調査、遅いところを直していこうって感じでした。

書いている間にふぉのさんは使うかもしれないRedis入れたりとかの環境の整備、あーちゃんはデプロイの自動化とかやってました。

golangでやってたので、pprofで調査したところ、多倍長演算がとんでもなく時間食っていることが判明しました。

この時の話し合いで、僕は多倍長演算をなんとかする、あーちゃんは構成を分散させてroom名で使うマシンを切り替える、ふぉのさんはそのサポートって感じで仕事を分けました。

結論から言うと、多倍長演算を最後までなんとかできなくて、あまり点数を伸ばすことができませんでした。

addingの方はかけ算をサボることができて、まず左から60bitくらいを残すように右にシフトさせたあとかけ算して、右にシフトさせた分を左にシフトし直すことで、誤差範囲内でかなりの計算量を減らすことができたのですが、Priceの方はこれやっちゃダメで、どう頑張っても誤差範囲内に収めることができませんでした。書いてる時はわからなかったのですが、これは当たり前で、買えるかどうかの判定を厳密な値を用いて判定しているからでした。大して多くもないパターン数だったので、計算結果をキャッシュすればよかったっぽいんですけど、引数が64bit変数だったんでキャッシュは無理って判断してました。少し競技プログラミングを齧ってる身としては、今から思えばなんで無理って思い込んだんだろうってなってます。

あーちゃんの方の分散はある程度うまくいき、ジャッジケースセットによっては一つのマシンに偏ったり、うまく分散したりと、微妙な挙動をしてました。

結局やれたのはここまでで、あとはガチャ回していい結果を引こうとしたのですが、うまくひけず、最高点の17000点くらいまでできずに12000点くらいでフィニッシュしました。競技終了後に運営側で一回回して、その点数と競技時間内最後に提出された点数の高い方が取られるので、ちょっといいガチャが引けたっぽくて15000点くらいの結果になりました。

再起動試験は2回くらいしかやってなかったので、少し不安だったのですが、ちゃんとFailせずに終わりました。

 

終わってから

なんか頭がぼーっとしちゃって、ちょっとしんどかったです。でもビール飲んでケーキ食べたらちょっと回復しました。

優勝したチームと全く同じ構成(golang+vim)だったので、実質優勝もっといい点数を取りたかったです。

来年はあーちゃんがいなくなるので、今回でこのチームも解散です。

ISUCON5,6,7と本戦出場率100%を誇るすごくいいチームでした。

来年のISUCONはどうするかまだ決めてないのですが、あーちゃんレベルの超人オペレータはなかなかいないので苦戦しそうです。それとコード読める人が欲しい・・・。

そろそろ就職活動するんで、もし面接とかでお会いできれば、よろしくお願いします。

リンク集

isucon.net

goryudyuma.hatenablog.jp