Petitverse

とりあえず、部分永続Disjoint Setについておさらいしてみる。

まず、部分永続でないDisjoint Setは以下の操作ができる

union x,y …xの属するグループとyの属するグループを融合させる
find(x) … xの属するグループを返す

場合によっては以下の操作が出来る
same(x,y) …xの属するグループとyの属するグループが同じかどうか判定する
size(x) … xと同じグループに属する要素数を返す

雑に実装するとこんな感じ

DIM PARENT[1000],SIZE[1000]

DEF INIT N
　VAR I%
　FOR I%=0 TO N-1
　　PARENT[I%]=I%
　　SIZE[I%]=1
　NEXT I%
END

DEF UNION X,Y
　WHILE X!= PARENT[X]
　　X=PARENT[PARENT[X]]
　　PARENT[X]=X
　WEND
　WHILE Y!= PARENT[Y]
　　Y=PARENT[PARENT[Y]]
　　PARENT[Y]=Y
　WEND
　IF X!=Y THEN
　　IF SIZE[X]>SIZE[Y] THEN
　　　PARENT[Y]=X
　　　INC SIZE[X],SIZE[Y]
　　ELSE
　　　PARENT[X]=Y
　　　INC SIZE[Y],SIZE[X]
　　ENDIF
　ENDIF
END

DEF FIND(X)
　WHILE X!= PARENT[X]
　　X=PARENT[PARENT[X]]
　　PARENT[X]=X
　WEND
　RETURN X
END

対して部分永続Disjoint Setは以下のような操作を提供する
union x,y …xの属するグループとyの属するグループを融合させる(時刻が1増加する)
find(t,x) … 「時刻tにおける」xの属するグループを返す

過去の状態は知ることが出来るけど、過去の状態に遡ってグループを融合させるとかは出来ない(==最も新しい状態にしか変更を加えることができない)。
このようなものを部分永続データ構造と言うらしい。

部分永続Disjoint Setに関しては明確な欠点があって、普通のDisjoint Setに比べて速度が遅い(それでも十分に高速ではある)

と、言うのも、先に書いたDisjoint Setはpath-halving(経路半減)とunion-by-size(データ構造をマージする一般的なテク)という2つの高速化の工夫をしてあって、そのうち経路半減の方が部分永続と相性が悪いらしい(どちらか一方の工夫でも十分に速いけど)。