No Such Blog or Diary

並列化しやすいプログラムを入れると並列化してくれる．手でOpenMPのディレクティブ(parallel for)書いた位には．

でもちょっと複雑なプログラムになると何もしてくれない．ま，そんなもんか．

あいにくの曇天で空と桜の境がわからない…　とりあえず良く咲いていた．むしろ桜吹雪な勢いで散っていたかもしれない．

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

桜よりも源平桃のほうが面白かった．赤白が同じ木に咲く．赤白半々の花も４つくらいは見つけられた．そのなかでいい位置にいたやつ．

EF400mm F5.6L USM + EF1.4xII + trimming-1200x1200

それにしても人多すぎ．臨時門が開いてたくらいに．互いに邪魔になるので平日のが良かったかも．

今度は玄関（土間部分）で水漏れしやがって水溜りを作りやがっている．放って置く訳にも行かないので管理会社へ電話．折り返し水道屋から15:00～16:00の間に行きますんでとの連絡．

が，しかし，時間になっても水道屋現れず．その後も続けて部屋で待機してたが連絡もない．とりあえず時間を返せバカヤロウ．

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

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

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

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

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

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 と住み分けるのが面倒．