前の月 / 次の月 / トップページ
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

2009-02-21 Sat

「未踏」の2008年度上期 田中・石川PM 合同成果報告会にLuxの発表を聞きにいった

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

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

- - - 

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

- - -

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

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

- - -

Strage Interface
Strage Structure Interface 
Strage Structure (論理構造:転置index、ハッシュとか)
Strage Engine Interface 
Strage Engine (Lux IOとか、QDBMとか)

- - -

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

- - -

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億件の文書を扱える。


山田さん、とりぜあえず、お疲れさまです!!(まだ期間はあるけど。。)

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-17 Tue

アルゴリズムデザイン 読書メモ1-2

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

アルゴリズムデザイン: 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)を示せたんじゃないかな。

以下つづく。


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


- アルゴリズムデザイン 読書メモ2-2
- アルゴリズムデザイン 読書メモ2-1
- アルゴリズムデザイン 読書メモ1-2
- アルゴリズムデザイン 読書メモ1-1

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-16 Mon

地獄谷温泉

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

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

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

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

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

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

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

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

おおおお、猿、猿、猿、猿だらけや!


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


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


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


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


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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-15 Sun

六本木・赤坂でランチ価格は、スキー場並み

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

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

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

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

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

戸隠スキー場でスキー

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

スキー場

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

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

人大杉

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

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

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

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

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

大盛り過ぎ

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

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

コース全然分からん

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

初級者コース

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

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

すっからかん

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-14 Sat

かっぱ寿司の醤油は、スナック菓子の味がする件

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

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

おみくじで3回連続で大吉が出た

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

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




1回目

これは、本気で引いたら大吉が出た。素直な結果。

2回目

**で「80〜90年前のおみくじ」という宣伝文句のおみくじを見つけてしまい、
ついつい引いてしまった。で、引いたら大吉。

**のくじは、棒に吉凶が書いてあるので引いた瞬間に結果が分かる。

「おおお!!」と思い、大喜びで引き出しを開けたら、

「このひきだしのおみくじは無くなりました。もう一回引いてください。」
と書いたシールが貼ってあった。

3秒くらい放心した。

斬新すぎる。。。

3回目

おもしろいなぁと思いながら気持ちを切り替えて引いたら、
今度は違う番号の大吉!

すげえ!




いずれも、すごく強く「大吉でろ!」と思いながら、
くじ箱をかき混ぜ、「ここだ!」と感じたら引きました。

強く思うとうまくいくなんて、とっても非科学的ですが、
別に全く害は無いし、強く思っておけば良いのでは。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

万華鏡をスクリーンに投影すると綺麗!

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

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

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

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

善光寺の灯明祭り

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

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

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

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

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

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

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

ネギ塩ラーメン

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

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

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

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


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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

Happy 1234567890 !!

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

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

# perl -e 'print scalar localtime(1234567890),"\n";'
Sat Feb 14 08:31:30 2009


で、その瞬間を実際に迎えたわけですが、
僕はその瞬間に恵比寿駅のホームに居ました。

Twitterでは割と大騒ぎでしたが、現実世界は静かなもんでした。
だれも、カウントダウンとかしませんでした。

この世は様々な半並行する世界が絡み合って構成されている、
という具体例を目の当たりにして感じたことは、
Twitterなどのネット上以外に存在する他の半並行世界が
ネット上に引きずり込めると良いのになということです。

やっぱりコミュニティ系サービスが最強なのかな。。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-13 Fri

指定フォルダ以下の画像を、一辺が指定長の正方形に加工するPerlスクリプト

縦横長がバラバラの画像集合を全部まとめて、
「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");
  }
}


しばらく自分で使いながらデバッグします。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-12 Thu

アルゴリズムデザイン 読書メモ1-1

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

アルゴリズムデザイン: 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つの集合と、各集合がもつ全好意順リスト
出力:完全マッチングな順序対集合

■解析
以下つづく


今後も気が向いたら公開する予定。

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


- アルゴリズムデザイン 読書メモ2-2
- アルゴリズムデザイン 読書メモ2-1
- アルゴリズムデザイン 読書メモ1-2
- アルゴリズムデザイン 読書メモ1-1

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

Emacsでflymake.el + auto-complete.el + anything.el + perl-completion.el


ちょっと前にチャレンジして、
どうにもうまく動かなかった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/

私は“Mac”erで“ことえり”erでありますから、“C-;”というショートカットはさり気に重要なのです。


ですよね。

ということで、設定をいただきます。

- 例のあれ(仮題)・私とanything.el。
-- http://reiare.net/blog/2008/09/28/anything/
;;; anything.el
(mac-add-ignore-shortcut '(ctl ?'))
(require 'anything)
(require 'anything-config)
(require 'anything-match-plugin)
(setq anything-idle-delay 0.3)
(setq anything-input-idle-delay 0.2)
(setq anything-sources
  (list anything-c-source-buffers
    anything-c-source-files-in-current-dir
    anything-c-source-recentf
    anything-c-source-file-name-history
    anything-c-source-bookmarks
    anything-c-source-locate))
(define-key anything-map (kbd "C-p") 'anything-previous-line)
(define-key anything-map (kbd "C-n") 'anything-next-line)
(define-key anything-map (kbd "C-v") 'anything-next-source)
(define-key anything-map (kbd "M-v") 'anything-previous-source)
(define-key global-map (kbd "C-'") 'anything)


anything本体は、以下の記事を参考にもってきました。

- 巷で話題の anything.el を使ってみた — ありえるえりあ
-- http://dev.ariel-networks.com/Members/matsuyama/open-anything-emacs
以下の URL から anything.el と anything-config.el をダウンロードして load-path の通ったところにインストールします。


http://www.emacswiki.org/cgi-bin/wiki/download/anything.el
http://www.emacswiki.org/cgi-bin/wiki/download/anything-config.el

他のプラグインももってきます。

- anything.elとプラグイン等をリリース - ’(rubikitch wanna be (a . lisper))
-- http://d.hatena.ne.jp/rubikitch/20080908/anything
素のanything.elだと候補の絞り込みに正規表現をひとつしか指定できないものを、複数個の正規表現を書けるようにしました。しかも、完全一致候補→先頭一致候補→その他の順で候補を表示するので目的の候補を探しやすくなっています。anythingユーザーは入れておくと幸せになれるでしょう。どんどん絞り込みましょう。


http://www.emacswiki.org/cgi-bin/wiki/download/anything-match-plugin.el

ここまで揃ったら、perl-completionをゲッット。

- /lang/elisp/perl-completion/trunk/perl-completion.el -- CodeRepos::Share -- Trac
-- http://coderepos.org/share/browser/lang/elisp/perl-completion/trunk/perl-completion.el

設定を書く!

(add-hook 'cperl-mode-hook
           (lambda ()
             (require 'perl-completion)
             (add-to-list 'ac-sources 'ac-source-perl-completion)))


emacsを起動すると、最初はモードは

(CPerl AC Flymake:2/0


なんだけど、自分で

M-x perl-completion-mode


すると

(CPerl PLCompletion AC Flymake:2/0


になった。自動で起動されるとうざいこともあるから丁度良い。

以降、便利に使い始めている。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-11 Wed

今日は伊能忠敬の誕生日らしい

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

伊能忠敬

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

延享2年(1745年)1月11日、神保貞恒の次男として上総国山辺郡小関村(現・千葉県山武郡九十九里町小関)の名主・小関五郎左衛門家で生まれる。


56歳から測量開始、って、すごく夢がありますね。

僕は、まだ56歳じゃないし、今よりもっと頑張らねば。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-11に尽きたもの

今日尽きたもの。

- 万年筆のインク。

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

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

[Amazonで詳細を見る]


これに入れるインクが丁度なくなりました。

ブルーブラックを使っているので買わなきゃ。

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

[Amazonで詳細を見る]

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

誤解は情報を与えてないから起こる

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

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

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

ふと、

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

と、思うときや、

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

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

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

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

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

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

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

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

パスワードを思い出した

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

このブログ

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

何故だと思いますか?

それは

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

からですよ。ほんとに。

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

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

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

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

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

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

レンジで簡単、ホクホクにんにく

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

つくりかたは超簡単。

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

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

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

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

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

[Amazonで詳細を見る]

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

今日はよく寝た

今日はよく寝てました。

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

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

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

[Amazonで詳細を見る]


やけに寒いなぁ、と思いつつ外に出たら雨が降っていました。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

2009-02-10 Tue

Doing リストといえば Task*Pad かな

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

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

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

黄色いノートパッドはそんな彼を脱線させないための「いま、何をしているか」のリストなのだということが見て取れました。実際、彼はリストに書かれている以外のことは、いっさい実行していません。


僕はDoingリストと聞くと、Task*Padを思い浮かべてしまいます。
百式の田口さんのツールです。

Task*Pad
- http://www.taskpad.jp/jp/

かなりシンプルだし、使っていて楽しいとか全くないですけど。
でも、使っていると戦っている感じのするアプリです。

で、そう言っている自分が実際にはどうしているか、というと

- ブラウザを頻繁使っているとき → 大きめな付箋紙
- ブラウザを頻繁に使っておらず、画面にスペースがあるとき → Task*Pad

という2つの使い分けをしています。

Task*PadはWebアプリなので、結局のところ
ブラウザが使えない状況、または、使いにくい状況では
使っているのが煩わしくなるのです。そういうときは付箋紙。
付箋紙に今やってることを書いて、終わったら塗りつぶしてます。

一方でパソコンに向かっていて、プログラミングをしているときは、
画面の空きスペースにTask*Padが映っていると、
今やっていることが、画面に書いてあるので良い感じです。

個人的にTask*Padには以下の4つが実装されていると、
末永く使えそうな気がしています。

- 現在取り組んでいるタスクを大きめな文字で表示可能に
- 思いついたタスクを保留する機能
- 保留タスクのソートを容易に
- タスクリストの保存機能。textファイルをダウンロードとかでも良い

ここまでやるなら、もっとリッチなアプリを使えば良い、
とも言えなくも無いです。
でもログインしなくてもこれくらいできると嬉しいす。
紙でDoingリストを扱っている感覚が、かなり良いんですよ。。

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

[Amazonで詳細を見る]

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

ポメラ欲しい

ああ、ポメラが欲しい。

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

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

[Amazonで詳細を見る]


でも、、

8000字しか打てないんじゃな、とか

もうすぐ新しいのが出るんじゃないか、とか

いろいろ考えると買えないわけですよ。

当面は我慢。臨時収入があったら買う。

楽天で「ポメラ」を調べる。

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

最近の1日の睡眠時間 = 4時間

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

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

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

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

快適睡眠のすすめ

[Amazonで詳細を見る]

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |

アルゴリズムデザイン勉強会 1章1日目

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

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

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

[Amazonで詳細を見る]


大学の教科書として用いられているので、すごく分かりやすいです。

今日の消化範囲は

- 序章
- 第一章の解答付き演習の手前

でした。演習は来週!

書いてある内容については、あとでまとめを貼付けますかね。

1章の中に含まれるアルゴリズム設計的なポイントは、

- 複雑な問題は単純化しよう
- 的確に単純化すれば、複雑なケースに応用できる。
-- 単純化しても大丈夫
- 計算時間の上界を決める要素を見極めよう
- 計算が終了するのかを確認しよう

でした。どこかで学んだことも含まれています。

この勉強会は細く長く続く予定。

全然関係ないけど、はてなでは、アルゴリズムイントロダクションを使って勉強会しているみたい。
ちょっと難しい文体で書いてある印象があるけど。どうなのかな。

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

[Amazonで詳細を見る]

投稿者:としのり  日時:23:59:59 | コメント | トラックバック |