未踏の合同成果報告会でした。最後の報告会っすね。
僕はLuxの発表を聞くためだけに来ました。

背景
　探す、という行為の効率向上が課題
　　情報多いし
　オープンソースの重要性

- - -　

Lux
　2008年3月から開発、5月に公開、7月から未踏に専念
　未踏では高速化、データベース、分散インデックスの開発

- - -

特徴
　使いやすさ、機能は、他の全文検索エンジンに劣る部分もある
　性能、分散・スケールアウト性、拡張性は、他の検索エンジンより有利と評価。
- - -　

１、高速化
　高速なデータベース
　　Lux IO
　圧縮された転置インデックス
　　検索速度を重視した圧縮
- - -
　　
２、拡張性
　抽象化
　　各層での変更が、多層に影響を及ぼさない構造
　再利用性
　　共通部分をフレームワーク
　　　サーバーデーモンの共通部分(pthreadのサーバ部分、
　　　クライアントも同じ。
　　外部ライブラリの利用
　　　STL
　　　libevent
　　　Google Protocol Buffer

- - -

Strage Interface
Strage Structure Interface 
Strage Structure （論理構造：転置index、ハッシュとか）
Strage Engine Interface 
Strage Engine （Lux IOとか、QDBMとか）

- - -

３、スケーラビリティ
　分散インデックス
　　スケールアウトのため
　　　ドキュメントベースで分散
　　　　全ホストへの問い合せ
　　マシンの追加で扱える文書数が、ほぼ線形になるように

- - -

Indexer
Engine -> Strage
Searcher

分散indexのサーチは、dispatcher daemonが全部のindexを見る。

- - -

評価
HEとLuceneはindexにかかる時間、だいぶかかる
SennaとLuxは500万件(6.5G)くらいの文書を追加するときに線形に時間増加
Luxのindexは9Gくらいになった

- - -

単体構成の検索
PageCache無しの場合、
Luxと同じく、線形に劣化するSennaよりだいぶ早い。

PageCacheを使った場合には
Sennaよりも、ちょいと早い。

Luxのindexとsearchが文書数の増加に対して線形に劣化することが分かった。

- - -

複数構成でも、
レスポンスタイムは線形に増加するし、
スループットにも通信時間やIOのオーバーヘッドの悪影響はなかった。

- - -

現状
　Lux
　　Sourceforgeに。
　　フォーラムもある。
　Lux IO
　　これもSourceforge
　　各種言語のバインディングを作ってくれている

- - -　　

今後の課題
　使ってもらう事が重要。導入先探し。
　開発者を募集している。
　
- - -

今後
　ツールの充実
　　使いやすさ向上
　機能やハードウェアを時代に合わせて変化
　　SSDが流行って来てるしー、とか

- - -　　

質問
　Q、分散機能を使うのは簡単？

  A、Serverのconfigを、各サーバに配布して起動すれば、
  各サーバは担当機能を立ち上げる。
  
  ---

  Q、以前作っていた検索エンジンとの差は？

　A、以前開発に携わっていたのは、
　オンメモリにindexを乗せる検索エンジン。
　
  100台くらいマシンがないと無理。
　そこでディスクベースにした。
　100台くらい無くても1億件の文書を扱える。

アルゴリズムデザインを読んでるのですが、
先週に引き続き読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]

■G-Sアルゴリズム
日本語の助詞が絶対におかしかったり、
言葉が足りないために意味が一意にならない部分を補った。

すべての男性m∈Mとすべての女性m∈Wは自由な身であると仮定する。
Whileすべての女性にはプロポーズしていない自由の身の男性mがいる
　そのような男性mを選ぶ
　wをmの好意順リストでmがまだプロポーズしていない女性の中で、最も好きな女性とする
　mがwプロポーズする
　If wが自由な身である then
　　(m, w)は婚約する
　Else
　　wは現在m'と婚約しているとする
　　If wは、mよりm'が好きである then
　　　mは自由な身で在り続ける
　　Else
　　　（wはm'よりmが好きである）
　　　(m, w)は婚約する
　　　m'は自由な身になる
　　Endif
　Endif
Endwhile
婚約のペアの集合Sを返す。


■解答付き演習1の設定
n人の男性と、n人の女性がいる。

各男性は全女性の好意順リストをもち、
各女性は全男性の好意順リストをもっている。

また、2n人の集合は「良い人」と「悪い人」に分けることができる。
良い人は、男女共にk人ずついるとする。

このとき、誰もが悪い人よりも良い人と結婚しようとする。
そのため好意順リストでは必ず良い人が悪い人より先に来る。

とする。

■解答付き演習1の問い
いずれの安定マッチでも、良い男性は良い女性と結婚することになる、ことを示せ。

■「！」：解答付き演習1の解答法のポイント
命題が真で無いと仮定し、その仮定の矛盾点を示す。

■解答付き演習1の解答
「いずれの安定マッチでも、良い男性は良い女性と結婚することになる」が真ではない時として、
「いずれの安定マッチでも、良い男性は良い女性と結婚することになるとは限らない」という状況を仮定できる。

このような仮定が真である場合には、
「良い男性と悪い女性の組」と「悪い男性と良い女性の組」が
少なくとも一組づつ、存在することになる。

このとき、少なくともこれらの組の間には不安定性があると言える。

なぜなら、「良い男性が良い女性と組になりたい」と考えており、
「良い女性が良い男性と組になりたい」と考えており、
良い男性と良い女性のニーズが合致してしまうからである。

最終的にいずれの安定マッチングも、良い人同士が組になり、悪い人同士が組になる。

ゆえに、「いずれの安定マッチでも、良い男性は良い女性と結婚することになるとは限らない」
という仮定は偽であり、仮定は成立しない。
したがって、命題は正しいと言える。

■記号「∈」と「⊆」
前者は、左辺の要素が、右辺の集合の元であることを表す。
後者は、左辺の集合が、右辺の週報の部分週報であることを表す。

■解答付き演習2の設定
禁止されている男女ペアの集合Fがあるとする。
つまりn人の男性の集合Mと、n人の女性の集合Wにおいて、
結婚が許されないペアの集合「F ⊆ M×W」が存在するということである。

各男性mは、すべての(m, w)!∈Fである女性の好意順リストをもち、
各女性wは、すべての(m, w)!∈Fであ男性の好意順リストをもっている。

■解答付き演習2の設定における安定マッチング
以下が、いずれも真ではないときに、一般に安定であると呼ばれる。
ただし、以下の定義では、安定マッチチングが必ず完全マッチングになるとは言えない。

1、これまでと同じ不安定性
(m, w')!∈Fであり、「mはwよりw'が好き」かつ「w'はm'よりmが好き」であるような
2つのペア(m, w)と(m', w')がS(= M×W)に存在する

2、既婚女性と独身男性の不倫の可能性による不安定性
(m', w)!∈Fであり、m'はSのどのペアにも含まれず、
かつwはmよりm'が好きであるようなペア(m, w)∈Fと、m'が存在する。

3、既婚男声と独身女性の不倫の可能性による不安定性
2の反対。省略。

4、未婚の男女の結婚可能性による不安定性
(m, w)!∈Fであるが、Sのどのペアにも含まれないような、
男性mと女性wが存在する。
# 禁止されてなければ結婚するし

■解答付き演習2の問い
どのような好意順リスト、および、禁止ペア集合に対しても、安定マッチングはいつも存在するか？

■「！」：解答付き演習2の解答法のポイント
以下のいずれかで解答を導く

1、任意の好意順リスト、および、任意の禁止ペア集合に対し安定マッチングを求めるアルゴリズムを提案
- より単純な条件を満たすアルゴリズムを動作させ、うまく動いていない部分を変更する。

2、「安定マッチングが存在しないような好意順リスト、および、禁止ペア集合」の反例を与える

■解答付き演習2の解答
1、アルゴリズムの提案

単純な条件を満たすG-Sアルゴリズムを動作させてみる。
すると、「Whileまだ全ての女性にプロポーズしていない未婚の男性mがいる」
というWhileループの条件がうまくいかない。

実際には、「全ての女性」ではなく「すべての(m, w)!∈Fである女性」である必要がある。

そこで、「Whileまだ『すべての(m, w)!∈Fである女性』にプロポーズしていない未婚の男性mがいる」
というように制約を厳しくしてみる。

この場合でも、
G-Sアルゴリズムの定義(1.1)(1.2)(1.3)はそのまま成立する。
また、このような拡張をおこなうと、得られるペアの集合は、
完全マッチングであるとは必ずしも言えない。
そのため、(1.4)以降は検証できない。

従って、本アルゴリズムは「出力が安定マッチングになる」
というところまで言えれば十分だと言える。

付け加えた制約によって、出力が安定マッチングになるかは
「解答付き演習2の設定における安定マッチング」で示した、
4種類の不安定性がいずれも成立しないことを示せば良い。

1、(m, w')!∈Fであり、「mはwよりw'が好き」かつ「w'はm'よりmが好き」であるような
2つのペア(m, w)と(m', w')がS(= M×W)に存在するとき、
アルゴリズム的にはmがwより先にw'にプロポーズしたが断られたことになる。
さらに、「wはm'よりも好きなm」のプロポーズを断ったことになる。
これはアルゴリズムに矛盾するので、この不安定性はない。


2、既婚女性と独身男性の不倫の可能性による不安定性
(m', w)!∈Fであり、m'はSのどのペアにも含まれず、
かつwはmよりm'が好きであるようなペア(m, w)!∈Fと、m'が存在するとすると、
未婚の男性m'がいて、そのm'は(m', w)!∈Fであるwにプロポーズしたが断られ、
かつ、「wはmより好きなm'」のプロポーズを断ったことになる。

3、既婚男声と独身女性の不倫の可能性による不安定性
2を裏返せば良い。省略。

4、未婚の男女の結婚可能性による不安定性
(m, w)!∈Fであるが、Sのどのペアにも含まれないような、
男性mと女性wが存在する場合、アルゴリズム的には
男性mが女性wに告白してしまい、その瞬間wは婚約することになるので、
未婚ではいられない、ゆえに、このような不安定性はない。

■演習問題1
以下の命題は正しいか。正しければ理由を述べ、間違っていれば反例を与えよ。

「安定マッチング問題のどのインスタンス」に対しても、mがwの好意順リストで最高位であり、
かつwもmの好意順リストで最高位であるペア(m, w)を含むような安定マッチングが存在する。

■演習問題1の解答
今回は、「「安定マッチング問題のどのインスタンス」にも、必ずペア(m, w)を含むような安定マッチングが存在する、わけではない」ことを示す例を出す。

m1 : [w2, w1]
m2 : [w1, w2]
w1 : [m1, m2]
w2 : [m2, m1]

このような好意順リストをもつ男女間の安定マッチング問題は、
GSアルゴリズムに従うと、男女が両思いにはならないので、
命題に矛盾する例の一つと言える。

ということで、反例を与えることができた。

■演習問題2
以下の命題は正しいか。正しければ理由を述べ、間違っていれば反例を与えよ。

mがwの好意順リストで最高位であり、かつ、wもmの好意順リストでで最高位である
「安定マッチング問題のインスタンス」に対して、全ての安定マッチングSはペア(m, w)を含む。

■演習問題2の解答

このような「安定マッチング問題のインスタンス」は、
GSアルゴリズムに従って操作してあげるとペア(m, w)ができる。

mからwにアプローチしても、wからmにアプローチしても、
アプローチされた側は、自分の好意順リストの最高位の候補から
告白たのだからそれを受け入れっぱなしになる。

よって、命題は正しいなぁと分かる。

■演習問題3
問題文が長いので省略。

1、任意のテレビ番組の集合と付随する任意の評価点の集合に対して、
安定なスケジュール対を求めるアルゴリズムを与えよ。

2、安定なスケジュール対が存在しないテレビ番組の集合と付随する
任意の評価点の集合の例を与えよ。

■演習問題3の解答

23ページの上から4行目に「以下の2つのいずれかを示せ」と書いてあるので、
(b)の「安定なスケジュール対が存在しないテレビ番組の集合と付随する評価点の集合の例を与えよ」をやってみる。

以下のような評価点の順になっているような集合を考える。

p1 > q1 > p2 > q2

そうすると、p社は「p1 > q1」と「p2 > q2」にしようとするし、
Q社は「p1 > q2」と「p2 < q1」にしようとして、収束しない。

ということで(b)を示せたんじゃないかな。

以下つづく。

「アルゴリズムデザイン 読書メモ」関連エントリ

昨日、一日スキーをして、余裕があれば今日も行こうとしたのですが、
寝て起きたら上半身が疲労は取れてませんでした。

なので、行ったことがない地獄谷へ行くことにしました。

地獄谷に一番近い入り口は、地獄谷まで「歩いて20分」の距離にある駐車場にあるコレ。

軽く吹雪いているなか、こんな感じの山道を延々と歩きます。
山道は大人が4人並んで歩けない幅で、かなり狭いです。

地面は凍っており、足を滑らせると谷に落ちてしまいます。
極寒のなか修行をしている気分で緊張しまくり。

手足が冷えきってガクガクしたころに、道が開けて地獄谷に到着。
ここからさらに5分歩いて地獄谷の猿パークまで歩きます。

猿パークの入り口側では温泉が吹き出ており、硫黄の匂いでむせ返っています。

入場料500円を払って中へGO。

おおおお、猿、猿、猿、猿だらけや！


一番奥には、猿の姿を撮影している観光客が沢山います。


この異様な光景を見られただけで大満足です。
寒い中歩いて来た甲斐がありました。


一応、猿に15cmまで近づいて撮影してみました。
猿、怖ぇぇぇ。話とか通じないもんね。


かなり驚いたのが、公苑にいた観光客の持ってるカメラ！
本体もレンズも、僕の目が確かならすごく高額なものばかり。
みんなきっと良い写真が撮れてるんだろうなぁ。


僕は、標準レンズを使っていたんだけど、
どうも締まりが悪いというか、確かに取れるんだけど、
今日はかなりモンヤリとした写真が撮れるので嫌だったです。
もう少し上手に撮れる気がするので、まだ標準レンズで頑張るっす。

スキー場のランチは高い、高い、と言いますよね。

だいたい、こんな感じの値段なんですけど。

この値段を見ているときに、ふと、

「だいたい六本木と一緒だ。」

ということに気がつきました。

六本木・赤坂のランチの高さは一部で有名です。
でも、具体的にどれくらいか実感は湧きにくいものです

「お昼代がスキー場並」と伝えると、
スキー場に行ったことがある人には分かりやすく良いと思います。

戸隠スキー場で、ようやく初スキーをしてきました。



本当は先月に行こうとしてたのですが、
急遽開発する必要のある物ができて、休日が潰れちゃったんです。

ようやく行ったスキー場。今日の人入りはこんな感じ。
すげえええ、人。ここ、入り口から一番近いリフトですよ。。



でも、北海道とか新潟のスキー場ほどではないですね。
みんな僕より上手そうなので、安心して転がれそうです。

リフトのチケットを買うときに、スキー場が閉まるまでに
5時間40分くらいだったので、5時間30分のリフト券を購入。

午前は一番入り口から近い、超短い中級者向け斜面で練習。
予想通り戸隠スキー場は、上手な人が多くて
へたくそな僕は安心して滑れました。

お昼前には、転ばなくなって感覚も戻ってきました。

お昼はカレー。頼んでも無いのに大盛り。



寝ろ！と言いたいのでしょうか。

ともかく、ちょっと食休みして、すぐにコースに戻りました。



午後は、初心者コースを1回滑って、
初心者ではないことを確認し、初級者コースへ。



初級者コースは自分のレベルだと、「ちょっと難しいレベル」で
いい感じだったのでスキー場が閉まるまで、
初級者コースを滑り続けていました。

終わる頃には、微妙にハの字滑りを卒業しかけました。
曲がるときに片足に体重を乗せて山側の足を揃えららるようになってきました。



帰って来て愕然としたのは昼は、ギチギチに詰まっていた車が、
あららら、って言うほど無くなってたことです。
みんな近所の喫茶店にでも行くような感じで滑りに来てるのかな。

春までにもう一回スキーに行って、感覚をしみ込ませたいなぁ。

[2009-03-18]：追記
コグレさんから「写真ない」とツッコんでいただき、気がつきました。
ので写真を追加。ありがとうございます。

タイトルのまんまですが、かっぱ寿司のしょうゆって
スナック菓子の味がしませんか？

というか、僕はすると思います。

寿司を食べてるのか、しょうゆ味のスナックを食べているのか、
よく分からない気分になったので、記念にメモしときます。

それにしても、一生使いたくなるおいしい醤油って、
どこで買えるんでしょうか。醤油蔵とか回れば良いのかな。。

別におみくじが大好きなわけじゃなく、
流れで1日に3回引いたら、3回とも大吉でした。

これって、割と良い確率なんじゃないかな。

1回目

2回目

3回目

万華鏡をモーターで回転させながら、
小型プロジェクタでスクリーンに投影していました。

実は僕は万華鏡が大好き。
特に、あらかじめ素材がセットされていて、
それだけで像が構成されるタイプの万華鏡が好き。

撮影禁止だったので写真はありませんが、すごく綺麗でした！

ふと、これって、アイフォンAppに無いのかなと思ったので調べてみました。

プログラミングで万華鏡を作るのは簡単なのかを調べてみると、
そこそこ簡単そうなので、自分でも作ってみようと思います。
やっとネタが見つかった。

みんなも作って僕に教えてください。

たまたま今日は善光寺の灯明祭り期間でした。

喫茶店に入る前に、足下に灯籠っぽいのが並んでいるところがあって、
何だろう？とは思っていたんです。

で、喫茶店から外に出ると、丁度灯明に日が灯されていく瞬間でした。

18時からわずか5分後には、こんな感じでびっしりとキャンドルライト。
そして坂の下から、大量の人がゾワっと善光寺に上がってきます。すごい！

善光寺はライトアップされまくりで、昼間とは全然違う感じ。

突然のことなので、携帯カメラスタンドを持っていませんでしたが
頑張るだけ頑張って撮影。

時間が経過すると色が変わっていくので撮るたびに色が変わります。
ずっと見ていても飽きません。

赤くライトアップされた本殿は、かなり迫力があります。
中にいる仏様の威厳や力強さが強調されている気がします。

それにしても手持ちで、明るい写真を撮ろうと思うとかなりしんどい。
日が沈むととたんにISO1600じゃなきゃ撮影ができない。

店内にはニンニクの匂いが充満していて、一瞬入店をためらいましたが、勇気を出して入店。

まだビールが残り気味だったので、サッパリしたネギ塩ラーメンを食べました。

期待通りさっぱりして美味しかったです。

ちなみに店内には、こんな張り紙がしてあります。


って、これ、見た目も情報も、ほぼ次郎wwwww！！！

次郎ファンの人は長野駅周辺に行ったときに立ち寄ると良いかも。

今日、2009年の朝8時31分30分はUNIX時間が「1234567890」になるのでした。

Perlが入っている環境でターミナルに以下の、
「Perl -e・・・」を入力すると、確認できると思います。

縦横長がバラバラの画像集合を全部まとめて、
「50x50」とか「100x100」とかの正方形画像に加工したくなりました。

画像フォルダの指定、出力フォルダの指定、一辺の長さの指定、
をするとモリモリと正方形画像を生成します。

とりあえず自分の用途では動いたのでアップ。

#!/usr/bin/perl

use strict;
use warnings;

use App::Options(
  option => {
    indir => "type=string; required; default=Unknown;",
    outdir => "type=string; required; default=Unknown;",
    type => "type=string; required; default=Unknown;",
    width => "type=integer; required; default=Unknown;",
    debug => "type=boolean",
  },
);

use Image::Magick;
use Path::Class;

my $image = Image::Magick->new;

my $dir = Path::Class::Dir->new($App::options{indir});
while (my $file = $dir->next) {
  my $absin = $file->absolute;
  my $image = Image::Magick->new;
  next unless $absin =~ m|$App::options{type}$|;
  $image->Read($absin);
  my ($now_width, $now_height) = $image->Get('width', 'height');
  my ($x_start, $y_start, $x_width, $y_height);
  if ($now_width < $now_height) {
    my $retio = $App::options{width} / $now_width;
    my $new_height = int($now_height * $retio);
    $image->Resize(
      width => int($App::options{width}),
      height => int($new_height),
      blur => 0.9
    );

    ($now_width, $now_height) = $image->Get('width', 'height');
    if ($now_width < $now_height) {
      $x_start = 0;
      $x_width = 0;
      my $margin = int(($new_height - $App::options{width}) / 2);
      $y_start = 0;
      $y_height = $margin ;
      $image->Crop(geometry=> $x_start."x".$y_start."+".$x_width."+".$y_height);
      $image->Crop(geometry=> $x_start."x".$y_start."+".$x_width."-".$y_height);
    }
  }
  else {
    my $retio = $App::options{width} / $now_height;
    my $new_width = int($now_height * $retio);
    $image->Resize(
      width => int($new_width),
      height => int($App::options{width}),
      blur => 0.9
    );

    ($now_width, $now_height) = $image->Get('width', 'height');
    if ($now_width > $now_height) {
      $y_start = 0;
      $y_height = 0;
      my $margin = int(($App::options{width} - $new_width) /2);
      $x_start = 0;
      $x_width = $margin;
      $image->Crop(geometry=> $x_start."x".$y_start."+".$x_width."+".$y_height);
      $image->Crop(geometry=> $x_start."x".$y_start."-".$x_width."+".$y_height);
    }
  }
  if ($absin =~ m|^.+/(.+?)$|) {
    my $filename = $1;
    my $absoutdir = Path::Class::Dir->new($App::options{outdir})->absolute();
    $image->Write("$absoutdir/$filename");
  }
}

先日から、アルゴリズムデザインを読んでるのですが、
読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]

■序文
アルゴリズム的思考
- 情報科学の分野で、通常見えなかったものが見える

アルゴリズムの設計
- 問題の数学的な核の抽出
- 適切なアルゴリズム設計技法

■本書のスタンス
2つのアクションに、手法を提供する
- 複雑な計算問題から、問題の定式化を発見する
- 定式化に基づく、効率よいアルゴリズムの設計する

■共通のアプローチ
1、新しい問題がNP-完全かどうかを見極める。
2、NP-完全だったら近似、局所探索、特別な構造を抽出、などを試みる
3、問題を解決する

■第1章
代表的なアルゴリズム問題を紹介

1、安定マッチング
- 本書のスタンスや、アプローチの例として最適
2、グリーディアルゴリズムで解ける問題
3、動的計画法で解ける問題
4、ネットワークフローで解ける問題
5、NP-完全な独立集合問題
6、PSPACE-完全な問題


■1.1 安定マッチング
以下を説明しやすい好例
- アルゴリズムの正当性の証明
- 解の取得に必要な計算時間の上界

好例な理由
- 実際の問題から自然に生じた
- 問題の定式化が単純明快
- 問題解決のアルゴリズムも明快

■問題1.1 安定マッチング：問題の背景と定式化
Stable Matching
- 1962年
- David Gale & Lloyd Shapley
-- 数理経済学者

プロセスを自己規制的であるように設計
- 大学入試
- 就職活動

Self-enforcing

■自己規制的：Self-enforcing
個人の価値観に基づく規制を組み込むこと

目的
- プロセスを構成する集合間の不誠実な裏取引を制限する

■具体例
ある日、佐藤くんが「おいしいレストランA」を予約。

佐藤くんは「さらにおいしいレストランB」を発見。

佐藤くんは、Aをキャンセルし、Bに予約する。

Aは小林くんに「予約空いたよ」と連絡

小林さんは予約していた「B級レストランC」をキャンセル。Aに予約。

グルメ評論家がBに予約をねじこんだ。
実はBは有名店になりたかった。。。
Bは既に予約していた鈴木くんに「予約取り消し」を伝える

鈴木くんは・・・
Cは・・・

以下カオス

■例の問題
問題：一連の流れに自己規制がない！

- 客もレストランも利己的だった
-- 利己的行動は破滅につながる
-- 良くもわるくも状況が安定しない

■例題の状況を安定させる方法
以下の2条件のうちどちらかを成立させる

a、レストランは、新規の顧客より予約済みの顧客を好む
b、顧客は、新しいレストランより、予約済みのレストランを好む

■具体例
ある日、佐藤くんが「おいしいレストランA」を予約。

佐藤くんは「さらにおいしいレストランB」を発見。

「佐藤くんは、Aをキャンセルし、Bに予約する。」
→　キャンセルしない

「Aは小林くんに「予約空いたよ」と連絡
小林さんは予約していた「B級レストランC」をキャンセル。Aに予約。」
→　予約が空かないし、キャンセルしない

「グルメ評論家がBに予約をねじこんだ。
実はBは有名店になりたかった。。。
Bは既に予約していた鈴木くんに「予約取り消し」を伝える」
→　ねじ込めない

「鈴木くんは・・・
Cは・・・」
→　悩む必要がない

「以下カオス」
→　カオさない

■定式化
- 単純化
- 好意順の概念を導入

■「！」：問題は単純化しよう
問題のポイント
- 顧客とレストランには非対称性がある
→「顧客はひとつのレストランを探し、レストランは複数の顧客を探す」

非対称性は定式化を複雑にする！
- 複雑である必要がない

→まずは、複雑性を除去し単純に考えよう

■より単純な問題
n人の顧客、n件のレストラン。

1、顧客はn件全てに予約を入れる
2、レストランは一人だけ予約OKにする

■「！」：的確に単純化すれば問題ない
的確な単純化
- 問題の本質を損なわない
- より一般的な問題に容易に拡張可能

■単純版で解決すべき問題
n人の顧客
- M={m_1,..,m_n}

n件のレストラン
- W={w_1,..,w_n}

M×W
- 全ての順序対(m, w)の集合
- m∈M かつ w∈W

S
- M×Wの部分集合

■高々
≒ 多くとも = at most

順序（不等式など）の上限を表す

例、高々1つ

以下のどちらかである。
- 1つもない
- 1つある

■マッチング・完全マッチング
部分集合S中の順序対

MとWの各要素について、それ含む対は高々1個な状態
→マッチング:matching

MとWの各要素について、それ含む対がちょうど1個な状態
→完全マッチング:perfect matching

単純な例で言うと、
完全マッチングは全レストランに予約が入った状態

■好意順の概念の導入
好意順リスト : preference list
- ある集合の各要素がもつ、他の集合の全ての要素を
　好きな順にランクづけしたリスト

例、
・顧客m∈Mは、全てのレストランにランクを付けた
→mのもつ順序つきランク = 好意順リスト

・AよりBに高いランクを付ける
→AよりBの方が好き

■好意順リストは不安定性を顕在化する
不安定性
- instability

順序対の部分集合Sが自己規制的ではない対を含む
→ Sに関する不安定性、と呼ぶ

例、
ペア(m, w)と(m', w')を考える
もし、mはwよw'が好き、w'はm'よりmが好き、なとき
顧客mがレストランw'に行くのは仕方がない。
→　これは、自己規制的ではない！！

■安定(Stable)である、ということ
→順序対の集合が不安定性を持たない

安定であるとき、以下を満たす
1、完全マッチングである
2、Sに関する不安定性がない

■安定マッチングへの疑問
1、 どんな好意順リストの集合に対しても、
　　安定マッチングはある？

2、 与えられた好意順リストの集合に対して、
　　安定マッチングがあるならば、
　　いつでも効率よく安定マッチングを求められる？

■不安定性の発生条件
不安定性は、以下が満たされると発生する

1、 各順序対すべてに、現在の順序対を離れて
　　新たな順序対を作りたがる要素がいる
2、 さらに、それらの要素から新たに理想の順序対を作れる

→ある要素Aが要素Bと順序対を作りたくても、
　すでにBが別の順序対の要素であり、
　かつ、要素Aよりもランクの高い要素と対なら、
　不安定性は発生しない。

■安定マッチングはひとつだけ、ではない
m  : w > w'
m' : w > w'
w  : m > m'
w' : m > m'
→ (m, w), (m', w')

m  : w > w'
m' : w < w'
w  : m < m'
w' : m > m'
→ (m, w), (m', w')
→ (w, m'), (w', m)

これは興味深い！！

■アルゴリズム1.1 安定マッチングアルゴリズム
Stable Matching Algorithm

Gale-Shapleyアルゴリズム(G-Sアルゴリズム)
入力：2つの集合と、各集合がもつ全好意順リスト
出力：完全マッチングな順序対集合

■解析
以下つづく

「アルゴリズムデザイン 読書メモ」関連エントリ

ちょっと前にチャレンジして、
どうにもうまく動かなかったperl-completion.elにチャレンジ。

新しくなってるかもしれないので、
auto-complete.elを更新。

- EmacsWiki: auto-complete.el
-- http://www.emacswiki.org/cgi-bin/emacs/auto-complete.el

あ、新しくなってた。

anything.elも更新したり、他の記事を探したり。
そんななか、以下の記事を読んでいてうなづいてしまった。

- 例のあれ（仮題）・私とanything.el。
-- http://reiare.net/blog/2008/09/28/anything/

Googleを見ていたら、伊能忠敬は1745年2月11日に生まれたのだと気がつきました。



- 伊能忠敬 - Wikipedia
-- http://ja.wikipedia.org/wiki/%E4%BC%8A%E8%83%BD%E5%BF%A0%E6%95%AC

今日尽きたもの。

- 万年筆のインク。

去年から北林さんから頂いた、LAMYのサファリを使ってます。

LAMY/ラミー サファリ イエロー 万年筆 (F) L18-F

[Amazonで詳細を見る]

LAMY/ラミー カートリッジインク【ブルーブラック】

[Amazonで詳細を見る]

「誤解」は相手に情報を与えてないから起こるのです。

普段から十分に正確な情報を与えていれば、
誤解されて困るということは起こらないはずなのです。

と、そうでも考えないと、毎日元気にやってられません。

ふと、

「分かってもいないあなたから、それは言われたくない！」

と、思うときや、

「見てもいないあなたが、何故そうだと分かるのだ！」

ろ、思うときがありませんか。

僕はときどきありますよ。

そういう風に自分が思う時に、考えることは、

相手からしてみると、
「まさにそのように感じたり見えたりする」から、
そういう発言をするんだ、ということです。

もし、相手の発言をきいた自分が不本意だとしたら、
それは、自分が相手に情報を与えていなかったり、
相手の前での態度や言動が微妙だったりするのでは、
ないでしょうか。

相手に情報を沢山伝えていれば、
相手の前で人前と同じように振る舞っていれば、
相手の前で気の抜けたことを言わないようにしていれば、
そしたら、どうなっていたでしょうか。

どうにもならない可能性もありますが、
何もしないよりはマシです。

自分のアクションで自分の不満が解消するなら、
これは本当に最高ですね。

と。自戒の念をこめまくって書いてみました。

このブログの上部には、長年ピザのバナーが貼ってあります。



ちなみにクリック率は凄くわr、、です。

何故だと思いますか？

それは

「LinkShareのログイン用のパスワードを忘れた」

からですよ。ほんとに。

他のに変えたくても変えられないし、
登録時に使ったメールアドレスが破棄されてるんです。

郵便を使ったパスワードの変更手続きがめんどうすぎで
思わず2年も経過してしまいました。

で、今日、夢で見たんですよ。パスワードを。

起きたときに「まさかね」と思いつつ入力したら、
普通にログインできたので思わず大声をあげちゃいました。

ということで、上部のバナーがピザじゃなくなる日も近いでしょう。

にんにくを電子レンジで調理して食べるのが好きです。

つくりかたは超簡単。

1, にんにくを丸々1個用意する。皮を剥かない。
2, にんにくをラップでくるむ。隙間が無いように。
3, ラップでくるんだにんにくを、電子レンジで90〜120秒加熱。
4, ラップを皮を剥いて、一粒づつ食べる。

ほんの120秒でホクホクにんにくのできあがりです。
そのまま食べても美味しいですが、塩、味噌、マヨネーズ、カレー粉、焼き肉のタレなどが合います。

電子レンジでちゃんと加熱すると、匂いの成分のアリナーゼは熱に弱いから壊れてくれるので、食中や食後に匂いがしません。すごい！
# 食べてて辛味を感じたら、再度加熱すると良いでしょう。

台所ににんにくが転がっていたら、是非試してくてください。

旨みスタミナにんにく料理 (西川治の食材まるごとシリーズ)

[Amazonで詳細を見る]

今日はよく寝てました。

午前3時から、午後14時まで寝てました。
寝過ぎ。

朝食と昼食を食べ損ねた。。。

朝時間.jp わくわく朝ごはん

[Amazonで詳細を見る]

最近、また、「今やっていること」の管理に波が来てる感じがします。

Doingリストとして言及がされているのを見かけました。

- ゆっくりと動きながら高速でこなす、一流の研究者の Doing リスト | Lifehacking.jp
-- http://lifehacking.jp/2008/03/doing-list/

はじめてのGTD ストレスフリーの整理術

[Amazonで詳細を見る]

ああ、ポメラが欲しい。

今買えば、新ファームになってるから色々安心なのか。

KINGJIM デジタルメモ「ポメラ」

[Amazonで詳細を見る]

最近の睡眠時間は4時間くらい。

5時に寝て8時半に起きてます。
あと、お昼ご飯食べたあと眠くなります。

これは、自慢できることじゃなく、完全に不健康な証拠。

もっと早く寝ましょう。はーい。

快適睡眠のすすめ

[Amazonで詳細を見る]

今日はアルゴリズムデザイン勉強会でした。

教科書は「アルゴリズムデザイン」です。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

[Amazonで詳細を見る]

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

[Amazonで詳細を見る]