動的計画法とナップサック問題を学びたい人におすすめのサイト
組み合わせ最適化の手法として「動的計画法」というモノがあります。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）
コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法
一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。
ナップサック問題と動的計画法
動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。
こんな感じの問題です。
今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各々値札が着いているとしましょう。
そしてあなたはナップサック（リュックサックでもいい）を１つもっています。
このナップサックに、もっとも合計額が高くなるように、目一杯ぎゅうぎゅうに品物を詰めてください。
イメージしやすいですね。要するに特定の制約条件のもとで利益を最大化させるような話です。実生活でも色々なシーンで遭遇しそうな問題ですね。
さて、このナップサック問題を解こうとすれば、単純に考えれば、すべての品物について「選ぶ／選ばない」の２つの場合を考えて行けばいいので、品物がN個だとすると2のN乗のパターンを総ざらいすれば最適解は求まりそうです。
ところが総当たり方式だと、品物が３０個になっただけで実に1073741824、つまり10億以上のパターンを演算しなければなりません。
このように総当たりでは現実的な時間内で計算できないような問題を数学的には「NP困難」と呼びます。
そこで動的計画法を使ってスマートに最適解を導き出そう、というのがナップサック問題といわれるネタになります。
動的計画法の詳しい説明は解説サイトが数多くあるので、ここでの言及は控えます。
ここではperlを使ってちょっとした例題を解いてみます。
準備
動的計画法はとてもシンプルなアルゴリズムなので、自前で書いてしまっても数十行程度に収まりますが、やはり面倒なので、まずはCPANを探してみます。
あっさりとAlgorithm::KnapとAlgorithm::Knap01DPというモジュールを発見。
今回はKnap01DPを使ってみます。これは0-1ナップサック問題を解くためのモジュールっぽいです。
（商品を１回しか選べない場合は0-1ナップサック問題、複数回選択可能な場合は123ナップサック問題と呼ばれています）
さてさてコード書いてみるか、、、、ん？なんだこれ？？
書き始めてみて気がついたのですが、このモジュール、えらく使いづらいです。。
データをわざわざ別ファイルに持たなければ行けないし、メソッドもなんだか素直じゃない。ちょっと大きめのデータ（数万件程度）を処理したらあっさりout of memoryしてしまうし。実用的なモジュールとは言いがたい印象です。
なので、あくまで「雰囲気を知る」程度に触ってみます。
例題
お題は「遠足で３００円以内で持って行きたいお菓子をえらぶ」というシチュエーションにしましょう。
gooランキングで「遠足のおやつ300円」に必ず入れたいお菓子ランキングという丁度良いネタがあったので、これらのお菓子を候補とします。
# ポッキー 168円 496kcal
# うまい棒 10円 45kcal
# じゃがりこ 145円 325kcal
# ベビースターラーメン 60円 347kcal
# チロルチョコ 10円 61kcal
# かっぱえびせん 124円 486kcal
# サッポロポテト 124円 446kcak
# 都こんぶ 105円 22kcal
# ヨーグレッとは入れもん 126円 110kcal
# おにぎりせんべい 184円 475kcal
（値段とカロリーは適当に調べたのであまり正確ではないです）
さて、これらのお菓子を３００円を上限としてもっとも満足度の高い組み合わせで選びたいと思います。
ちょっと不自然ですが満足度としてカロリーを使います。
肥満児の気持ちになって「３００円以内でカロリーを最大化したい！」と考えて下さい。（どんな子どもだ？）
まずは上記のお菓子の情報を以下のような入力ファイルにまとめます。
okashi.txt
10 # 品物の数
300 # 上限金額
168 # ポッキーの値段
496 # ポッキーのカロリー
10 # うまい棒の値段
45 # うまい棒のカロリー
145 # じゃがりこの値段
325 # じゃがりこのカロリー
60 # ベビースターラーメンの値段
347 # ベビースターラーメンのカロリー
10 # チロルチョコの値段
61 # チロルチョコのカロリー
124 # かっぱえびせんの値段
486 # かっぱえびせんのカロリー
124 # サッポロポテトの値段
446 # サッポロポテトのカロリー
105 # 都こんぶの値段
22 # 都こんぶのカロリー
126 # ヨーグレット／ハイレモンの値段
110 # ヨーグレット／ハイレモンのカロリー
184 # おにぎりせんべいの値段
475 # おにぎりせんべいのカロリー
コードです。
knapsack_test.pl
use strict; use warnings; use Algorithm::Knap01DP; my $file = $ARGV[0]; my $knap = Algorithm::Knap01DP->ReadKnap($file); $knap->solutions(); $knap->ShowResults();
そうすると以下のような結果が得られます。
[miki@godzilla knapsack] $ perl knapsack_test.pl okashi.txt
Problem: okashi.txt
Number of Objects = 10 Capacity = 300
1 (10) 4 (10) 5 (124) 6 (124) Used Capacity = 268
Profit = 1038
これによると１と４と５と６を選ぶと価格が２６８円、満足度が1038で最大だよ、ということになります。
つまり、こうなります！
うまい棒 10円 45kcal
チロルチョコ 10円 61kcal
かっぱえびせん 124円 486kcal
サッポロポテト 124円 446kcal
うーん、そうきたかぁ。。。
うまい棒とチロルチョコの小物２つをおさえつつも、高カロリー・フライ系をしっかりメインに据えてくるあたり、とても合理性を感じます。
まとめ
うまい棒、チロルチョコ、かっぱえびせん、サッポロポテト。。。
大物と小物の組み合わせで４種類のアイテムを展開しつつ1038kcalの堂々の布陣！それでもって268円というリーズナブルな組み合わせ！
「遠足と言えば都こんぶだよね」なんてしたり顔しているあなた
「ポッキーははずせないよね」なんてアタリマエなこと言ってるあなた
だからキミは甘いって言うんです
そんなこと言ってるようでは、さぞかし遠足で惨めな思いをしてきたはず。
大人になった今もきっと幸薄い人生でしょう。
かく言う私もチロルチョコなどの小物には目もくれない強欲な子どもでした。
今すぐ少年時代に戻って「動的計画法」を駆使してお菓子選びから人生をやり直したい今日この頃であります。
まとめなおし
だいぶ脱線したので、まとめなおします。
動的計画法は応用範囲も広いし、エンジニアにとって覚えておくとよい知識だよ、ということで、最後にいくつか参考になりそうなサイトを列挙しておきます。
http://www-or.amp.i.kyoto-u.ac.jp/open-campus-04.pdf
簡単そうで難しい組合せ最適化
京都大学のオープンキャンパスの資料？らしいですが、とてもわかりやすいです。初心者はここから学ぶのがおすすめ。
http://algorithms.blog55.fc2.com/blog-category-6.html
ALGORITHM NOTE 動的計画法
様々な例があってすばらしくわかりやすい。Cによるサンプルコードも勉強になります。
pythonで例示しながら解説してくれています。欲張り法（greedy）についても学べます。
nitoyonさんによるスライド。超大作（165ページもある！）
bayonやCLUTOが爆速な理由
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。
うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。
きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。
このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほどクラスタの中心に凝集しているようになり、クラスタ中のデータが似た者同士の集まりである、と考えるわけです。
ふむふむ。cosine類似度の和が大きいほどまとまりがよい、というのは直感的に理解できますね。
ただし、クラスタ中の各要素と中心との類似度をまじめに全て比較するのは計算量も高くなってしまいます。実際には、この値はクラスタ中のベクトルをすべて足した複合ベクトルの長さと同値になり、そのため計算量も少なく評価値を求めることができます。
なぬ！？要するにcosine類似度を全部足すと、全ベクトルを足しこんだもののノルムに等しくなる、ということを言ってます！？ま、まじっすか！
「くわしくはCLUTOの論文読んでね」と書いてあったので、適当にあたりをつけながら斜め読みしてみました。Criterion Function（評価関数）の説明の部分にそれらしき記述がありました。
どうやらこれはComposite Vector（複合ベクトル）の特性のようです。
確かにこの特性を利用すれば計算コストは大幅に削減できそうです。
実験
というわけで簡単なスクリプトを書いて確認してみました。
use strict; use warnings; #---------------------------------------------------------- # # クラスタ中の全ベクトルと重心とのcosine類似度を全部足すと、 # 複合ベクトルのノルムに等しくなるかどうかを確認してみます # #---------------------------------------------------------- # 適当なベクトルを準備 my $vec_1 = { '日本' => 1, '今日' => 3, '高校' => 2, '国語' => 1, }; my $vec_2 = { '日本' => 2, '今日' => 1, '高校' => 1, '数学' => 1, '国語' => 1, }; my $vec_3 = { '今日' => 1, '高校' => 1, '国語' => 5, '英語' => 3, }; # 単位長に正規化 for ( $vec_1, $vec_2, $vec_3 ) { unit_length($_); } #------------------------------------------------------------ # 重心とのコサイン類似度を足し込んで行く #------------------------------------------------------------ # 重心を取得 my $centroid = centroid( $vec_1, $vec_2, $vec_3 ); # 各ベクトルと重心との類似度を足して行く my $sum; for ( $vec_1, $vec_2, $vec_3 ) { $sum += cosine_similarity( $_, $centroid ); } #------------------------------------------------------------ # 複合ベクトルのノルムを計算してみる #------------------------------------------------------------ # 複合ベクトルを計算 my $comp = composite( $vec_1, $vec_2, $vec_3 ); # 複合ベクトルのノルムを取得 my $norm = norm($comp); #------------------------------------------------------------ # 出力! 結果は同じ値になるか！？ #------------------------------------------------------------ print $sum, "\n"; print $norm, "\n"; exit; # 以下サブルーチン sub centroid { my @vec = @_; my %cent; for (@vec) { while ( my ( $key, $value ) = each %$_ ) { $cent{$key} += $value; } } while ( my ( $key, $value ) = each %cent ) { $cent{$key} /= int @vec; } return \%cent; } sub unit_length { my $vec = shift; my $norm = norm($vec); while ( my ( $key, $value ) = each %$vec ) { $vec->{$key} = $value / $norm; } } sub norm { my $vec = shift; my $norm; for ( values %$vec ) { $norm += $_**2; } sqrt($norm); } sub composite { my @vec = @_; my %comp; for (@vec) { while ( my ( $key, $value ) = each %$_ ) { $comp{$key} += $value; } } return \%comp; } sub cosine_similarity { my ( $vector_1, $vector_2 ) = @_; my $inner_product = 0.0; map { if ( $vector_2->{$_} ) { $inner_product += $vector_1->{$_} * $vector_2->{$_}; } } keys %{$vector_1}; my $norm_1 = 0.0; map { $norm_1 += $_**2 } values %{$vector_1}; $norm_1 = sqrt($norm_1); my $norm_2 = 0.0; map { $norm_2 += $_**2 } values %{$vector_2}; $norm_2 = sqrt($norm_2); return ( $norm_1 && $norm_2 ) ? $inner_product / ( $norm_1 * $norm_2 ) : 0.0; }
結果。
2.47915597812817
2.47915597812817
おお、本当に一致しましたよ！びっくり。
ちなみに単位長で正規化している部分ですが、これはCLUTOの論文を読んでいたら「unit length」という表現があったので気がつきました。
mysqlで複数行にまたがるカラムをCSVフォーマットで出力する方法
地味なネタですが、今日はまってしまったのでメモっておきます。
とあるとmysqlのデータをselect * from xxx into outfileで外部ファイルに出力したいとします。
テーブルのスキーマは「URL、タイトル、 HTML本体」という構成だとしましょう。HTML本体の部分は改行がたくさん入っています。
このデータをあとからcsvとして正しく読み込めるようなフォーマットで出力したいわけです。
まずは普通に出力してみます。
select url, title, html from table into outfile "output.tsv";
そうするとこのような結果になります。
http://hoge.com タイトルですよ \
\
\〜途中省略〜\
mysql のinto outfileはデフォルトだとTAB区切りで、複数にまたがるデータについてはバックスラッシュでエスケープするようです。
区切り文字はなんでもいいんですが、改行している部分がこれだとCSVとしてはあつかえませんね。
例えばPerlでText::CSVで読み込むためには、複数行にまたがるカラムの場合、ダブルクオートで囲ってやる必要があります。
つまり上のサンプルだとこんな感じ
select url, title, html from table into outfile "output.csv" fields terminated by "," enclosed by '"';
"http://hoge.com","タイトルですよ",""
"
"
〜途中省略〜""
"
区切り文字をカンマにしてダブルクオートで囲むようにしました。
これならPerlのText::CSVとかで簡単にパースできそう！・・・と思ったらNG！！
ダブルクオートで囲った内部でダブルクオートがあるケースではmysqlが気を利かせてさらにダブルクオートでエスケープしてくれてるあたり、とてもいい感じなんですが、mysqlではメタ文字のエスケープとして改行の部分にも"が入ってしまいます。
これがよろしくない。
"" を１つのカラムだと認識してしまって、２行目以降でエラーになります。
なので囲み文字はダブルクオート、エスケープの文字をバックスラッシュにしてみます。
select url, title, html from table into outfile "output.csv" fields terminated by "," enclosed by '"' escaped by '\\';
そうするとこのような出力結果になります。
"http://hoge.com","タイトルですよ","\
\
\
〜途中省略〜\\
"
全てのカラムがダブルクオートで囲まれてますね。それと同時にエスケープはバックスラッシュになってます。
さてさて、Text::CSVでパースしてみます。こっち側でもちょっとした工夫があります。
use strict; use warnings; use Text::CSV_XS; use Data::Dumper; my $csv = Text::CSV_XS->new( { sep_char => ',', escape_char => "\\", allow_loose_escapes => 1, binary => 1 } ); open my $fh, "<", 'output.csv'; while ( my $row = $csv->getline($fh) ) { for (@$row) { print $_,"\n"; print "-" x 100,"\n"; } }
Text::CSV_XSのコンストラクタでsep_charやescape_charを指定してるのはまぁ普通なんですが、allow_loose_escapesをセットしてるところがミソです。これがないとエラーになります。
Text::CSV_XSのPODにはこんなことが書いてありました。
allow_loose_escapesBy default, parsing fields that have escape_char characters
that escape characters that do not need to be escaped, like:my $csv = Text::CSV_XS->new ({ escape_char => "\\" });
$csv->parse (qq{1,"my bar\'s",baz,42});would result in a parse error.
Though it is still bad practice to allow this format,
this option enables you to treat all escape character sequences equal.
ふーむ。
なんだか何言ってんだかいまいちよくわからんけど、結果としてはうまくできたので、まぁいいや。
それにしても地味というかレアケースというか、微妙なハウツーだね、これは。
だれか一人でも参考にする人がいれば、ミラクル！
onUnloadでクリックトレース
メリークリスマス！
聖なる夜に不慣れなjavascriptをいじってる豚野郎です。
「普段からwebビーコンでユーザの閲覧ページの追跡ばかりしている変態くん。本当はそのユーザが飛んでいった外部ページのURLも知りたいんじゃないのか？ん？我慢すんなよユー。」
と、さっきから心の中でデブな悪魔がささやくのです。クリスマスだというのに、暑苦しいなぁもう。
仕方がないのでやってみましたよ。
<html> <head> <script type="text/javascript" src="jquery.min.js"></script> <script type="text/javascript"> $(function () { window.addEventListener("unload", function(){ var link_url = document.activeElement.href; if(link_url){ var click_tracer = 'http://hoge/click_trace?url=' + link_url; $.ajax({ type : "GET", timeout : 0, url : click_tracer, }); } }, false); }); </script> </head> <body> てきとうなページ <li><a href ="http://www.yahoo.co.jp">Yahoo</a></li> <li><a href ="http://www.google.co.jp">google</a></li> <li><a href ="http://www.goo.ne.jp">goo</a></li> </body> </html>
onUnloadでactiveElementを取得してajaxでどっかのサーバに放り込む、というベタな作戦です。
ホントにベタですね。普通ですねー。みんなやってますねー。
んで、実験したところ、firefoxとIEでは問題なく動作しました。
やったぜ！うひひ、と喜んでおりましたところ、なぜかsafariでは動作しませんでした。
なんでだろう？と小一時間ほど悩んでみました。
そしたら以下のようなブログを発見。
JavaScriptでonunloadを書く時の注意点（ノヴァちゃん日記）
次にSafariですが、こいつは一見正しく動作してるように見えます。っていうか大体の場合は正しく動作すると思っていいと思いますが、onunnloadを使用してAjaxで通信を行おうとするとその処理はスルーされてしまいます。つまり以下のような状況が発生します。
window.onunload=function(){
alert("start!!") // 動作する
ココにAjaxでの通信処理 // ココだけ動作せずにスルーされる！！
alert("end!!") // 動作する
}これはどうやらSafariのみの問題のようで、例えばOperaでは、ページ内のコンテンツからの移動でさえあれば、Ajaxだろうとなんだろうと正しく動作します、FirefoxやIEも同様です。
なんと！Safariくん、とっても性格悪いですね。先生は君のそういう所が気に入りません！
ちなみに、、ああ、やっぱりGoogle Chromeくんでもスルーされてしまいます！先生は悲しい！
やっぱり人の行動を覗き見するようなことばっかり考えている人には幸福は訪れないようです。
聖なる夜にカンパイ！
噂のnode.websocket.jsでサーバサイドJSとHTML5 WebSocketを体験してみたの巻
WebSocketを体験してみたいのと、サーバサイドJSを試したいのと、さらにはmac版のChromeをインストールしてみたという条件が重なり、これはもう深夜だけどnode.websocket.jsを試してみるしかないな、という状況に追い込まれました。
構成
最近あたらしく調達したばかりのmacbook air にvirtualboxを入れています。その上でCentOSが動いています。
macbookをクライアントに、CentOS側をサーバとみたてて話を進めていきます。
ちなみに、virtualboxではアダプタ１をNATに、アダプタ2をホストオンリーアダプタ（IPはstaticに設定）としているので、CentOSからは外にも抜けられるしmacbook側からも自由にアクセスできます。ごきげんな環境です。
Node.JSのインストール
まずは土台となるnode.jsが必要。ソースをダウンロードしてくるか、もしくはgitからcloneするかします。
展開して./configure & make します。やや時間かかりますが、とくに問題なくコンパイルできました。
make test すると私の環境では「abが入ってないよ」と文句言われましたが、しょうがないじゃんapache入れてないんだから。なのでシカトしてsudo make install。
/usr/local/bin/nodeがインストールされました。
さて、これでgoogle V8エンジンによるサーバサイドjavascriptな環境ができたはずです。早速ためしてみます。
var sys = require('sys'), http = require('http'); http.createServer(function (req, res) { setTimeout(function () { res.sendHeader(200, {'Content-Type': 'text/plain'}); res.sendBody('Hello World !\n'); res.finish(); }, 2000); }).listen(8000); sys.puts('Server running at http://127.0.0.1:8000/');
http://nodejs.orgに書いてあったサンプルのままですが、これをexample.jsなど、適当な名前で保存します。
そしてnodeでjsを走らせます。
[miki@gamella nodejs]$ node example.js
Server running at http://127.0.0.1:8000
おお、サーバが起動した！netstat で確認してみたらちゃんと8000番でlistenしてるよ！
macbook側（クライアント側）からHTTPをたたいてみます。
godzilla:Hacks miki$ lwp-request http://gamella:8000/
Hello World !
godzilla:Hacks miki$
ちゃんと返ってきました！
次にTCPサーバのサンプルもあるので、それも試してみました。
var tcp = require('tcp'); var server = tcp.createServer( function(socket) { socket.setEncoding("utf8"); socket.addListener("connect", function() { socket.send("hello\r\n"); }); socket.addListener("receive", function(data){ socket.send(data); }); socket.addListener("eof", function(){ socket.send("goodby\r\n"); socket.close(); }); }); server.listen(7000, '192.168.56.101');
これもサンプルのままなんですが、最後の行だけオリジナルとは変えています。
オリジナルでは「server.listen(7000, "localhost")」となっていましたが、
自分のサーバ環境（virtualbox上のCentOS）だとlocalhostと指定するとアダプタ１（NAT）のIPになってしまうので、
ここではアダプタ２（ホストオンリーアダプタ）の方のIPを直で書いています。
（本質とは関係ないことなので、どうでもいいことですが。）
なにはともあれ、こんな簡単にサーバサイドJSが実現できてしまって、ちょっと驚きです。
今までは事あるごとにperlでAnyEvent／POEでサーバを書いてきましたが、ちょっとした用途であればJavascriptでもいけそうです。
node.js.websocketを試してみる
さぁて、ようやく本題です。HTML5 WebSocketです！
まずはここのサイトをザッと読んでおくといいでしょう。
http://devthought.com/blog/2009/12/nodejs-and-the-websocket-protocol/
- Node.JSを読んで触発されてNode.JS.Websocketを書いたよ
- WebSocketいいよ COMETの対抗馬だよ
- Node.JSはネットワークなイベントドリブンなフレームワークでgoogleのV8エンジン搭載だよ
- loggingにはRedis使うけどなくても大丈夫だよ
- WebSocketはまだ限られたブラウザでしか使えないよ（Webkit, Chromium, trunk Firefox (and possibly Opera) have a decent degree of support of WebSocket）
ほかにも最後の方で今後の抱負みたいなことがかいてありますが、まぁだいたいこんな内容のことが書いてあります。
というわけでさっそくソースを落としてきます。
http://github.com/guille/node.websocket.js/
README.mdの最初の方をサラリと読んだだけなんですが、どうやら簡単に使えるみたいです。
まずは同梱されているtest/test.htmlをサーバ側に設置します。
あ、そういえばapache入れてないんだった。面倒いからyum install httpd してしまえ。えいっと。
test.htmlはそのまま使えます。メインのjavascript部分だけ書き出しておきます。
<script>
var webSocket = new WebSocket('ws://192.168.56.101:8080/time');
webSocket.onopen = function(event){
document.getElementById('time').innerHTML = 'waiting for socket';
webSocket.send('start');
};
webSocket.onmessage = function(event){
var object = JSON.parse(event.data);
document.getElementById('time').innerHTML = object.time;
};
webSocket.onclose = function(event){
document.getElementById('time').innerHTML = 'socket closed';
};
</script>
これがWebSocketかぁ。なんだかえらく簡潔なコードですね〜。
いずれ、HTML5が本格普及した暁には、こんな簡単なコードで永続セッション張れてしまうようになるんですね。
（いつ頃になるのかは怪しいところですが・・・）
つづいてサーバ側です。
node runserver.js とたたけば起動するんですが、何度も書いている通り 自分の環境ではホスト名をIPにしないとだめなので、--hostオプションをつけます。
[miki@gamella node.websocket.js]$ node runserver.js --host="'192.168.56.101'"
[Wed Dec 16 2009 03:16:58 GMT+0900 (JST)] [info] 0 clients connected
ふむ。websocketサーバが起動した。0 clients connected だってさ。
ではでは、クライアント側（macbook）からブラウザでアクセスしてみます。ブラウザはmac版のGoogle Chrome 4.0です。
やた！成功！。。。ってなんかえらく地味なデモですね。
でもちゃんと現在の時刻がPushされて画面上で更新されています。
ちなみにコンソール上ではこんなログが出力されました。
[miki@gamella node.websocket.js]$ node runserver.js --host="'192.168.56.101'"
[Wed Dec 16 2009 03:22:16 GMT+0900 (JST)] [info] 0 clients connected
[Wed Dec 16 2009 03:22:21 GMT+0900 (JST)] [info] 0 clients connected
[Wed Dec 16 2009 03:22:26 GMT+0900 (JST)] [info] 0 clients connected
[Wed Dec 16 2009 03:22:31 GMT+0900 (JST)] [info] [client 192.168.56.1] Server created
[Wed Dec 16 2009 03:22:31 GMT+0900 (JST)] [info] [client 192.168.56.1] Performing handshake
[Wed Dec 16 2009 03:22:31 GMT+0900 (JST)] [info] [client 192.168.56.1] Handshake sent
[Wed Dec 16 2009 03:22:31 GMT+0900 (JST)] [info] 1 clients connected
[Wed Dec 16 2009 03:22:36 GMT+0900 (JST)] [info] 1 clients connected
実際のところどうなのか？
見た目はぱっとしませんが、WebSocketにはちょっと面白い一面があります。
wsプロトコルはHTTPをベースとしている、ということです。
自分はFlash-XMLSocketの用に、socket的にハンドリングしているのかと思っていたんですが、どうやら違うようです。
実際にtcpdumpしてみたんですが、HTTPのコネクションが確立した後、jsonでやり取りしている様子を確認しました。
しかしなんでわざわざHTTP的なステージでやり取りさせる必要があるんだろ？？
ここまで書いてきて何なんですが、これだけのことならFlash-XMLSocketで既にできているんだよなぁ、とか思ったりして。
リアルタイムWebの本命となるのは、COMETなのかXMLSocketなのか、はたまたWebSocketなのか？
google waveの動きも含めて、どこらへんの技術がデファクトになるのか、今後もしばらく注目する必要がありそうです。
macbook airにvirtualboxでwindowsをインストールする方法
普段持ち歩くノートPCをvaioからmacbook airに変えました。いやっほう！！うれしいナ。
ですが職場ではwindowsなので、macbookだと時折不便なこともあるんですよね。
なのでvirtualboxでwindowsもセットアップしておくことにしました。
「余裕でしょ簡単でしょ」と高をくくっていたんですが、これが意外や意外。苦労させられました。
なのでインストールメモを残しておきます。
CD-ROMドライブがない！
当たり前だね。macbook airだもん。
でも家にはもう1台macbook（白）あるからリモートディスク機能使えばいいんだよね！
・・・と思ったんですが、あれれ？virtualboxではリモートディスクのドライブは認識してくれないみたいです。
「ど、どうすりゃいいのよ！？」と少しだけうろたえてみたんですが、普通に考えて、単にisoイメージを作ってやりゃいんだろ、と思ってググったら、まさにそのまんまでした。
以下、macでwindowsのisoイメージファイルを作る方法です。
- ドライブにwindowsのCDを入れる。
- ディスクユーティリティを起動して左側のペインでwindowsのインストールCDを選んでおく。
- 「新規イメージ」をクリック。
- 名前と場所は適当でオK。「フォーマット」を「DVD／CDマスター」にし、「保存」をクリック。
- しばらくすると「xxxx.cdr」というファイルができるので、拡張子をisoに変える
これだけです。最後は拡張しかえるだけでいいんですね。簡単ですね！
出来上がったisoイメージを適当な方法でmac book air に持っていきます。
自分は何を思ったのかインストールしたてのDropboxでisoイメージをsyncさせて喜んでいたんですが、えらい時間かかりました。
手元に２台ともあるんだから素直にUSBメモリかなにかでコピればよかった。。。
ともあれ、なんとかairの方にisoイメージファイルを持ってくることができました。あとはvirtualboxで普通にセットアップすればいいはず。
と思ったんですが、じつは最後にとんでもない難関が待ち受けてました。
F8が押せない
今回インストールするのはwindows server 2003だったんですが、セットアップの途中で「規約に同意するならF8押せよ」っていうような場面があるんですよ。
ぬっ、しまったぁぁ。macでF8押しても認識してくれない！
で、またまたgoogleに聞いてみましたよ。そしたらすぐ答えを発見。
- Virtual Box 2.0 + WindowsXP Pro on Mac OS.X 10.5（明日のために今日できる事。）
このブログに「fn押しながらF8押してみ」ってなこと書いてあります。なぁんだ、そんな簡単なことか。
というわけでこの関門もクリア。
しばらくすると、今度はキーボード識別のために「半角／全角キー押せ」みたいなこと言われました。例のアレです。アレ。
んなこと言ってもmacには半角／全角キーないんだよ！と怒りつつ、すごく適当に「英数」を押してみたら通りました。おおラッキー！
あとは特に問題なく、windows server 2003のインストール完了までこぎ着けました。
Ctrl-Alt-Delとかどのキーにどう割り当てられてるんだか今イチよくわからないけど、まぁいいや。
以上。おしまい。
==以下、追記==
クラスタリングツールbayonを便利に使うText::Bayonを書きましたよ
JPerl Advent Calender 2009 のhacker trackに「Perlではじめるテキストマイニング」というタイトルで記事を書きました。テキストマイニング系のモジュールを色々紹介しているので、興味ある人はぜひご覧ください。
さてさて、記事の最後の方で軽くふれましたが、つい先日 Text::Bayon というモジュールをリリースしました。
Text::Bayon - Handling module for the clustering tool 'bayon'
CPAN : http://search.cpan.org/~miki/Text-Bayon/
Github : http://github.com/miki/Text-Bayon
それの具体的な使い方を紹介します。
何をするものか？
Text::Bayonはクラスタリングツールbayonをperlスクリプトからスマートに利用することを目的としたモジュールです。
「bayonってなに？」という方はこちらを先に読んでください
- 計量データクラスタリングツールbayon (mixi Engineer's Blog)
- クラスタリングツールbayonがとてつもなく素晴らしいです！ (たつをのChangeLog)
- クラスタリングツール「bayon」を試してみた(ダウンロードたけし（寅年）の日記)
bayonとはmixiのfujisawaさんが開発＆公開されてい軽量クラスタリングツールです。
bayonの特徴としては、「速い、インタフェースが優しい、ライセンス的にも優しい、日本語ドキュメントがちゃんとある」といったところがあげられるかと思います。
わたしも仕事でずいぶん使わせてもらってますが、精度もけっこういいと思います。はい。
で、ちょこちょこ使っていて思ったんですが、
分析用データをperlなどで作る
↓
ファイル出力
↓
bayonコマンドでクラスタリング
↓
ファイル出力
↓
結果データを加工するためのスクリプトで処理
みたいな感じで、ほとんどの場合bayonへのやり取りの前後になにがしかのデータ加工処理が必要となるんですが、毎回毎回タスクが分断されて、ちょいとかったるいな、と。
そこでbayonへのやりとりも含めてperlスクリプトに突っ込めると、とてもスマートになるなぁと思い、そこらへんを実装してしまったのがText::Bayonです。
入出力のカタチ
まずは基本的な使い方。「データ to データ」な場合です。
use strict; use Text::Bayon; my $bayon = Text::Bayon->new; # 架空のデータ生成関数 # { ドキュメントID => { 単語 => スコア, ... }, ... } なデータ構造を生成 my $input = _gene_data(); # Bayonに渡す任意のオプション my %options = ( number => 10, point => 1, idf => 1, ); # クラスタリング！ my $output = $bayon->clustering($input_data, \%options); print Dumper $output; # 結果データはこんな構造 # { クラスタ => [ ドキュメントID, ドキュメントID, ... ], ... }
すっきり書けますね。
「ファイルに出力して、bayonコマンドに投げて、結果ファイルをまたロードして...」みたいな面倒いことをする必要はありません。
裏でText::Bayonがそのまんまの処理を請け負います。
ちなみに「ファイル to ファイル」な処理も１本のスクリプト内で完結できたりもします。
my %option = ( l => 2.0 ); my %output = ( output => 'bayon_out.tsv' ); # 入出力をファイルに指定して実行 # bayon_out.tsvに結果が出力される $bayon->clustering( 'bayon_in.tsv', \%options, \%output);
まぁこの場合はスクリプトなんかにしないで「 bayon -l 2.0 bayon_in.tsv > bayon_out.tsv 」ってコマンドたたいた方が早いか。
でも「ファイル to データ」とか「データ to ファイル」みたいな変則的なケースにも対応できるので、その場合には役に立ちます。
# -------------------- # ファイル to データ # -------------------- my $output = clustering('bayon_in.tsv'); # -------------------- # データ to ファイル # -------------------- my $input = _gene_data(); my %output = ( output => 'bayon_out.tsv' ); # 入力はデータ、出力はファイルに指定 $bayon->clustering( $input , undef, \%output);
ソフトクラスタリングにも対応
bayonにはclassifyというオプションがあって、ソフトクラスタリング相当の処理もできるようになっています。
なのでこれもclassify()というメソッドでカバーしています。
# clvectorを有効にしてクラスタリング my %option = ( clvector => 1, # optionでclvectorを有効にする ); my %output = ( output => 'bayon_out.tsv', clvector => 'centroid.tsv' # clvectorの出力ファイル名を指定 ); $bayon->clustering( $input, \%option, \%output ); # 取得したcentroid.tsvと、もとの$inputを使ってclassify my $classify_result = $bayon->classify($input, { clvector => 'centroid.tsv'} );
ちょっとclvectorの周辺が回りくどくてイケテナイんですが、まぁ一応こんな感じで１本のスクリプトにおさめることができます。
さらに詳しく
さらに詳しくはbayonのマニュアルを読んでください。オプションの指定とか色々あるので。
マニュアルサイト ＞ http://code.google.com/p/bayon/wiki/Tutorial_ja
その上でText::BayonのPODをみれば、何となくわかってもらえるかな、と思います。
なんか最後の方、だいぶ投げやり気味になってしまいましたが、Light-weightなマイニング屋さんにはおすすめです！
