No Such Blog or Diary

飛鳥山公園と千鳥ヶ淵緑道に行ってみた．

王子駅ホームから飛鳥山公園．ちょうちん沢山．それ以上に酔っ払いが沢山．

TAMRON SP AF28-75mmF/2.8 XR Di LD Aspherical [IF] MACRO

千鳥ヶ淵緑道から武道館側の対岸．狭い歩道に人がギュウギュウ．人多過ぎ．左側通行で人の流れに乗るしかない．さらにビールくさい．

TOKINA AT-X 116 PRO DX 11-16mm F2.8

リモートのRedHatにvinagreで接続したらシフトキーが入りっぱなしの状態になってて操作不能．何が悪いのやら？　うちのマシンにつなげたときには何の問題もなかったので，RedHat側のVNCサーバとの最小が悪いのだろうか？

とりあえずの解決策として，Ubuntu 内の VMware 内の Windows から UltraVNC 使って接続…　とかいう使い方をしている．アホだ…

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に入れるか．