もう一度Nginx+Unicorn+Railsを試してみる
もう3年以上前のことですが、一度Unicornを試してはいます
Rails3アプリをnginx+unicornで動かしたら速すぎた - ぱろっと・すたじお
その頃はまだ「運用」に関するノウハウが足りておらず、
サーバ再起動のたびに失敗する起動スクリプト*1を手動で実行するとか、
速さの代償にいろいろ面倒を背負い込んでいる感じでした(´-ω-)
なにより、動かしていたサイト自体が頓挫し、
その後構築していたRO用のシステム*2は、
一つのサーバに複数動かす仕組みだったので、あまりUnicorn向きではありませんでした
(今の仕事でも、Rack以外の部分も含めて統一した運用をしたいということで、
あえてApache+Passengerという環境で動かしています)
そして今取り組んでいるのがこちらですが・・・
Get our light! - チェンクロパーティーシミュレーター
・・・これを独立したドメインにするか悩んでいて、
とりあえずサーバだけ移行しようかな・・・と考えていたところ、
今月のWEB+DBでRackサーバの記事を読んだわけです*3
- 作者: 原田騎郎,吉羽龍太郎,山口陽平,青木雅弥,松下誠太,三宅英明,高橋征義,南川毅文,伊藤直也,海野弘成,高安洋輝,佐藤歩,泉水翔吾,佐藤太一,横江直輔,舘野祐一,橋本翔,渡邊恵太,中島聡,はまちや2,小沢邦雄,長沢智治,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2014/10/24
- メディア: 大型本
- この商品を含むブログを見る
一つのサーバに一つのアプリならUnicornで問題ないですし、
記事の中でもだいぶ枯れていると紹介されていたので、
いい機会だからやり直してみようかと
以上、経緯と前置きでしたΣ(・ω・ノ)ノ
なお、今回参考にさせていただいたサイトはこちらです
Ruby - Nginx+Unicorn設定ファイルサンプル - Qiita
Unicorn+Rails入門 - Less is Best
Unicornの設定
Unicorn側は3年前とそんなに変わるところがないのですが、
同一サーバの場合はソケットがいいらしいので、
そこが以前と変わったところでしょうか
https://github.com/parrot-studio/cc-pt-viewer/blob/master/config/unicorn.rb
といっても、以前のシステムはソースをGitHubに置いてない*4ので、
比較しようもないわけですが・・・(´・ω・`)
あと、以前は「unicorn_rails」ってコマンドを使っていましたが、
今はただの「unicorn」で起動するのが主流だそうです
Nginxの構築
Passengerの場合、組み込む都合で専用のインストーラーがあったりしますが、
今回はProxy経由なので普通にyumでインストールしただけです
設定ファイルもひな形を作ってくれるツールがあります
https://github.com/i2bskn/nginx_utils
Unicornとの連係を前提にしたconfを出力できるので、
そこだけ指定した形で出力し、細かいところは後からいじりました
upstream backend-unicorn { server unix:/path/to/app/tmp/sockets/unicorn.sock; } server { listen 80; server_name ccpts.parrot-studio.com; root /path/to/web/root; index index.html; location / { try_files $uri @proxy; } location @proxy { proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for; proxy_set_header Host $http_host; proxy_redirect off; proxy_pass http://backend-unicorn; } }
「ファイルがあればそのまま返し、なければProxy」って設定が、
これだけ簡単に書けるのはすばらしいですね(`・ω・´) b
まあ、以前からあったのを、当時の私が知らなかっただけ、という可能性も・・・
あとは自動起動スクリプト(for CentOS6.5)ですが、
調べるといろいろ出てきますので、必要なところを書き換えて使用しました
私がやったのは、「unicorn_rails」を「unicorn」に変えた程度です
運用レベルでのPassengerとの違い
PassengerはNginxに組み込まれて動いており、
アプリ再起動のために「restart.txt」の仕組みが存在します
なので、基本的にはアプリの管理を一般ユーザで実行できます
Unicornの場合はアプリ自体をinit.dで自動起動しているため、
実行権限はrootになります
そのため、システムが生成するtmp以下のファイルは、root権限になります
このため、アプリのcacheクリア等*5をsudo経由でやらないといけないのが面倒なのですが、
一般権限でUnicornを動かすような指定も面倒だったので、そこは許容してますΣ(・ω・ノ)ノ
いやまあ、「最近のサーバ管理手法」とかなんとかいろいろあるのはわかりますが、
今回の目的は「Nginx+Unicornで動かすこと」なので、
その辺は "面倒になったら" 考えます
以上、わかっている方には当たり前の話でしたが、
例によって自分用のメモ書きということで...φ(・ω・`)
例えば、パスワードを避ける
今回も長いメモ書きなのですが・・・
最近、パスワードに関する議論*1が多かったわけですが、
もっと根本的にどうにかならないのかな・・・と思いまして
自分でそう思ったというか、せんせー*2のTweetを見ていて、
「もう一つ上のレイヤーで考えないといけないんだな・・・」と気づいたというか
|ω・`).。oO( なるほど、理解した 「パスワードに関する議論」そのものが、現状においてはもはや建設的ではない 「どうやってパスワードを破棄するか?」の方が現実的だ )
— ぱろっと (@parrot_studio) 2014, 10月 17
つまり、こういうことなのかなとΣ(・ω・ノ)ノ
考察の前提
この手の考察はいくらでも発散するので、大前提として、
「不特定多数に公開されたWebシステムにログインする場合」に限定します
「パスワード」の限界
|ω・`).。oO( ローカルログイン等、状況によっては十分役に立つ でも、「Webにおける辞書攻撃」に対して、「パスワードという仕組み」自体がもはや脆弱だ MD5やSHA1と同じ )
— ぱろっと (@parrot_studio) 2014, 10月 17
|ω・`).。oO( 理論的上、辞書に「存在しうる全ての文字列パターン」が存在し、それを「現実的な時間」で試行できるなら、どうやっても防御ができない それよりも、「別な仕組み」を考える方が「未来」を見据えるなら建設的 )
— ぱろっと (@parrot_studio) 2014, 10月 17
極論ではありますが、「文字列のみで照合する」という仕組みである以上、
どうやったって「いつかは」突破されるわけです
そもそも、「辞書に載ってない文字列」というのは、
「人が覚えるのに適していない文字列」なので、面倒ですよね(´-ω-)
「認証」が満たすべき要件
|ω・`).。oO( 「認証が満たすべき要件」とは、「自分であることを証明でき、かつ他人がそれを容易に利用できないこと」なのだから、「文字列」である必要はない かといって、「何らかの外部デバイスの強制」はWebの文脈では強すぎる ではどうするか・・・ )
— ぱろっと (@parrot_studio) 2014, 10月 17
|ω・`).。oO( Win8における「ピクチャログイン」は、文字列ではないし、直感的なログインが可能という点で優れている 私もあればかり使っている でも、「覚えてなければならない」という点でまだ不十分 「デバイスに依存せず、何も知らなくてもいい」に持っていく方法は・・・ )
— ぱろっと (@parrot_studio) 2014, 10月 17
私自身、実験的に「合い言葉(=マルチバイト文字列)認証」のシステムを作ったことがあります
下書きをひっそりと共有するサイト「紙片」を公開しました - ぱろっと・すたじお
この問題点を今改めて考えてみると、
「意味的な表現とバイナリ表現が一致するとは限らない」ってことで
つまり、「UTF-8で"ああああ"」くらいであれば、
ほとんどのブラウザで一致するはずです
しかし、絵文字のような最近定義された文字列を使われた場合とか、
そもそも日本語がまともに実装されてないブラウザ*3の場合、
そこは保証できません(´-ω-)
一方、ASCIIの範囲であれば、たいていのシステムでコードが一致するため、
「意味とバイナリ」が1対1で対応するはずです
そういった利点もあったのかな・・・と
なにより、こういった「自身が設定した"何か"による認証」は、
「それを記憶しておかなければならない」というコストが常に存在するわけです
つまり、「何も覚えてなくていい」状態が理想なのではと
デバイスの依存性と二段階認証
|ω・`).。oO( 「OTPトークン」は現時点において相当強い しかし、デバイスがなければ全くログインできない まだROにおける「電話認証」の方が「いつでもログイン可能」という点で優れている それでもまだ「電話というデバイス」に依存している 持ってない人が少ないとはいえ・・ )
— ぱろっと (@parrot_studio) 2014, 10月 17
|ω・`).。oO( 林檎の「Touch ID」も、「容易にログインできる」という要件は満たすけども、「デバイスに依存しない」という要件は満たせない Webの認証を「Webのみで」「安全に」「完結させる」方法・・・・・・ )
— ぱろっと (@parrot_studio) 2014, 10月 17
「覚える情報を減らす仕組み」として、
現時点で最適な回答としては「パスワードマネージャー」でしょう
実際、私も"ほぼ"移行しています
パスワードマネージャーの問題はシンプルで、
「パスワードマネージャーが使えない環境では結局手打ち」ということです
例えば、Twitterのパスワードをソフトウェア的に管理していたとしても、
Androidのクライアントアプリにログインするときは、
キーボード入力しないといけません
その辺の解決策として、iOS8版1Passwordは良くできていると思います
それでも、「アプリ側が仕組みに対応していないと使えない」*4だけでなく、
そもそも「iOS8以上のデバイスでしか使えない仕組み」であり、
Androidはもちろん、私のiPad miniはiOS7なので、iOS系なのに使えないわけです(´-ω-)
「パスワードを使い回したとしても、一定の効果がある手段」として、
最近では「OTPトークンによる認証」や「二段階認証」が存在します
OTPトークンはオンラインRPGのログインでもよく使われていますが、
1分ごとにアルゴリズムで値が変更されるため、
たとえある時点での値が漏れても、ログインは相当難しくなります
欠点はシンプルで、「OTPトークンがない限りログイン不可」ということです
スマフォにOTPトークンアプリを入れることである程度リスクを軽減はできますが、
OSのアップデートで動かなくなるとかよくあるので、
たいていは物理的トークンの方が楽、という結論に至ります(´・ω・`)
やはり、現時点で妥当なのは「二段階認証」でしょう。
GoogleやMSにログインする場合、IDとパスワードが正しくても、
送られてくるSMSやメールに書かれたコードがなければ、
最終的なログインはできません
OTPトークン方式を実装しているROでも、
トークンを設定してない場合、「電話による認証」が行われます
ログインすると「あちら」から電話がかかってきて、
コードが「音声で」読み上げられるので、
それを「Web画面に」入力するわけです
冷静に考えると、この方式はかなり「楽」で、
OTPトークンと電話、どちらを忘れる確率が高いかは自明ですし、
「OSのアップデートで電話ができない」ってことはまずないはずです*5
デメリットは、「(一時的とはいえ)電話番号を渡す」という心理的障壁と、
あと導入側の料金的コスト*6が、おそらくOTPより高いという点でしょうか
そして、あまりないことかもしれませんが、
「電話がない場合はどうしようもない」という問題もあります
とはいえ、最近は「スマフォでインターネット」が一般化しており、
「ネット環境はあるけど電話番号がない」というケースはだいぶ減っています
ですが、格安SIMでのSMS機能はまだまだ「オプション」扱いであり、
全くないとも言い切れません(´-ω-)
「パスワードの代わり」を「ユーザが選択する」
「年に一度ログインするかわからないレベルのサイト」で、
私が実際にやっていることなのですが、
「あえてめちゃくちゃなパスワードを登録し、ログインの都度リセットする」という手段があります
つまり、パスワードを覚えることを放棄しているわけですが、
冷静に考えれば、これは二段階認証の二段階目と同じようなものであり、
ならば「二段階目のみ」にはできないものでしょうか?
どうせGoogleでもMSでも、ログインしたブラウザでCookieが生きている限り、
再度の(二段階)認証を要求してこないわけですし、
「自分が設定したパスワード(のようなもの)」は必要なのでしょうか(´・ω・)?
・・・ということを先日の朝考えていたら、
夕方にこのようなものが流れてきました
パスワードを使わずトークンで認証する express middleware / “Passwordless - A node.js/express module for token-based logins” http://t.co/H5WD4lazaI
— Takuto Wada (@t_wada) 2014, 10月 17
Passwordless - A node.js/express module for token-based logins
Passwords are broken. Inspired by Justin Balthrop's article Passwords are Obsolete token-based one-time password (OTPW) authentication is faster to deploy, better for your users, and more secure.
https://passwordless.net/
Twilioにも対応しているということは、Gほーさんが(補助的に)やっているような「電話認証」も可能、ということ…φ(・ω・`)
— ぱろっと (@parrot_studio) 2014, 10月 17
今朝の段階では「デバイスの非依存性がほしい」といっていたけど、せめて「複数の手法(メール/電話/etc…)を任意に選んで認証が可能」であれば、十分現実的か・・・ その意味では、この仕組みはベター…φ(・ω・`)
— ぱろっと (@parrot_studio) 2014, 10月 17
要するに、私が(せんせーのpostから)思い当たるような仕組みは、とっくに考えている人がいるってことだよщ(゚Д゚щ)
— ぱろっと (@parrot_studio) 2014, 10月 17
この仕組みのポイントは、認証コードの送り先を任意に選択できる、というところです
Flexible
Deliver your tokens via email, text messages (SMS), or smoke signs. You can embed Sendgrid, emailjs, Twilio, or any other framework you like to get the token to your user.
https://passwordless.net/
つまり、この仕組みを使えば、実装によっては
「ユーザがコードの受け取り先を選択する」ということが可能になります
つまり、「今日は電話を忘れちゃったけど、メールなら使える」という場合に、
メールでコードを送ってもらう、ということが可能になりそうです(`・ω・´)
このフレームワークはnode.jsによるものですが、
同じ仕組みは他の言語でも可能なはずで、
今後こういった仕組みがどんどん出てくるかもしれません
問題点は・・・?
論理的に考えると、「パスワードを捨てる」というのは妥当に見えます
一方で、「パスワードで認証する」というのは「当たり前」であり、
「説明がいらない」という利点もあります
都度メールでコードが送られてくるのは「面倒」なので、
まだパスワードを入れる方が楽だし、もっといえばIDだけでログインできてもいい
こういう層には響きません(´・ω・`)
実際、初期のLINEでは、
パスワードの存在そのものを認識してないユーザが多数いたようです
「LINEのパスワードを忘れた」「ログインできない」が急増している理由とその対策 | LINEの仕組み
特に、最近のスマフォゲーでは、「ユーザ登録が不要」なのが常識*7であり、
「端末移行するための簡易パスワード」くらいなので、
「ログインしている」という認識は薄いと思われます
もちろん、「アプリとWebサイトでは違う」のですが、
今は「Webサイトがあってもアプリからアクセスする」のが一般化しており、
果たして「面倒な仕組み」が受け入れられるのか・・・というのは問題かと
このあたりは「時代の流れ」で決まるもので、
「それが当たり前」になるまでには時間がかかるわけですが、
今ですら、「二段階認証」の存在を認識してないユーザが多いわけですしね・・・
他にも、「仕組み的な穴」もまだあるはずで、
このあたりの議論を進めてもらえると、
「目指すべき方向性」が見えるのかな・・・と思います*8
おまけ:「Digits」に対する疑問点
そして今日、Twitterが新しい認証の仕組みを発表しました
Twitter、モバイルアプリ向け新SDK「Fabric」発表 パスワード不要の次世代認証「Digits」リリース - ITmedia ニュース
電話番号確認方式のユーザ認証をTwitterがデベロッパサービス(一種のAPIスイート)Digitsとして提供 - TechCrunch
これが「ログインのたびに都度電話番号を入れる仕組み」ならパーフェクトだったのですが、
ざっと読んだ限りではLINEと同じような仕組みであり、
「電話番号が変わったらどうするのか?」とか、同じ問題を抱えているようにも見えます
電話帳をUPして結びつける機能もあるようなので、
「以前その番号を使っていた人の知り合いがレコメンドされる」・・・という、
LINEで発生していた問題もあるのではないかと
このあたりは情報がもっと出てこないとなんとも言えないのですが、
さすがにTwitterならそこはクリアできている、
あるいはしてくれると思ってます(`・ω・´)
追記
書き終わってからこのような記事を見つけました
Windows 10はセキュリティキー不要の2段階認証機能搭載に - ITmedia ニュース
まだ詳細はわかりませんが、認証の安全性と利便性を、
どうにかして両立させたいんだな・・・という感じはします
ついでに、Googleの取り組みも(´・ω・)っ
Google、USB使った2段階認証サービスを提供 - ITmedia エンタープライズ
こっちは特定のデバイスが必要という意味でOTPトークンに近いですね
おそらく企業向けを想定しているのかもしれません
*1: ・・・か、どうかについては個々で判断していただいて・・・
*2: と、私が表記する場合は、この分野におけるラスボスである「あのお方」でございます
*3: 現状ほとんどないとは思いますが、今後ありえそうなのは例えばIoT系デバイスの簡易ブラウザとか
*4: これは時間が解決しますが
*5: おっと、アップデートで通信ができなくなった某OSの話はそこまでだ( ゚Д゚)y─~~
*6: 参考までに、Twilioの料金体系 http://twilio.kddi-web.com/price/
*7: 実際、私も「特定サービスへのユーザ登録を要求するゲーム」はその時点で(内容に興味があっても)蹴ってます
*8: 「筋の良い方々」の思考リソースは、こういう方面に使ってほしいのですよ・・・(´・ω・`)
「デザイン」は難しい
別に役に立つ話ではなく、ほとんど愚痴というか言い訳なのですが・・・Σ(・ω・ノ)ノ
先日公開した「チェンクロパーティーシミュレーター」のデザインを大幅に変更しまして
- リリース時の記事
- 関連
- ソースコード
リリース後も機能追加にあわせて頻繁に修正はしていたのですが、
基本的なところから考え直したのは初めてです
当初はデータ(各アルカナの属性情報)が少なく、
「少ないなりにどうごまかすか?」と考えていたのですが、
データがメンテされてきたので、「必要な情報をわかりやすく」に変更したかったのです
変更後がこちら(´・ω・)っ
「おい、たいして変わってないじゃないかщ(゚Д゚щ)」と思われるかもしれませんが、
それは結果であって、ここに落ち着くまで二転三転したわけですよ
大前提として「サマリーの情報を増やす」というのがあって、
それだと元のUIでは検索結果が縦に伸びすぎるので、
ページ送り的なものが必要だろうと*1
で、ページ送りとか横スクロールのライブラリをいろいろ試したわけです
それぞれプロトタイプを作ってみた結果、
「filpsnap.js」がシンプルで私の好みに合っていたし、
違和感も少なかったのです
しかし、これを適用すると「ドラッグアンドドロップ」で表示がおかしくなるのです
できることはできるのですが、copyした要素が裏に回ってしまうという・・・(´-ω-) *2
仕方なく、シンプルなページ送りを自分で実装したわけですが、
次にやりたかったのが「スワイプでページ送り」です
せっかくタブレット対応をうたっているのだから、
やっぱりスワイプで切り替えしたいじゃないですかщ(゚Д゚щ)
スワイプ自体はすでに使っている「hammer.js」でいけます
問題は、スワイプのイベントを(検索結果エリアに)セットすると、
ドラッグイベントが覆い隠されることでしてΣ(゚Д゚)ガーン
海外のフォーラムでもこの問題が挙がっていました
javascript - Draggable code not working with hammer.js - Stack Overflow
結局、ページ送りボタンを大きめにすることで別の対応を入れました
今さら「ドラッグアンドドロップで編集」という概念を変えたくないので、
妥協せざるを得ないところで(´-ω-)
そもそも、「デザイン」って妥協の連続だと思うわけですよ
自分の中に「理想のUI」はあるけど、それを表現するには制約がたくさんあり、
一方で「使う側にとっての使い勝手」も考えなければならず、
それに「明確な答え」なんてないわけで
こういう経験をすると、「デザイナーさんの苦労」も見えてくるわけです
「妥協点探し」は相当大変なんだろうな・・・と (´-ω-)
|ω・`).。oO( 極論をいえば、「プログラム」は「仕様」をどう満たすか考えるだけなので、ある程度「答え」がある だからテストも書ける でも「デザイン」って人の感覚に訴える部分で、明確な答えがない だから個人的にはデザインの方がはるかに難しいと思ふ・・・ )
— ぱろっと (@parrot_studio) September 11, 2014
もちろん、「プロのプログラマ」もさまざまなリソースを加味して妥協しまくりです
でも、「満たすべき仕様」がある程度はっきりしているので、
少なくとも表面上そこだけはクリアする、という基準があるわけです
(でないとコードは書けない・・・ですよね?)
「目に見える部分」だからこその難しさは
実際にサイトを作らないとわからないと思いますし、
たまにはいろいろ試してみてはいかがでしょう(´・ω・)?
*1: 「検索エリアの要素をパーティーエリアにドラッグアンドドロップする」という都合上、ドラッグ距離は短い方がいいというか、長いと使えませんよね・・・
*2: ライブラリの実装方法を調べて原因はわかりましたが、簡単にどうにかできるものではありませんでした(´・ω・`)
天才火消しエンジニア霧島さんのトラップに引っかかった件
今回はいろいろ油断があったわけですが・・・
天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」|paizaオンラインハッカソンLite
・・・って、よく見たら霧島さん=挑戦者=私でしたかΣ(゚Д゚)ガーン
それだと美しくないなので、霧島さん(26歳女性)の依頼で問題を解いたという体にしてですね・・・
とにかく今回は油断があったわけです
- タイトルに「Lite」と入っていた
- たぶん簡単なんだろうと誤解した
- 問題が前回に比べて簡単に見えた
- 前回はまず仕様をどうコードに落とすかが壁で、今回は書くだけなら簡単
- 前回うかつにもSSSを取ってしまった
- http://parrot.hatenadiary.jp/entry/2014/04/25/134010
- だいたいポイントは見切りましたし・・・的な無意識レベルの慢心が
- 前回はプレゼントをいただきありがとうございました(ノ´・ω・)ノミ(m´_ _)m
- 最初に書いたコードでCase5を通過してしまった
- しかも0.02sというかなりのタイムで
特に最後のが致命傷で、「あ、もうちょっとやん」と思ってしまったんですよね・・・
そこからが面倒だったのに(´-ω-)
- コード: https://gist.github.com/parrot-studio/f7770fdfb6b12b472504
- 修正履歴: https://gist.github.com/parrot-studio/f7770fdfb6b12b472504/revisions
とはいえ、前回に比べれば比較的シンプルで、
アルゴリズム勝負になっていたのは間違いありません
問題をどう捉えるか?
最初は1回目*1のような簡単な問題だと思ったのですが、
あれは「ペア」という縛りがあったのに対し、
今回は「任意のn個」(n <= 会社数)の組み合わせが存在します
nが小さいうちは総当たり・・・つまり、
全ての組み合わせについてコストを計算したあと、
条件を満たすデータを探す、という手も使えます
result = [] (1..(companys.size)).each do |n| # n個の組み合わせを全て抜き出す companys.combination(n) do |list| # 人数が足りないなら無視 next if list.map(&:member).inject(:+) < need_member # コストを計算 result << list.map(&:cost).inject(:+) end end # 最小が答え puts result.min
擬似的なコードですっごく雑に書くとこういうことですが、
nがちょっと大きくなるだけでも、
あっという間に組み合わせが発散してしまいます(lll゚Д゚) *2
一方で、ある程度総当たりしないと、
「どれが最小か?」はわからないのも事実です
1回目の時は目標金額が設定されていたため、
ある程度答えが見えたら切り捨てることも可能でしたが、
今回その手は使えません
結果的に、見た目は簡単そうでも、
実際には「高速なアルゴリズムを使う」か、
「適切な足切りを探す」か、その両方かが必要だったのです(´-ω-)
いきなりCase5を突破
以上をふまえてコードを書き始めたわけですが、
前回さんざん苦労させられた結果、
処理速度を上げるポイントはだいたいこんなところだろうと
- データを「リスト」として処理する
- 前回は盤面をbit化し、数値の配列として処理した
- (Rubyの)eachで回すより、indexでアクセスした方が早い
- RubyのEnumeratorは高性能だが、オブジェクトアクセスなので遅い
- とはいえ、Arrayもオブジェクトなので、Cの実装レベルで最適化されている可能性
- 無駄なデータを早めに刈り取る
- 明らかに要件を満たせないデータはそもそも処理しない
- うかつなソートは遅くなる
リストを探索するルートは以下のようになるはずです
1つ目を起点にする 2つ目を足してみる 3つ目を足してみる 4つ目を足してみる 4つ目を足してみる 3つ目を足してみる 4つめを足してみる 4つ目を足してみる 2つ目を起点にする ... 1 1-2 1-2-3 1-2-3-4 1-2-4 1-3 1-3-4 1-4 2 ...
つまり、ツリー構造の探査になります
で、各探査のタイミングで、条件に見合わないと確定したら切ってしまうわけです
ある時点でわかっているコストより、そこで計算したコストが大きければ無駄です
これを再帰的に処理するように書いたのが最初のコードです(´・ω・)っ
- https://gist.github.com/parrot-studio/f7770fdfb6b12b472504/7eeb3bb4d9065c733a43a348b222ea5f6c8f786d
- http://paiza.jp/poh/kirishima/result/3ed226ed924f99208e77cea595699529
この時点でいろいろ考慮されていたのもあり、
最初からCase5で0.02sを叩きだしたわけですが、
ここからが問題でした(´-ω-)
メンバー数で足切りする
計算量を減らすには、「ここより先は無駄である」ということが、
「明確に言い切れる」条件を探す必要があります
今回の場合、この「明確に言い切れる」の部分が難しいのです
まず思いついたのが、「メンバー数」です
あるノードを見ている時に、あと20人必要だとしても、
その先の全ノードを足しても20人に満たないならそこで切り上げることができます
- https://gist.github.com/parrot-studio/f7770fdfb6b12b472504/ef6fbc2cd92053a0dbca188b3a51a88c71506fd4
- http://paiza.jp/poh/kirishima/result/04030b70baad1928a36adfb7963e88cb
しかし、「この時点では」無駄でした(´・ω・`)
深さで足切りする
先ほどのcombinationを使った擬似コードにおいて、
例えばn=3の時点で答えの候補が見えているのであれば、
n=4でそれより小さい値が見つかるとは思えません
そこで、「深さ」の概念を追加してみたわけですが、
元々ツリーの途中で適切な足切りが実装されており、
あまり効果がないどころか、むしろループを増やすだけでした(´-ω-)
- https://gist.github.com/parrot-studio/f7770fdfb6b12b472504/3feb7eb1f9b3482a9bc5711fc03889e09c8c63af
- http://paiza.jp/poh/kirishima/result/7c3b1a804dc2b128ff4cdacd621e83cb
そもそも、nが大きい場合に、
n=2とか3で組み合わせ数が爆発する問題は解決しないわけで・・・
試行錯誤
この辺から完全に行き詰まったのですが、
やはり複雑なデータ構造を作るほど遅くなるため、
どうにもうまくいきません
問題が良くできているので、「一か八か、データ依存」的な条件を追加しても、
今度はCase5すら通らなくなるのです
コスト効率を考える
ここでいったんしばらく時間をおきまして、
一度頭をリセットしてやり直しました
冷静に考えると、足切りするには何らかのソートが必要です
でも、今回はデータのベクトルが「メンバー数」「コスト」の2次元なので、
どちらかの概念でソートしても、足切りがうまくいかないのです
ならば1次元化、つまり「コスト/メンバー数=コスト効率」でソートすればと、
一度は考えていろいろ試したのですが、決定打がありませんでした
しかし、冷静に考えれば、「コスト効率×メンバー数=コスト」です
もしコスト効率でソートされている場合、
ある時点での「コスト効率×残りメンバー数+現時点でのコスト」が、
最小値を超えてしまうのであれば、それ以降の計算は無駄です
例えば、あるノードの時点で
「わかっている最小コスト100、コスト効率1.2、残り20人、現時点でのコストの和が80」
だとします
すると、「次のノードのコスト効率」は1.2以上であることが保証されており、
コストが「80+1.2*20」以上になることが確実です
なので、ここで切り上げてしまっても問題ないことになります
- https://gist.github.com/parrot-studio/f7770fdfb6b12b472504/9bfde259135e8689fbae3c2274ae1f3b994fdf13
- http://paiza.jp/poh/kirishima/result/d89160ddb3129940a31a502afb5b5e75
これを追加したところ、Case6を突破しました(`・ω・´)
もう一度メンバー数で足切り
先ほど一度は棄却した「これ以降はメンバー数を満たせない」という足切りですが、
今度は一次元の概念でソートされており、
うまく寄与するのではと予測しました
ついでに、コスト効率に関してももうちょっと見直しまして・・・
- https://gist.github.com/parrot-studio/f7770fdfb6b12b472504/124936a370734bff364544c20a2615d123a7fb03
- http://paiza.jp/poh/kirishima/result/fa999e57b33527ff7dbbaefb67620f7e
・・・Case7を突破し、S評価を獲得ですヽ(`・ω・´)ノ
まとめ
実は、前回の2回目で行き詰まった際、
「次元を落とす」というのを試していました
前回はうまく当てはめることができなかったのですが、
今回の場合はまさにぴったりだったようです(`・ω・´)
逆に、このような1次元化を導入したので、
探査ロジックを見直すことで、
まだまだ数秒縮められる気がします
「起点」という考え方を捨てて、
全体を一つのツリーとして見なせば、
ループを削れるのはわかっているのですが・・・
(まさにこれを書きながら気づきました
前回もそうだったのですが、「行き詰まったらBlogに書いて整理」というのも、
一つの手法かもしれません)
・・・暑いし、やることが他にある*3し、あとはお任せしますΣ(・ω・ノ)ノ
*1: https://paiza.jp/poh/ec-campaign 私のコードはこちら(´・ω・)っ https://gist.github.com/parrot-studio/7763295
*2: ちょっぴりグレーな方法・・・適当なところで例外を上げるようにしただけ・・・で確認したところ、Case5まででだいたいn=10、Case6でn=30程度でした おそらくCase7は最大のn=50でしょう
*3: 「チェンクロパーティーシミュレーター」を開発中です(´・ω・)っ http://parrot.hatenadiary.jp/entry/2014/07/15/142913
「チェンクロパーティーシミュレーター」を公開しました
昨年からだいぶはまっていた「チェインクロニクル」ですが、
そのパーティー構成を編集して共有するサイト、
「チェンクロパーティーシミュレーター」を公開しました
Get our light! - チェンクロパーティーシミュレーター
(現時点ではまだβ版としています)
- 関連
- ソースコード
経緯
セガさんが「サポーターサイト」というのを募集し始めまして、
素材利用申請をしようとしたところ、
まずサイトを登録する必要があることが判明しましてΣ(゚Д゚)ガーン
そこでBlogでも書き始めようかと思ったのですが、
あまりしっくりこなかった*1ので、
いろいろ考えた結果、こういうサイトになったという・・・
元々、私はROを長いことやっていて、
こういった便利ツールにはさんざんお世話になったのもあり、
チェンクロでも何か作れないかな・・・と
アーキテクチャ
今回のサイトはできるだけブラウザ上で完結させることを目指しましたが、
それ以上に「タブレット*2での動作」を意識しました
ずっと「PC向けだけど、たまたまタブレットでも動く」ってサイトばかりだったので、
「タブレットで "快適に" 動く」というのはやったことがなかったのです
時代的にPCよりタブレットやスマフォデバイスがメインになってますし、
そもそもチェンクロ自体、タブレットでプレイしているわけで、
タブレットで動くのは必須だろうと
タブレット向けに調整するまでのメモ
サーバ側のAPIは(得意分野なので)あっという間にできたものの、
そこからView側を調整するのにひたすら時間がかかりました(´-ω-)
せっかくなので、引っかかったポイントを覚えている範囲でメモしておきます
1. clickイベントの動作
ボタンでもリンクでも、たいていのものは「クリック」できるわけで、
clickイベントは相当使いまくります
$("#search").on 'click', (e) -> searchTargets() e.preventDefault()
例えば「検索ボタン」のコードがこれですが、
PCだけ考えればこれで十分すぎます
でも、このままタブレットで動かすと、
タップしてからの反応が恐ろしいほど遅いです
「あれ? 動かない?」と思う程度のラグがあります(´・ω・`)
原因はモバイルブラウザにおけるイベント処理にあるわけですが、
モバイルブラウザで「click」イベントを処理する前に、
大量のイベント判定をしているようなのです
http://patrickhlauke.github.io/touch/tests/results/
そこでいろいろ調べてみたのですが、
touchstart/touchend等できっちり書くやり方は面倒すぎるので、
もっと楽な方法はないかな・・・と
そこで見つけたのがこれです(´・ω・)っ
これを読み込ませて、先ほどのコードをこう直します
$("#search").hammer().on 'tap', (e) -> searchTargets() e.preventDefault()
すると、PCではclick、タブレットでは「それっぽいタップ動作」になり、
非常に簡単ですヽ(`・ω・´)ノ
Railsに組み込むためのgemもあります
https://github.com/vincent-pochet/hammerjs-rails
2. ドラッグアンドドロップの実装
いつもの私ならこの辺でリリースレベルなので、
データの入力とかちまちま進めていたのですが、
試しに会社の人*3に軽くいじってもらったところ・・・
「ドラッグアンドドロップができないのが違和感」
・・・と言われましたΣ(゚Д゚)ガーン
元々、「候補をクリック -> PT欄をクリック」という操作だったのですが、
このデザインだと「(アルカナ自体を)動かしたくなる」、と
最初に設計していた時点で、「ドラッグアンドドロップ」は考えていたものの、
とりあえずプロトタイプを・・・ということでスルーしてしまったのですが、
やはり対応しないとダメでした(´・ω・`)
これもやり方はいろいろあるものの、
面倒なのでjQueryUIを使うことにしました
ただ、さっきのclickイベントより深刻で、
PCで動くように実装しても、タブレットでは全く動きませんΣ(・ω・ノ)ノ
そこでまた調べたところ、「jquery.ui.touch-punch.js」というのを発見
こちらは読み込ませるだけでタブレット対応できてしまうので、
hammer.js以上に簡単です(`・ω・´) b
ただ、hammer.jsと同時に使う場合、
裏で使っているイベントが競合する場合がある*4ようで、
イベント登録する要素を工夫するとか、気をつけないといけません
3. デザイン周り
プロトタイプからたぶん3周くらい回って今のUIにしてますが、
それでもまだ微妙な感じがします(´-ω-)
チェンクロは「横画面のUI」で、アルカナは「縦表示」なので、
そこをデザインの基本にしました
ぶっちゃけ、アルカナを横長にして縦に積み重ねた方が、
デザインを考えやすかったのですが、
やはりゲームにあわせたかったので・・・
一方で、Twitter経由でサイトを見た際に、
Twitterはどうしても縦画面で見るのもあって、
やはり違和感がある、という意見もいただきました
せっかくBootstrapを使っているわけで、
画面の幅に合わせてデザインを変えられるのがベターですが、
まずは基本的な部分だけリリース、ということで、一つ(´・ω・`)
"全部"対応してから・・・とかやっていると、
いつになってもリリースできませんからね・・・
一方で、「どこを最小限とするか?」は、
「これは何をするためのサイトなのか?」が定義されていないとわからないので、
やっぱりコンセプト設計は大事です*5
追記
そもそもPC/タブレットを想定していたとはいえ、
それ以外のデバイスで画面がめちゃくちゃってのも気分が悪いので、
閲覧機能だけ暫定対応しました
「タッチで操作する」という前提なので、
スマフォの縦長画面だと操作しづらいのは見えているのですが、
どうしたものですかね・・・(´-ω-)
それにしても、classを指定するだけで、
ここまでさくっと表示/非表示やデザインを変更できるあたり、
やはりBootstrapはすばらしい・・・