長文書くところ

技術系のアウトプットとかメモ書きとか

ICFPC 2019 参加記

ICFPC 2019にチームdot cubeとして参加した. dot cubeは私が所属する宮崎大学のプログラミングサークルの名前. チーム全員,ICFPC初参加.

メンバー

  • zenito (私)
  • kai
  • Takahiro55555
  • twugo

今回の我々の目標は,「正の点数を取ること」とした. 私以外のメンバーは,長時間でのコンテストは今回が初めての参加. ICFPCは基本的にスタートラインがめちゃくちゃ遠いコンテストなので,最悪ビジュアライザだけ作って手動で解くのでもよしって感じ. ゲーム制作はある程度みんな経験があるので,まあビジュアライザなら作れるでしょって気持ち.

チームでのコンテスト参加は初だけど,全員ハッカソンへの参加経験はあるので,チームでの情報共有はわりとすんなり決まった. 会話はSlack,データ共有はDropbox,タスク管理とか情報共有はTrello.

以下ログ.Slackの会話とか見ながら記憶を頼りに書いているので,ところどころ怪しい気もする.

初日 (6/21)

AM 10:00
開始時刻を9時間間違える(今年の開始時刻は 6/21 AM10:00 (UTC) ).そういえば日本に住んでいましたね. Rustで書くつもりなので,structoptとかreqwestとかの使い方を見たり,Slack botの作り方入門したりして過ごす. なお,最終的にstructoptしか役に立てられなかった.

PM 7:00 以降
開始.問題を読む.TOEIC最低点180点な集団なのでみらい翻訳に投げ込む作業. なんかすげー普通のマラソン問題っぽくない????実行時間制限もコンピュータリソース制限も無いマラソンをチームで3日間でやる感じ. とりあえず入力がやたら扱いが面倒な形式なので,みんなで夜ご飯食べながら,入力をグリッドに変換する方法を考える. グリッドへの変換プログラムを私がRustで書き始める. 残りのメンバーはみんなでビジュアライザを作り始めた (Python in Processing).

深夜2時ごろにグリッドへの変換ができるようになって,ようやくスタートラインに立てたぞ〜って盛り上がる. 一段落したので帰宅.

なお,このグリッドへの変換がバグっていて,2日目3日目のかなりの時間を浪費する. 見やすいビジュアライザを自前で作るのって大事ね.

2日目 (6/22)

私以外の人々はビジュアライザ制作の続き. 私はAIの制作に入る.マニピュレータの視線の判定のために,グリッドに直線を書くアルゴリズムを調べる. ブレゼンハムのアルゴリズムばっかり出てきて困る.近似されると困る.結局teratailにドンピシャなやつがあったので,参考にしながら実装した. なお,結局最終日まで全くブースターに対応しなかったので,これは完全に無駄になった.

視線に対応できたので,とりあえず動きのシミュレーションを実装する.気合でゴリゴリ. 一発書きでも全然バグが出ないRustは最高.盤面カバー率が高い方を優先するビームサーチ(1手だけ進める遷移)を書いて,全く解けねえ〜って悲しくなる. このAIをaragogと名付ける.枝がたくさん伸びるため.

途中でいろいろルールが追加されているものの,初日のルールですらまともに解が作れていないし,ルール見た感じ探索空間がめちゃ増える感じだったので,とりあえず新ルールたちは無視することにする. Lightningが終わって,なにやらルールにマイニングという文字が見えたものの,まあ無視していいでしょっつってもはやまともにルールすら読まずに無視.

aragogのビームサーチの改良を考える. 遷移で1手しか進まないので,角とかですでに塗ったマスに囲まれるとランダムムーブしかできないな〜って思ったので,評価関数に「一番近い未到達マスまでの直線距離」を含めることにする. いい感じに進むものの,直線で進もうとするのでハマりまくってダメ.ということで,bfsして「一番近い未到達マスまでの最短移動距離」を求めることにする. 実装するものの,めちゃくちゃ重くてまともに探索できない.

めちゃ強い雨が降り出して帰れなくなり,3時くらいまで作業.

とにかく正の点がとりたいので,マニピュレータも回転も完全に無視して,己の通った道のみで盤面を全部埋めるbfsを書く.一番近い未到達マスまで最短で移動するだけ. このAIをdementorと名付ける.適当にターゲットを定めてそこまでグワーッと行くため. とりあえずこれで正の点が獲得できるようになって,深夜3時ごろに初めての提出.99位になって,やった〜2桁順位だ!と盛り上がる. これがチームとしての最高順位になった. 一段落したし雨もやんだので帰宅.

なお,グリッド生成がバグっているので,51番以降の盤面で途中で壁に突っ込んで死ぬ. グリッド生成側のことをまったく疑っていないので,延々とbfsのバグを探し続ける.今考えればめちゃくちゃ時間を無駄にしてしまった.

3日目 (6/23)

私以外のメンバーはビジュアライザ制作の続き.

私はaragogのビームサーチを改良. 前日に実装したbfsがバグっていて,visitを保存していない(!)とかいうゴミみたいなミスをしていた. 直したらかなりまともに探索できるようになって,50番までは時間をかければまあまあマシな解がつくれるようになった(まあ評価関数がヘボなのでアレなんですけど……). 相変わらずグリッド側がバグっているので51番以降は死ぬ.

ラソンマッチのブログ記事とか読んでたら,ビームサーチは遷移が大事,必ず評価の上がる遷移を考えろ,とのことだったので,それをやることにする. とりあえず,1手しか進めないで評価するのはめちゃくちゃダメじゃね?って気持ちになって,5手分全部の動きをしてみて評価するようにしてみる. めちゃくちゃ重くなったけど,ちょっとは良くなった.

公式ビジュアライザで動きを見てると,結構近場の未到達マスを見逃して後から取りに戻る動きをしている. うーんちっちゃいマスなら多分最適解が作れるんだろうな〜と思って,それを繋げたりするときれいに塗れるな〜ってぼんやり考える. しかし悲しいことに,それを実装できるだけのアルゴリズム力は自分には無いのであった…….

夜になって,最初に自分のいたマスを到達地点として塗るのを忘れていたバグに気づく.変な挙動がそこそこ取り除かれる. また,チームメンバーが作っていたビジュアライザが完成して,ようやくグリッドの生成がバグっていることに気づく. ビジュアライザを自前で作るのって大事ね.

最終日 (6/24)

3日間のコンテストなのに4日目で頭がバグるね.

月曜日なので,チームメンバーは講義があって動けず. 自分は講義なし.

とりあえず,5手全探索のaragogを自宅のデスクトップマシンで10並列で回す.12時間以内に解き終わるかどうかのお祈り. ……だったはずが,残り3時間になった時点で,修正されたグリッド生成プログラムでグリッドを生成し直していないことが発覚.もう時間的に無理や……と絶望する. グリッドをちゃんと生成し直す.

とりあえず自分ができることの最善策として,dementorをマニピュレータに対応させる. 拡張も回転もまったく考えないので,一瞬で対応できる. また,bfsの探索順を,これまでは左側から開始する時計回り方向だったものを,下→左→右→上の順で探索するように修正. これで下の方を重点的に攻めるようになって塗り残しが減り,prob-297の手数が1万手近く減った.

aragogで解ける範囲のものはできるだけaragogに解かせたいので,時間いっぱいaragogを回す.めちゃくちゃ時間がかかるので,4並列でギリギリ. aragogとdementorの解のスコアを比較して,いいほうだけを提出用ディレクトリにコピーするスクリプトを書く. 提出期限の19時が迫る中,シェルスクリプトと格闘しながらaragogの計算が無事終わるのを祈り続ける. 18時58分に提出完了して,初ICFPCは無事終了!

感想

悔しい〜〜〜〜〜〜〜〜〜! 私にもっとアルゴリズム力やら実装力やらが備わっていれば……って気持ち. 終了後のTLを眺めてたら,まさにやりたかったこと(小さい範囲で区切って最適解構成,それらを2-optでつなぐ)をやっているチームがいて,いやそれだよそれそれ〜!ってなるなどした. 小さい範囲での最適解構成,どうすればいいんだろうなあ…….

また,盤面の評価値をどうつければいいか,どう遷移させればいいか,も全く考えつかなかった. そもそも遷移をまともにするにはまともに評価値をつけられなければならない(気がする)ので,そういうのをもっとうまくなりたい.

チームでの参加について.多分1人での参加だと途中でやる気を失っていただろうと思うので,やっぱりチームでやるってのは楽しい. 欲を言えば,コード書いたらいい感じに自動でタスクを流したり,定期的にこれまで得られた一番いい解を提出したりする環境が作れると,いろいろ実験を回せたりするのかなあ……と思う. まあ,そもそものアルゴリズム力が無なのでそういう環境があったとしても無な気はするけど……. 個人的にインフラ側にも結構興味があるので,Jenkinsとかを触ってダッシュボードっぽいの作ったりしてみたい.自分が探索とかを書かなくても大丈夫にならないとそこまで手が回らないけど. でもJavaScriptを書く気は全く起きないので,早くWeb Assemblyがすべてを解決してほしい.Rustで全部終わるようになってくれ. シェルスクリプト力も足りないので,いろいろ強化すべき点だらけだなあ.

全体として,もっともっと実装力アルゴリズム力をつけたいねって感じ.私自身も,チームメンバーも. チームメンバーが基本的にあんまり探索とかに明るくないっていうのはわりとつらくて,AIとかを考えるときに全部一人でやらなくちゃならない. ビジュアライザを複数人がやってるってのもなかなか無駄が多い面があると思うので,やっぱりそれぞれが得意な分野をもっているようなチームのほうがいいよなあって思う. まあ,チームが組めるというのはそれだけでかなり恵まれているので,時間を割いてくれたチームメンバーには感謝の嵐なのだけど.

悔しいところが多かったけど,やっぱり長時間のコンテストは楽しかった.今回は追加ルールを完全に無視したので,次に参加するときは,追加ルールも楽しみたい.

マラソン系プログラミングコンテストページを立ち上げた

ラソンマッチってご存知ですか?
競技プログラミングの一種で,よく知られている短い時間でのコンテスト(アルゴ系とも言われますね)とは違い,数日間から数週間にわたって開催されるコンテストのことです.もとはTopCoderMarathon Matchだと思うんですが,長い時間で開催されるコンテスト全般をマラソン系と呼ぶことが多い気がします.

そんなマラソン系コンテストの一種で,かつてCODE RUNNERというコンテストが行われていました.たしかリクルート主催?だったと思いますが,2015年の開催の後,今や公式サイトすら開けなくなってしまっている状況です. 私はこのCODER RUNNER 2015の予選Aの開催時にリアルタイムで参加していて,当時の実力では全く歯が立ちませんでした.いつか復習したいなと思い続けるうちに時は流れ,今やちゃんとしたルールの確認すらできなくなってしまいました.

そこで,うろ覚えながら当時の提出形式や問題設定を再現し,いつでもどこでも(私が大学とかで外にいることも多いので……)復習できるようにしてみました.

URLはこちらです.
https://nocross-zenito9970.herokuapp.com/

コンテストの形式

TopCoder MMやAtCoderなどでのコンテストとは違い,解答の提出はソースコードを提出しません.特定の形式のURLに対して,HTTP(S)でGETリクエストを送ることによって,サーバがそのURLを読んで解答を処理します.つまり,ユーザーが手元で計算して解答を作成し,その解答の良し悪しを競う,という形です.

ユーザー登録をすると,提出のためのアクセストークンが発行されます.ユーザー名とアクセストークンをURLに含めることで,ユーザー認証としています.この仕様はたしか当時の形式でもこんな感じだったと思います.ただし,当時は普通にアカウントの概念が別にあって,そこからアクセストークンの発行ができたはずです.今回はページとか諸々が面倒だったので,registerを叩くとそのままアクセストークンが発行されるようにしました.

実装

サーバはRustで書いています.これは私が最近Rustを練習しているからです.趣味です.
webアプリケーションフレームワーク(というかルーティングとかやってくれるやつ)はwarpです.テンプレートエンジンにhandlebarsを使っています.ただし,warpでStringをブラウザに送りつけるとChromeくんが頭おかしい動作をしたので(pre タグの中にテキストとして埋め込んでしまい,ソースコードがドバーッ),定期的にHTMLファイルを生成してそのファイルを返すようにしています.

ランキングとかアクセス時間の保持とかは全部Redisに投げています.この辺自分で書くと面倒な上にバグの元ですし,永続化やらなんやらがひたすら手軽でとても良いです.

WebページのレイアウトとかはBootstrapに任せました.かなりAtCoderに似た見た目になっていますが,見やすいのでまあこうなるよなあと思いました(適当に作ってたら無意識に似てしまいました).

ホスティングにはherokuを使いましたが,これはheroku containerでDockerイメージをホストしています.もともとArukasを使うつもりだったんですが,正式版リリースでクレジットカードがないと使えなくなったみたいだったのでherokuに変えました.

herokuの無料枠は30分アクセスがないとスリープしてしまうので,Google Apps Scriptで15分ごとにリクエストを送りつけています.無料枠ってどのくらいの時間大丈夫なんでしょうね.インターネッツの情報は錯綜しすぎていて,なにを信じればいいのかわかりません.いい感じだったらそのうち課金するかも.いまのところherokuのスペックは所詮無料枠なので,何十人もがリクエスト投げるのは無理じゃないかなーと思っています.

Dockerイメージはalpineベースですが,これはローカルのストレージを圧迫されたくないからです.Ubuntuとかのイメージの圧倒的デカさの前には,macの256GBストレージでは太刀打ちできません. ekidd/rust-musl-builder でstatic linkなバイナリを生成して,それをalpineにCOPYしてます.

herokuもDockerもちゃんと触ったのは初めてなんですが,めちゃくちゃ手軽にできて良いですね.

その他のこと

これはコンテストとしてめちゃくちゃ致命的だと思うんですが,ランキングは24時間くらいに1回リセットされます. heroku無料枠の仕様で,マシンが定期的に再起動されちゃうんですよね.別のサーバにデータを投げたりすればいいと思うんですが,無料で使えていい感じのとこを見つけてないのでやってないです.Dockerイメージ的にはRedisのバックアップデータを永続化する仕組みを作ってはいるので,やろうと思えばいつでもできると思います.

あと,「No Cross」っていう問題名とか,問題設定自体とかがCODE RUNNER 2015 予選Aの問題そのもの(だと思う)なので,権利的にマズかったりしたら言ってください.すぐ消します.

うらら迷路帖における「祝詞」

この記事は 『うらら迷路帖 Advent Calendar 2016』 13日目の投稿です。

うらら迷路帖では、主人公たち「うらら」が占いを行う際、道具を用いたり、呪文を詠唱したりします。
作中で、道具は「占物」、呪文は「祝詞」と呼ばれます。それぞれ「うらもの」「のりと」と読みます。
今回は、作中で描写のあった祝詞を並べてみたいと思います。祝詞暗唱はうららへの第一関門です。
f:id:zenito9970:20161213201812j:plain

各巻ごとに見ていきたいと思います。まずは1巻です。

――東西東西皆々さまに さあさあ八卦の八つ当たり さてこのたび占いまするは かの温かき手の持ち主の 吉凶禍福のひとわたり かくも占々進ぜましょう さあ教えて茶の葉たち!

――奇々も怪々お尋ねします こっくりこっくりおいでませ もしもおいでになられたら どうか答えてくださいな

――四方八方夜空の包む 四十八の願い星 叶い叶わぬ夢のささゆき 暗闇渡りてお尋ねします


1巻は3つで、最初にしては意外と数が少ないですね。最後の数字の部分は人数×12になっているものと推測できます。また、最初の祝詞の「さてこのたび占いまするは~」に続く節は、占う対象によって変化すると思われます。
次は2巻です。

――かしこみかしこみお頼み申す 探しあそばせ彼の人の 赤い糸引く想い人 振り子揺り揺り恋心!

奇々も怪々お尋ねします こっくりこっくりおいでませ もしもおいでになられたら どうか答えてくださいな――……

――奇怪面妖御返しします こっくりこっくり恩返し 行きはよいよい帰りは怖い さばえさばえと帰りゃんせ! (お願いします帰ってください!!)

(――苦しみ惑い彷徨える子羊よ ミス・プラムの名においてそなたを占い導こう エロイムエロイムエッサイム我は求め訴えたり! 吠えろグリモワール!)

――知ぃらぬは教えておくんなし ねんねーこくぅるり寝惑い子 くぅらり目眩るる暗闇の 夢に潜むるゆーめあらし

――神様どうかお尋ねします こっくりこっくりおいでませ 心無き願いを占いに もしも奪いはしないなら どうぞ繋いでくださいな

――畏み畏み申し上げます 映し見水鏡現し身の 水底深く澄み渡り 隅から隅へ見透かして さああなたのすべてを視せて


括弧で囲った部分は詠唱かどうか怪しい部分です。ミス・プラムの詠唱は完全オリジナルかつデタラメなので全て囲っています。
2巻では7つと、1巻の2倍以上の詠唱シーンがあり、現在刊行されている単行本全3巻のなかで最も詠唱の多い巻です。また、千矢・小梅・ノノの初詠唱巻でもあります。時江さんの詠唱が見られるのもこの巻です。
1巻に見られたような、対象によって言葉を変える祝詞は登場していませんが、非常に用途の狭そうな占い(「もしも奪いはしないなら~」)が登場しています。過去にも見られた事例として伝わっているのか、オリジナルの祝詞なのかはわかりませんが、十番占でも占いなどの能力自体を対象にする祝詞を扱うことができるようですね。
さらに、この巻では次のような祝詞も登場します。

ひとふたみよ いつむななや ここのたり ふるべゆらゆら ふるべゆら

詠唱(歌唱?)があったのは冒頭3節のみですが、絵の書物から読み取ることができます。
f:id:zenito9970:20161213201838j:plain
作中では、この祝詞は「天の数歌」だと説明がありますが、調べてみたところ(信用に足るか怪しいサイトばかりという印象でしたが……)実際に「天の数歌」として伝わっているのは次のようなもののようです。

ひとふたみよ いつむゆななや ここのたり・もも ち よろづ

数え歌だとすると、たしかに後半は「ふるべゆらゆら ふるべゆら」よりも「もも ち よろづ(百 千 万)」のほうが適切な気がします。語呂は前者のほうがよいので、はりかも先生のアレンジかもしれません。

次は3巻です。

ミス・プラムの名において命ず ゆらり揺らめく振り子の女王 ユレール・フレール・マドモアゼル 我ら迷える子羊を導きたまえ!

語り継がれし形代の 人形語りもーのがたり 我ら傍らの片割れよ 知識を授けてくぅれまいか

奇々も怪々お招きします こっくりこっくりおいでませ この身を差し出す御代わりに どうか応えてくださいな!

(――視えた 七つの扉の右から二番目 赤絨毯の道罠四つ 三叉路真ん中突っ切って 階段登って突き当り)

迷い問い問い的を射る 我ら問うるはささゆきの 教えを請うるゆきさきへ 導きたまえ白羽の矢!

――眠りねむるる我が眼 目蓋の裏に映るるは 嘘か真かまぼろしか ゆめゆめ御見逃されるな


3巻は6つです。この巻では九番占試験での詠唱がメインなので、2巻までの詠唱で見られた冒頭の「――」が無いものが多いようです。

3巻までの祝詞を並べてみたところ、七五調になっているものが多いようです。詠唱するうえで、リズム感があるととても覚えやすいですね。しかし、最後の節では七五調が崩れているものもいくつかあります。上位のうららか、才能のあるうららが扱う祝詞によく見られるようなので、物語が進むと頻繁に登場するかもしれませんね。

終わりに

いかがだったでしょうか。うらら迷路帖といえば、非常に印象的で力の入った詠唱シーンが特徴なので、これからの物語でも楽しみですね。占物はまだ登場数があまり多くなく、詳細もはっきりしませんので、次巻以降やアニメで補完があったりするかもしれません。

うらら迷路帖のアニメは1月頭から放送開始です。BSでも放送があるのは地方民にとって救いですね。
原作を読んでいない方も、ぜひチェックしてみてください。もちろん原作もおすすめです。

それでは『うらら迷路帖 Advent Calendar 2016』、次の記事は16日のyaplusさんの投稿です。
ありがとうございました。

msys2 の裏にコマンドプロンプトが開くようになって気持ち悪いので直した

windowsでmsys2をメインに使ってるのですが、いつからか起動時に裏でコマンドプロンプトが開くようになって、気持ち悪いし悲しいので直しました。

一発で直る場合

  1. pacman -Syuu する
  2. msys2 のインストールフォルダにmsys2.exeがあるのでスタートメニューに登録

上記で直らない場合

  1. msys2 をアンインストール
  2. MSYS2 installer (https://msys2.github.io/) からインストーラをダウンロード
  3. 普通にインストール
  4. 起動->終了を2回繰り返してPC再起動
  5. 以下の操作をする
$ pacman -Sy
$ pacman --needed -S bash pacman pacman-mirrors msys2-runtime
(msys2 shellを再起動)
$ pacman -Su
(msys2 shellを再起動)
(ここまででmsys2起動時に裏にコマンドプロンプトが出てくるようになる)
$ pacman -Syuu
  1. 最後のコマンドで msys2 のインストールフォルダに msys2.exe が作られるので、それをスタートメニューに登録

自分はこれで治りました。
お疲れ様でした。

参考文献
MSYS2を試してみる - kashiの日記 (http://verifiedby.me/adiary/055)

Windowsのターミナル環境にCmderを使う ~Nyagosとmsys2を添えて~

僕の開発環境はwindowsに構築されています。
当然コードを書くのはwindows上だし、コンパイルするのもwindows上です。
ファイル操作はエクスプローラもターミナルも使い分けます。

さて、windowsのターミナルといえば、あの"cmd.exe"ですね。
f:id:zenito9970:20150619163238p:plain
こいつが非常に低機能で、なんとウィンドウサイズの変更も満足にできません。
そんな環境のターミナルでファイル操作なんかを行おうものなら、僕は将来育毛剤を使わないといけない体になってしまいます。
そんなことは丁重にお断りさせていただきたいので、windows上で快適に使えるターミナル環境を探していました。


最初に触ったのは、おなじみのCygwin
f:id:zenito9970:20150619163244p:plain
まあ、これで僕は概ね満足していたわけです。
見た目があまりクールじゃないという点と、パッケージの追加が面倒という点を除けば。


次に触ったのは、msys2です。
f:id:zenito9970:20150619163312p:plain
こいつはとてもいい環境でした。Cygwinで出来ていたことに加えて、pacmanでパッケージの追加ができるのです。
見た目はあまりクールではありませんが、これもだいたい満足できていました。


三番目に触ったのは、ckw+Nyagosです。
f:id:zenito9970:20150619163254p:plain
ckwがコンソール代替ソフト、Nyagosがシェルになります。
NyagosはNyaosの後継にあたり、Go言語で書かれています。
これは、あまり満足できるとは言えませんでした。
ckw自体は軽くてクールで良いソフトなのですが、Nyagosと合わさるとどうにも遅くなる時があるのです。
また、ckw自体がvimの利用をあまり考慮されておらず、カラースキームの色が狂ったり、背景色の番号が狂ったりと、環境としてはそこまでいいものではありませんでした。


四番目に触ったのは、ConEmu+Nyagosです。
f:id:zenito9970:20150619163258p:plain
ConEmuがコンソール代替ソフト、Nyagosがシェルです。
これはそこそこ良かったのですが、見た目が気に入らず、あまり満足できませんでした。


最後に辿り着いたのが、Cmder+Nyagos+msys2です。
f:id:zenito9970:20150619163318p:plain
Cmderがコンソール代替ソフト、Nyagosとmsys2がシェルです。
CmderはConEmuの改良版にあたります。
このCmderの導入に難儀し、Cmderの上でmsys2を動かすのに難儀しました。
しかし難儀の甲斐あって、Cmderは非常に使いやすいターミナルで、見た目も非常にクールでした。
動作は軽く、vimは快適に動く。これが僕の目指したターミナルです。
さて、導入に難儀したこの環境、もし環境を移行する必要がある時、また難儀しないために、ここに導入の手順やその中で躓いた点、その解決法などを残しておきたいと思います。
なお、ここではcmderを持ち運ぶことは一切考えていません。ポータブルにも出来るようですが、他の環境で使う予定は特にないので。

Cmder+Nyagos+msys2の環境を構築する

まずはcmder,nyagos,msys2のそれぞれのバイナリをダウンロードしてきます。

cmder:gooseberrycreative.com

nyagos:github.com

msys2:
https://msys2.github.io/msys2.github.io

cmderはfullを入れましたが、miniでも大丈夫だと思います。
cmder,nyagosはそれぞれ好きなディレクトリに展開し、msys2はインストールします。

とりあえずcmderを起動しましょう。
起動出来ましたか?僕は出来ませんでした。
最初から起動できる場合もあるようです。

さて、最初の難儀したポイントはここです。
とりあえずエラーメッセージは僕の場合こうなっていました。

api-ms-win-appmodel-runtime-l1-1-0.dllが見つからなかったため、このアプリケーションを開始できませんでした。
アプリケーションをインストールし直すとこの問題は解決される場合があります。

はい。dllを入れれば解決やん!って思いますが、このdllを探すのに苦労しました。
めんどくさいことは抜きにして、解決策を書きます。
Download Visual Studio 2015 RC の Visual C++ 再頒布可能パッケージ from Official Microsoft Download Center
ここからVS2015RCのランタイムをインストールすれば起動できるようになりました。
フォントの設定からMonospaceのチェックを外さないと、日本語の表示幅が合わずおかしくなります。

無事にcmderが起動出来ましたか?
ここでまた難儀ポイントです。
起動した時、僕の環境ではPowerShellが呼び出され、Pathに何かを追加するのに失敗していました。
これを解決したかったのですが、どうせPowerShellは使わないので、放置して構いません。
PowerShellを使う人は頑張って直してください……。
また、ConEmuがコマンドプロンプトの代わりに起動するように設定していた場合、"ConEmuのバージョンが違うよ"みたいなエラーが出ます。
設定を解除しておきましょう。

次に、cmderからnyagosを呼べるようにします。
Startusの中のTasksで、左の一覧の下にある「+」ボタンで項目を追加し、Commands欄にnyagos.exeへのフルパスを記入します。
Group(数字)となっている欄をNyagosなどわかりやすい名前に変更します。
お好みでDefault task for new consoleにチェックを入れましょう。
その後、Startupの項目を選択し、Startup optionsのラジオボタンでSpecified named taskを選択、先ほど作ったnyagosを選択します。
これでSave settingsを押し、再起動すると、最初に立ち上がるのがnyagosになっているはずです。

さてお待ちかね、cmderからmsys2を使えるようにします。
さきほどのStartupのTasksで、「+」ボタンで追加するところまでは変わりません。
その後msys2へのフルパスを記入する際、

(msys2のインストールディレクトリ)\usr\bin\mintty /usr/bin/bash --login -i

としてください。
こうすると、msys2を不完全な状態で呼び出せるようになります。

ここで難儀ポイントです。
こうやって呼び出したmsys2は不完全です。
vimの起動やらなんやらが出来ません。msysでもmingwでもない状態で起動しているからです。
そこで、これをmingwとして起動できるようにしましょう。
msys2は起動する際、ユーザの環境変数を参照し、msysかmingwかを判別します。
その参照する変数ですが、MSYSTEMという変数になっています。これをユーザの環境変数として登録し、値にMINGW64かMINGW32を設定しましょう。
MSYSでもいいですが、MINGWはMSYSも一緒にロードするのでMINGWのほうがいいと思います。

さて、これで完全な環境のmsys2がcmderの上で動くようになりました。
pacman -Syuを掛けておきましょう。
cmder+nyagos+msys2の環境構築は以上で完了です。
お疲れ様でした。

ちなみにmsys2にはvimが標準で含まれていません。
pacman -S vim でインストールしておきましょう。

golang でクイックソートを並列化してみる

僕の中で今アツイ golang
Googleが開発したプログラミング言語で、C言語を置き換える言語を目指しているらしいです。数多くの強力なライブラリを標準で備え、Cにあった様々な問題の解決を目指しているとか。
中でも僕が一番魅力に感じているのが、並列化機構を言語がネイティブで持っていること。外部のライブラリなどに頼らず、非常に簡単に並列処理を実現することが出来ます。
そういった機能がどれだけ強力なことなのか、検証やらの意味も込めて実験してみました。

今回 golang で書いたコードは以下になります。

<コード>

package main

import "fmt"
import "math/rand"
import "time"

func qsort(list []int) []int {
	if len(list) == 0 {
		return []int{}
	}
	x := list[0]
	xs := list[1:]
	smaller := make([]int, 0, len(list)-1)
	bigger := make([]int, 0, len(list)-1)
	for _, val := range xs {
		if val >= x {
			bigger = append(bigger, val)
		} else {
			smaller = append(smaller, val)
		}
	}
	smallch := make(chan []int)
	bigchan := make(chan []int)
	go sortchan(smaller, smallch)
	go sortchan(bigger, bigchan)
	smalllist := <-smallch
	biglist := <-bigchan
	return append(append(smalllist, x), biglist...)
}

func sortchan(list []int, ch chan []int) {
	sorted := qsort(list)
	ch <- sorted
}

func qsortNone(list []int) []int {
	if len(list) == 0 {
		return []int{}
	}
	x := list[0]
	xs := list[1:]
	smaller := make([]int, 0, len(list)-1)
	bigger := make([]int, 0, len(list)-1)
	for _, val := range xs {
		if val >= x {
			bigger = append(bigger, val)
		} else {
			smaller = append(smaller, val)
		}
	}
	smalllist := qsortNone(smaller)
	biglist := qsortNone(bigger)
	return append(append(smalllist, x), biglist...)
}

func main() {
	slist := make([]int, 200000)
	for i := range slist {
		slist[i] = rand.Intn(100000)
	}
	start := time.Now()
	_ = qsortNone(slist)
	end := time.Now().Sub(start).Nanoseconds()
	fmt.Println("並列化前: ", end, " ns")

	start = time.Now()
	_ = qsort(slist)
	end = time.Now().Sub(start).Nanoseconds()
	fmt.Println("並列化後: ", end, " ns")
}


<説明>

クイックソートアルゴリズム解説はWikipediaでも読んでください。
go func() でfunc()をゴルーチンとして実行し、終了を待たずに次の行へ進むことが出来ます。これが並列化です。今回は配列の先頭の数字をピボットとし、再帰的にソートする処理を並列化することによって高速化を試みました。qsort(int)が並列化バージョン、qsortNone(int)が並列化なしバージョンの関数です。
0から99,999までの範囲の乱数が200,000個ランダムに入ったスライス slist に対してソートを実行し、それぞれの時間を計測しています。

<実行結果>

10回実行し、平均を取ります。

1. 並列化前: 117006700 ns
  並列化後: 839048000 ns
2. 並列化前: 116006600 ns
  並列化後: 776044400 ns
3. 並列化前: 115006500 ns
  並列化後: 840048100 ns
4. 並列化前: 117006700 ns
  並列化後: 768044000 ns
5. 並列化前: 114006500 ns
  並列化後: 778044500 ns
6. 並列化前: 112006400 ns
  並列化後: 764043700 ns
7. 並列化前: 111006400 ns
  並列化後: 757043300 ns
8. 並列化前: 111006400 ns
  並列化後: 752043000 ns
9. 並列化前: 111006400 ns
  並列化後: 767043800 ns
10. 並列化前: 111006300 ns
  並列化後: 764043700 ns

<平均>
  並列化前: 113506490 ns
  並列化後: 780544650 ns

以上のような結果となりました。並列化前が0.114秒、並列化後が0.781秒くらいですね。…………???

あれ……並列化した後のほうが遅い……。並列化の強力さって……?

<考察>

きっとスレッディングだから。
実際に並列に処理しているわけではなく、一定時間ごとに「次はこっちのスレッド、その次はこっちのスレッド……」みたいな感じで、他のスレッドを停止しながら1つずつ処理していっているからだと考えられます。ゴルーチンはCPUが同時に複数計算するのではなく、同時に見えるように計算しているだけなので、チャネルのロック待機時間やら関数呼び出しのオーバーヘッドやらなんやらで並列化バージョンのほうが余計に時間がかかってしまっているものと思われます。
コーディングが悪いわけではない……と信じたい。実装方法的に、スライスの要素数が1つになるまでスレッドが分かれてしまうので、そのせいで時間がかかっているのかもしれません。


<まとめ>

golang楽しい(錯乱)。
スレッディングはゲームプログラミングでめっちゃ使うので、ぶっちゃけ処理時間が向上しなくても普通に使い道はあるのです。
使いやすいゲーム用GUIライブラリがなさそうなので、しばらくはこういうことずっとやってる感じになるかもしれません。
go-sdlとかは出てます。(SDL触ったことないので敬遠してます。食わず嫌いとはまた違いますが、チョットコワイ)

前に言ってたこととやってることがぜんぜん違う……。すごいH本買ってからしばらく経ったはずなのに、まだ読み終わってないしhaskellの勉強も進んでいないので、もっと勉強します。

それではまた。次の更新がいつになることやら。




--- 2015/05/50 17:30 追記 ---

スレッドを分けすぎているのかもしれないと思って、ピボットよりも小さい配列と大きい配列それぞれについて、要素数が1000個以下の時はqsortNone()を適応してみました。結果、平均が0.126秒となり、場合によっては並列化前よりも高速に動作することもありました。
このことから、遅くなってしまったのは実装の問題だということがわかりました。あまりにスレッドを分けすぎた結果、チャネルのロックやらなんやらのせいで遅くなったものと思われます。
計算が並列に見えるだけとか適当な事書いてすみませんでした。