No Such Blog or Diary

Kruskal はソートと union/find があれば出来る．Prim はヒープ(バイナリヒープ)があれば出来る．これだけみると Prim のほうが単純そうなんだけどなぁ…　ゼロから実装してみた感じでは Kruskal の方が断然単純だった気がする．実用上はどっちの方が速いのだろうか？

熱暴走．人間が．

どうやら風邪を引いたらしい．そんなに寒くなかったのに昨日はくしゃみ連発しとったからなぁ．

経路圧縮とランクによる合併操作をあわせる，n 要素で操作回数が m 回のときに O(m a(m,n)) とのことだが，何で Ackermann 関数の逆関数 a(m,n) （正確な逆関数では無いらしいが…）が登場するのだろう？　O(m lg*(n)) の評価は原理が簡単だが a(m,n) の方は面倒らしい．機会があれば調べてみるか．どっちにしろ無視できるスピードの関数だからどうでもいいのだけど．

やっぱりJRは高かった．小田急安かった．そして御殿場線は電車が少なかった…

折角APLというものの存在を知ったので，その発展である J を少し使えるようになろうかと考えた．J の実行環境としては JSoftwareからインタプリタがダウンロード可能．JAPLA のシンポジウムの資料を見つつ簡単なところからやってみる．

とりあえず，配列の定義． i. という動詞（関数）で 0 から n-1 の要素を持つ長さ n の配列を作る．代入は =: ないし =. とのことで，値の出力は ] とのこと．

  ] D=: i.8
0 1 2 3 4 5 6 7

すでに分かりにくい．

ついで，reduction に手を出してみる．正確には insertion とか言うらしいが…　BMF の reduce と同じで左にオペレータを取って配列をぶっ潰す．和を求めるのも簡単．

  sum =: +/
  ] sum D
28

これはまだ分かりやすい．

次に訳の分からん（気がする）動詞の fork 合成を試す．fork は３つの動詞からなり， f g h という fork に引数 x を適用すると (f x) g (h x) とかになるらしい．こんなのどこに使えばいいか良くわからんが，とりあえず平均がこれで書ける．# は要素数を返す演算子で % は割り算（剰余ではないらしい）の演算子．

  mean =: +/%#
  ] mean D
3.5

うーん，微妙に気持ち悪い気がしなくも無い．Lisp の括弧だらけの式を読むのと APL ないし J の式を読むのとどっちが面倒なんだか…