No Such Blog or Diary

Driscoll, J. R., Gabow, H. N., Shrairman, R., and Tarjan, R. E. Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM 31, 11 (Nov. 1988), 1343-1354.

実用的に使える，殆どの演算がフィボナッチヒープと同じ計算量になるヒープ．二項ヒープがベース．

ただの二項ヒープだとすべての演算がO(log n)だけど（ノード数nで），ヒープ条件満たさないノードが log n 個くらいあってもいいよねとする．結果として，insert と decrease_key が O(1) になる．最小を取ってくる delete_min と最小を見る find_min とヒープをマージする union は O(log n) を保つ．フィボナッチヒープの decrease_key はならしでO(1)だけど，Relaxed heap のは最悪計算量でO(1)である点が賢い．

基本，ヒープ条件を壊したノードを覚えておいて，その数が log n を超えたときにはO(1)の操作でヒープ条件を壊したノードの数を1以上減らす．ヒープ条件を壊したノードのペアを持ってきて，適当にノードの入れ替えをすると条件を満たさないノードの数が減る．この操作をO(1)でやるために条件を壊したノードの連続やペアを保持するリストを余計に持っていると．

最小の取り出しやマージの計算量は，通常の二項ヒープと同様，log n 回二項木を結合すれば操作が完了することから保証される．最小の読み出しの計算量は，最小値が各二項木のルート（最大 log n個）かヒープ条件を壊したノード（最大 log n個）であることから O(log n) になると．

そしてこれがどのように最短路の並列計算に使えるのかはまだ読んでいない．

特に問題なくRedHatのインストール完了．GnomeについてるシステムモニタでCPU利用率見ようとしたらCPU数が多すぎてウィンドウが超横長に…　いろいろと面白い．

ためしにN-queensのベンチマークプログラムを走らせて見たら，n=17のときスレッド1個で51.9秒がスレッド24個で2.24秒 （23倍）と，ちゃんと並列の効果が出てくれた．めでたしめでたし．

問題といえば Sun の JDK を入れるのが面倒なくらい．ubuntu は apt で入ってくれるのに RedHat だと yum で入らず（rpm もって来りゃいいだけだけど）．javaに依存関係のあるものを入れると openJDK とかが入っちゃうので Sun の JDK と住み分けるのが面倒．

とかいうサーバ君のセットアップをお手伝い…　とか思ったら RedHat のインストールディスクは自前で焼かないとダメなのねと．明日に持ち越し．

それはさておき明日の朝のミーティングの資料を上げなければ．

windows上でtrac用意しようとしたら失敗した…　面倒なのでVMware内のlinuxに入れるか．

「充分に発達した科学技術は魔法と見分けが付かない」ってのの元ネタ．

バーローwです。

微妙な中途半端感が漂ってはいたけれど…　ルパンサイドとコナンサイドの動きがほとんど絡まってないし…　不二子vsコナンはあったけどルパンvsコナンは…　殺人事件と盗みが全く関係ないって時点でどう考えても「ルパン//コナン」か「ルパン∨コナン」ぐらいだと思われる．とりあえず次回作に期待。