まだやってたのか、と言われてしまいそうですが、おねえさんが計算にかけた時間と比べればまだまだです。 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ この動画で出てくるおねえさんのコンピュータを作ってみた、というお話。 おねえさんのコンピュータからアクセスできます。 検索アルゴリズム HTML+CSSでコンピュータの画面を再現してみました。Javascriptを組むより、そっちの方に時間がかかった気がする。 経路の描画にはCanvasを使ってます。 この問題は自己回避歩行(Self-avoiding walk)と呼ばれるものらしいです。 単にグラフ上を移動するだけなので、小さいなサイズなら単純な深さ優先検索(DFS)で解けます(大きなサイズで何が起こるのか・・・それは動画で)。 実装では、DFSによる検索プログラムをWeb Workerを使って走らせ、スタートとゴールを結ぶ経路を見つけたらメッセージを飛ばしてます。 さすがに全部は表示できないので、実際に表示するのは50ms秒程度の間隔。 4×4以下ではそれだと速すぎて何が何だかわからないので、待ち時間を入れてある。 さあ、君も10×10にチャレンジだ！！ おねえさんに教えて上げよう！ しかしながらDFSだけだとなんだか負けた気がして悔しいので、高速化したアルゴリズムも試してみた。 「おねえさんに教えてあげる」のチェックボックスにチェックを入れると高速化したアルゴリズムで問題を解きます。 ゼロサプレス型二分決定グラフ 自分が色々試行錯誤している間に他の人が解いてしまった(「フカシギの数え方」の問題を解いてみた) ので、それを参考に実装してみた。 今回の問題は「グラフ上の経路問題」ですが、どの枝を通ってどの枝を通らないかという「枝の選択問題」として考えることができます。 その組み合わせを効率良く表すための方法が、ゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)。 ZDDは数学の組み合わせでよく使う樹形図の一種で、 同じ結果になる枝を集めることで樹形図を効率良く表したものです。 概要はBDD/ZDDを基盤とする離散構造と処理演算系の最近の展望 を参照。 もっと詳しい説明はThe Art of Computer Programmingに書いてあるらしい(まだ読んでない)。 ZDDを考えた湊先生は最初の動画の企画・監修も努めている方なので、 動画中の数値もZDDを使って求めたものと思われます。 Simpath ZDDは単なる組み合わせの表現方法なので、別途グラフからZDDを求める手法が必要になります。 これに関する簡単な解説がZDDを用いたパスの列挙と索引生成 から見られます。 上のセミナー資料ではZDDの基本演算を使った列挙の方法が紹介されているけど、 今回はクヌース先生のSimpathを採用。 Simpathでは(既約でない)ZDDを作ることができます。 経路の両端にのみ着目し、この情報をmateという配列で管理。 frontierと呼ばれる頂点のmateを用いてZDD上のノードを共有することで簡略化を行います。 実際使ったアルゴリズム セミナー資料では幅優先でノードを作ってみるように見えるけど、今回の実装では深さ優先で経路数だけカウント。 ZDDのノードを作るのが面倒だったんです。 しかし、覚えなければならないmateが大量になってしまいメモリがああああ！！ すべて覚えるのは諦め、一部のmateだけ覚えるようにしました。 「おねえさんに教えてあげる」のチェックを入れると、適当実装のSimpathで計算します。 計算中一部の枝が灰色になるのは、ZDD上でノードの共有化が行われたため、実際には枝が処理されなかったためです。 格子上の点に丸がついているのはfrontier。 この点の継続情報を用いて共有化を行います。 まとめ おねえさんのコンピュータの実装と高速化を行いました。 高速化の結果、処理に数分かかっていた6×6の計算が200msで終わるようになりました。 10×10も1分程度で終わります。 ただ、表示のためのオーバーヘッドがあるとはいえ、他の人と比べると少し遅いような。 なにか実装間違っているかも。 The Art of Computer Programmingを読んで勉強しないとかな。

Vagrant VagrantはコマンドラインからVirtualBoxを扱えるようにするツール。 仮想マシンの起動・再起動をコマンドライン上から行えるのはもちろん、Chefや Puppet と連携することで必要なソフトウェアのインストールを行なってくれます。 Vagrantを使うには仮想マシンのひな形であるBase Boxが必要です。 Vagrantbox.esにいろんなOSのBoxがあるけど、 インストールされているOSのバージョンが古かったり、タイムゾーンがUTCになっていたりして 不具合発生。 そこでBoxを自分で作ってみようと思い立ち、やってみたのでそのメモ。 作ったBoxは GitHub にあげておいたので使いたい方はどうぞ。 Ubuntu 12.04.2 Server + VirtualBox 4.2.10 で作ってあります。 vagrant box add myubuntu https://shogo82148.github.io/boxes/ubuntu-12.04.2-amd64.box VeeWee VeeWeeはBoxの作成を自動化してくれるツール。 OSのインストール、不要なパッケージの削除、Box化なんかを自動でやってくれるらしい。 VagrantとVeeWeeのインストール Rubyの実行環境とVirtualBoxのインストールを済ませたら、 gemを使ってVagrantとVeeWeeをインストール。 gem install vagrant gem install veewee 使ってみる vagrant basebox templates と打つとテンプレートの一覧が出てくる。 現時点でのUbuntu最新版であるUbuntu 12.04をテンプレートとして使ってみる。 vagrant basebox define myubuntu ubuntu-12.04-server-amd64 これでdefinitions/myubuntuの中に設定ファイルができる。 そのままだとisoのダウンロードで404が帰ってくるので設定ファイルを書き換え。 加えて日本語が使えるようにLocaleをja_JPに、タイムゾーンをAsia/Tokyoにしておく。 --- templates/ubuntu-12.04-server-amd64/definition.rb 2012-08-31 18:23:28.000000000 +0900 +++ definitions/myubuntu/definition.rb 2012-08-31 21:17:52.000000000 +0900 @@ -6,8 +6,8 @@ :hostiocache => 'off', :os_type_id => 'Ubuntu_64', :iso_file => "ubuntu-12.

Octopressでツイートを引用しようと思ったけど 使えそうなプラグインがなかったので作ってみた。 ツイートに限らずいろんなものを挿入できるよ！ OEmbed 調べてみるとツイートの表示はOEmbedというのを使うとできるらしい。 これはURLを埋め込み適した形に変換してくれるプロトコル。 ツイートのURLから引用のためのHTMLを作ったり、YouTubeのURLから動画再生用のHTMLを作ることができる。 せっかくだからOEmbedに対応してしまえばいろんなものを埋め込めて便利だよね！ってことでやってみた。 インストール ruby-oembedをインストール。 gem install ruby-oembed ruby-oembedは名前から想像できる通り、RubyでOEmbedプロトコルを扱うためのライブラリ。 Provider(OEmbedの提供者)を自分で追加したり、Discovery(HTMLドキュメントにProviderの情報を入れる)にも対応している。 しかし、プロキシ環境下で動かなかったり、文字コードのエラーを吐いて死んだりしたので、 フォークして改造版ruby-oembedを作った。 もしオリジナルで不具合が出るようなら、こちらもどうぞ。 oembed_tagからoembed_tag.rbをダウンロードして、pluginsフォルダに置く。 Gemfileを適当なテキストエディタで開き、「gem ‘ruby-oembed’」の行を追加 source "http://rubygems.org" group :development do gem 'rake' gem 'rack' gem 'jekyll' gem 'rdiscount' gem 'pygments.rb' gem 'RedCloth' gem 'haml', '>= 3.1' gem 'compass', '>= 0.11' gem 'rubypants' gem 'rb-fsevent' gem 'stringex' gem 'liquid', '2.2.2' gem 'ruby-oembed' #追加 end gem 'sinatra', '1.2.6' これでとりあえずは動くはず。 以上の作業に加えて、キャッシュファイルがリポジトリに含まれないよう.gitignoreに.oembed-cacheを追加しておく。 使い方 以下の様に書くと、適切な埋め込み方法をWebから取得して変換してくれる。 {% oembed URL %} 例 Twitter {% oembed https://twitter.

久しぶりにOMakeを使おうと思ったら、使い方を忘れてしまったので復習。 基本的な流れ 初期化 OMakeのインストールはaptitudeやyumやDownload OMakeあたりで頑張る。 OMakeがインストールできたら、まずは初期化のおまじない。 omake --install カレントディレクトリにOmakefileとOmakerootが作られる。 自分のプロジェクト内容に合わせてOmakefileを編集。 具体的な例は後述。 ビルドする 単に「omake」と打つとビルド omake 継続監視ビルド 「-P」オプションで継続監視ビルド omake -P 関連するファイルを監視して、変更があれば自動的にビルドしてくれる。 キャッシュの削除 OMakeでビルドすると環境依存なパスの設定とかを書き込んだファイルが作成される。 Dropboxなどの同期ソフトはこれらの設定ファイルも同期してしまうので、 別環境で作業しようとするとエラーを吐いて止まってしまう。 次のコマンドでキャッシュファイルを無視すれば大丈夫。 omake --flush-includes Omakefileの例 TeXの文章をビルドするOMakefileの例。 LinuxとWindowsでデフォルトの文字コードが違って面倒なので、文字コードはutf-8に統一。 PDF出力はA3サイズ。 {% gist 3300749 OMakefile %} prosperを使ってプレゼン資料を作った時のOMakefile。 dvipdfmでは処理できない場合があるので、一度PostScriptにしてからPDFに変換するようにルールを上書き。 数式を多用するようなプレゼン資料だと便利。 {% gist 3300749 OMakefile-slide %} 参考 OMake つかったらC言語でプログラム書く手間がバカみたいに減った OMake つかって LaTeX コンパイルしたら簡単すぎて身長が5cm伸びた OMake マニュアル日本語訳 omakeが動かない …. 動いた [卒論] LaTeXのビルドにOMakeを使ってみた おまけ Dropboxと連携するとこんなことも。 Dropboxで同期しているフォルダで、「omake -P」を実行して自動コンパイルする設定のまま放置してきちゃった。別のPCでソース書き換えると、Dropboxが同期→リモートのomakeが自動コンパイル→Dropbox経由でコンパイル結果が帰ってきた。 — Ichinose Shogoさん (@shogo82148) 9月 27, 2011

さあ、皆さん！今年も長岡の大花火大会の季節がやって参りました！ 花火大会といえば、 光と音の速度差を体感できる絶好の機会です。 というわけで、去年もこんなアプリを作って遊んでました。 このアプリを頑張って改良したので、改めて紹介したいと思います。 アプリをダウンロード 使い方 起動すると、こんな画面が表示されます。 花火が開いたら画面をタップ！ そして、花火が画面中央に来るよう素早く端末を動かします。 (※画像ははめ込み合成です) 花火の音がしたら、目標をセンターに入れてタップ！ タップの間隔から花火までの距離を計算し表示してくれます。 さらに、加速度センサの値から端末の仰角を読み取り、花火の高さや水平距離などを算出してくれるという機能もついてます。 去年からの変更点 と、ここまでは、去年と一緒。 今年はさらにパワーアップしました。 地図へのマッピング スマートフォンには磁気センサがついており、方位が分かります。 加えて、GPSもついているので、スマートフォンの現在位置も分かります。 これだけの情報が揃えば、地図にプロットできるはず！ 結果表示の画面で「地図を表示」を選ぶとマッピングしてくれます。 この画面でメニューキーを押すと、TwitterやGoogle+などで、花火の位置をみんなに知らせることもできます。 GPS測位ができない場合は、デフォルトの位置を使用します。 この位置は設定画面で変更できます。 自動花火検出 去年からの課題であった、花火の自動検出も試みてみました。 初期画面でメニューキーを押すと設定画面へ飛べます。 ここで「花火を自動的に検出する」「花火の音を検出する」を選択すると、自動検出してくれるはずです(※理論値)。 花火が開いたことは、画面が明るくなったことで検出します。 明るさの検出は初期画面中央の四角の中が使われます。 設定画面でこの四角の大きさを変えることができます。 明るさの変化が閾値を超えたら測定開始です。 音は音量で検出します。 音声にDFTをかけて、周波数フィルタリングをかけてあります。 これで人ごみにまぎれても花火の音が検出できる・・・はず。 周波数0Hzにすると、周波数フィルタを通さずに振幅のみで判定します。 検出した値は、画面の右上に表示しているので、設定の時の参考にしてください。 ダウンロード アプリをダウンロード 野良アプリなので、「設定→アプリケーション→提供元不明のアプリ」をチェックする必要があります。 スマートフォンの機能をフル活用するので権限をたくさん要求してきますが、きっとだいじょうぶ。 そろそろマーケットでの公開も試してみたいですね。 ** Google Play にリリースしました！ ** Google Play からアプリをダウンロード まとめ それでは、大幅に機能UPしたアプリと一緒に、長岡の大花火大会をお楽しみください。 打ち上げはこのあたりらしいです。 ちゃんとマッピングできますかね？

背景・目的 なぜだか研究室のWiFi経由でSSHが通らないので、 GithubがBitbucketに繋がらない＞＜。 有線LAN経由なら通るので、ネットワークの問題だと思うのですが、 よくわからないのでとりあえずHTTPS経由で頑張ることにしました。 うちの学校ではHTTPSで外部に出るにはプロキシの設定が必要です。 そういうわけで、Gitでプロキシを使う方法を調べて見ました。 方法 .ssh/config に以下の設定をしました。 Host github.com User git Port 22 # or 443 Hostname github.com # or ssh.github.com IdentityFile /path/to/ssh.key TCPKeepAlive yes IdentitiesOnly yes ProxyCommand nc -X connect -x proxy.example.com:8080 %h %p 参考文献 git pull/push to github.com in proxy environment http proxy 越えの ssh SSHでプロキシ経由でアクセス

第27回NDS(長岡技術者勉強会)に参加してきました。 Gitハンズオン 今回はNiigata.scmとのコラボで GitハンズオンといつものLTの二本立てでした。 @masaru_b_clさんのGitの歴史や利点についての解説の後、 @dictavさんによる解説・演習。 addしてcommitする logやreflogでログ確認 reset –hard で元に戻す merge rebaseでコミットログを一本道に あたりをやりました。 一つのファイルの同じ行を20人でいじるという怖いこともしました。 凄まじいコンフリクト発生頻度と、すごい勢いで分岐していくログ。 実際の現場であったら恐ろしいですね。 gitはプラグインが使えるので、いろんなプラグインが出てます。 今回紹介があったのはgit-nowとgit-master。名前だけは聞いたことあるんだけど、使ってみますかね。 git-now masuru_b_clさんバージョン git-master あと、コミットログ英文の書き方とか Changelogのための英文テンプレート集 ust Gitの説明 ust 午前の演習その1 ust 午前の演習その2 ust 午後の部 push戦争 いつものLT 電子国土と地形図(その後) (@yu_hori)[http://twitter.com/yu_hori]さん NDS23での電子国土地図の発表の続き。 利用者にとって価値ある使いやすい電子国土基本図を目指して(中間提言) 電子国土ポータル 長岡にギークハウスを @geek_niigataさん やったーPICで作曲できたよー＼(^o^)／ @aokcub うおおおおおおおおおお！！！！ 期待の21世紀枠最後の昭和枠 NDS27に参加してきたよ！よ！ git-svn @masaru_c_blさん svnのリポジトリをgitにしてしまう奴。 ソフトウェアメトリクス調査2012を読み解く @hiro55bsさん ソフトウェアメトリックス調査2012 COBOL… 品質が低いと顧客満足度も低いけど、逆に品質が高すぎても顧客満足度は低い お客さんの要望に十分に答えられないのが原因？ やったーPerlでにゃん読化ツールできたよー＼(^o^)／ @neko_gata_sさん Niigata.pm 遊びに来てね NDSから大切なお知らせ @civicさん プロジェクトアンブレラ Niigata.pmはNDSの傘下 SRNDS(それNDSでできるよ) PSO aokcubさんの使ってたPSO面白そうだったので現実逃避に実装。 実際の効果はよくわからない。 初期値の時点でミニマムの近辺から外れると、ローカルミニマムに落ちることもしばしば。 それなら最急降下法でも・・・という気もしないでもない。 問題設定が悪いのか、パラメータが悪いのか。

こんにちは、gccのオプションを十個も言えない、非人のshogoです。 工藤氏作のTinySVMで遊ぼうとしていたところ、 ヘッダファイルの読み込み順序ではまったのでメモ。 2つのinclude文 皆さんご存知の通り、Cプリプロセッサの#include文ではファイルの指定方法が2種類あります。 #include <somefile> // システムにインストールされたライブラリを使う場合 #include "somefile" // 自作のヘッダファイルなどを読み込む場合 大抵はコメントで書いたような使い分けをするんじゃないかと思います。 両者の違いはファイルの検索対象となるディレクトリの違いにあります。 前者はコンパイラが知っているディレクトリのみを検索するのに対して、 後者はカレントディレクトリを検索したのち、<>と同じディレクトリを検索します。 コンパイラが知っているディレクトリは具体的に書くと次のようになっています。 -I オプションで指定されたディレクトリ 環境変数 C_INCLUDE_PATH や CPLUS_INCLUDE_PATH で指定されたディレクトリ システムによって予め決められたディレクトリ(/usr/local/includeとか) 上にあるものほど優先順位高く、同名のファイルがあった場合、優先順位の高いディレクトリにあるものが読み込まれます。 標準のヘッダを使いたい 次のようなCのプログラムを考えてみます。 /* sample.c */ #include <stdio.h> // 標準ヘッダのstdio.hを取り込んでほしい！ #include "stdio.h" // ../userheaderディレクトリ内のstdio.hを取り込んでほしい！ 最初のincludeではシステムに用意された標準ヘッダのstdio.hを、 2つ目のincludeでは自前で用意したstdio.hを読み込もうとしています。 しかし、自前で用意したstdio.hはuserheaderという別ディレクトリにあるので このままでは参照できません。 別ディレクトリにあるヘッダファイルを参照する場合、一般的には-Iオプションを使って次のようにコンパイルすると思います。 gcc -I../userheader sample.c しかしこの例の場合はこの方法は上手く行きません。 <>で囲った場合も"“で囲った場合も、カレントディレクトリにはstdio.hは見つからないので、 先の優先順位に従って次のような順番で検索を行います。 userheader 標準ヘッダstdio.hが入ったディレクトリ どちらの書き方でもuserheader内のstdio.hを先に発見してしまうので、 標準ヘッダのstdio.hにはどう頑張ってもアクセスすることができません。 解決策 iquoteオプションを使うと、""で囲った場合のみuserheaderを見に行くようになります。 gcc -iquote../userheader sample.c TinySVMの場合 TinySVM0.09(現時点での最新版)は一部環境でgetoptの違うというエラーが発生するようです。 これは-Iオプションを使ってしまったため、標準ヘッダのgetopt.hと、自前で用意したgetopt.hの使い分けができていないのが原因です。 TinySVMに同梱されたgetopt関数の引数を書き換えることで対処している例がほとんど (himorogiの日記, RとLinuxと…,etc) ですが、大抵の環境にgetoptはあると思うのでgetopt.hを削除してしまったほうがいいかもしれません。 (TinySVM最近更新されていないのでgetoptが古いし) 参考 C言語のヘッダ読み込み順について Directory Options - Using the GNU Compiler Collection (GCC) The C Preprocessor pp.

なんだか誘われたので、行ってきた。 メモメモ。 紹介された論文とか、スライドは自然言語処理研究室の意味知識勉強会のページからどうぞ。 関連学会 ACL AAAI IJCNLP Coling JIST 人工知能学会誌 自然言語処理(学会誌) 背景 人工知能の目指すところ 常識知識(common-sense knowledge)が必要 知識表現 オントロジー(ontology) 上位オントロジー 具体的な事象を対象としないオントロジー 常識オントロジー(Common-Sence Ontology) OpenCyc 語彙オントロジー(e.g. WordNet) 形式オントロジー OpenCyc 常識知識をデータベース化するCyc Project の一部。 専門家の手によって、手作業で構築されているオントロジー。 Open Mind Common Sense(OMCS) 機械的な常識知識獲得プロジェクト。 獲得した知識は ConceptNet というデータベースに取り込まれる。 GithubにデータベースアクセスのためのAPIが上がってるよ。 Recognizing Textual Entailment(RTE) テキスト含意関係認識 テキスト(Text)に対する仮定(Hypothesis)が含意している・矛盾している・Uknownであるかを判定するタスク RTEの初期のデータセットは無料で公開されている 論文紹介:Types of Common-Sense Knowledge Needed for Recognizing Texual Entailment RTE-5データセットから常識知識がなければ解けないものを「人手」で選択 単語の単純な言い換えなどで解決できないもの 600あるデータセットから108個見つけた 仮説が含意していると判定されるために必要な根拠を考える 分類して整理したよ！ 必要とされる回数が多いカテゴリは重要だよね！(ホント？元のデータセットに偏りない？) 言語処理でよく使うpart-of, is-a の様な関係が使われるのは、全体の40%でしかない 分類が正しさを表す指標としてκ値(Fleiss’s κ)を使って評価 20のカテゴリは大きく3つ分けられる Form-based Categories 因果関係とか Content-based Categories 計算しないといけない奴とか 地理関係とか Miscellaneous Categories みんなやっているから、この人もやっているはず！みたいな根拠のない関係 Omniscience(全知)

僕の学校では、学校のネットワークから外へ出ていくためにはプロキシと通す必要があります。 しかし、学内にあるサーバへは直接接続しなければなりません。 これを行うには no_proxy という環境変数を設定すればよいようです。 # Proxy 設定 export http_proxy=http://example.com:port/ export ftp_proxy=http://example.com:port/ export HTTP_PROXY=http://example.com:port/ export FTP_PROXY=http://example.com:port/ # 除外したいドメイン export no_proxy=localhost,.example.com no_proxyにカンマ区切りで除外したいホストを列挙します。 この設定を .bash_profile などに書いておけば、起動時に反映されるようになります。 全く・・・プロキシ面倒・・・。