線形時間で最小全域木を作るだって!?

いまMOCKで一番ネックになりそうなのが、初期化時に全データを含む最小全域木を作るところです。最小全域木の生成アルゴリズムはいくつかあって、データ数(というかリンク数?)Nに対してO(NlogN)で最小全域木を作れるといわれているのだけど、どれも扱うリンクが最初から分かっているという想定なのです。でも実際には各データ間のリンクの重みを求めるのもそれをメモリにのせるのもO(N^2)で大変。特に大規模データではメモリ量が半端じゃない(double型ならN×N×8 [Byte])。データ数に線形なメモリ量で(つまりすべてのデータ間のリンクを考えないで)、高速に最小全域木を作れるアルゴリズムが知りたかった。もしかしたらこの文献はビンゴかもしれない。

A Linear Algorithm for Analysis of Minimum Spanning and Shortest Path Trees of Planar Graphs

Read more

OB会を休んで海外に行くとかありだろうか?

OB担当なのに内定先の会社の社員旅行(いま会社が掲げてる目標を達成すると海外らしい)に行くとか、アリ??やっぱ無しだよねぇ〜。。

まだ社員じゃないのに社員旅行に行くとか、アリ??いや、これはアリだろ。

分身の術で、どっちも行けたらいいのになぁ〜。行き先イタリアだったら迷わず旅行行っちゃいそう。

ところで全然話は変わりますが。まだ東京から帰ってきて1週間しかたってないのにまた明日東京です。いま僕が関わってるプロジェクトで、今週末までに絶対つくらなきゃいけない書類を作るため、明日は昼から夜までみっちりミーティングがあるのです。サイボウズさんによると12:00-20:00らしい。

Read more