01:19 13/07/06
ソートキラー改
ここまでのあらすじ：
→ ソートの実装を渡すと、
自動でその実装の苦手な入力を作ってくれる
ソートキラーを作りました。
→ でも遅い。元々のソート処理が O(f(n)) として O(n2 f(n)) 時間かかる。
→ あっ O(n3 + f(n)) になった！
…という最後のステップを、コードは書いたのだけど説明どこにも書いてなかったのでメモ書きです。 本当にメモ書きであんまりわかりやすく書いてないので、気になる人だけ読んで下さい。 あと、特にたいしたことではないのでアルゴリズム得意な人には自明だと思われます。
説明
古いバージョンも新しいバージョンも、やっていることの流れは、こうです。
- 要素xは要素yより {小さい,大きい,わからない} の3状態を記録した n×n の表を準備。 初期値は "わからない"。
- ソート関数に「xはyより小さいですか？」と聞かれたら、表を引く。 "大きい" or "小さい" が既に入っていればそれを返す。
- "わからない" が入っていたら、"小さい" を埋めた場合に連鎖的に埋まるマスの数を数える （たとえばy-zに既に"小さい"が入っていたら、x-yと合わせるとx-zも"小さい"が確定する）。 "大きい"を埋めた場合に連鎖で埋まるマスの数も数える。
- 埋まる数が少ない方を選んで、実際に表を埋めて、その答えをソート関数に返す。
この一連の操作は、x-y から連鎖的に埋まるものを探すときに、確定済みの a-x と y-b について a-b ペア全てに影響します。つまり最悪で O(n2) 時間、というわけで O(n2 f(n))、 というのが最初の記事を書いた時点での評価。実際の実装もそれだけかかっていました。
ところで、一回あたりの最悪は確かに O(n2) なのですが、 そもそも埋めるマスが全部で n2 マスしか存在しないことを考えると、 全部のコストを合わせると、O(n2 × 回数) ではなく、もっと少なくできそうです。
実際これは可能で、"x-y:小さい" を埋めるときにどこまで辿れば良いかというと
- 既に埋まってる "a-x:小さい" があったら、"a-y:小さい" を(まだ埋まってなければ)埋める
- 既に埋まってる "y-b:小さい" があったら、"x-b:小さい" を(まだ埋まってなければ)埋める
- 2ステップ目で実際に埋めた "x-b:小さい" に対して、既に埋まっている "a-x:小さい" があったら、 "a-b:小さい" を(まだ埋まってなければ)埋める
くらいで、"まだ埋まってなければ"で外れを引く可能性があるのが曲者ですが、 それにしても、(実際に埋めた数 × n) マスくらいしか調べに行きません。 ということは、トータルで n2 しか実際に埋めるマスが存在しないことを考えると、 埋める処理の部分にかかるステップ数は、全体合わせて O(n3) です。
残る問題は、"大きい"を埋めた場合と"小さい"を埋めた場合の埋まるマスの数を数えるパートです。 どちらかの候補は捨ててしまって実際には埋めないので、 「トータルで n2 しかマスがない理論」ではすぐには抑えることができません。
が、ここは正確に数を数える必要はなくて、どっちが埋めるマスの個数が小さいかだけわかればよいので、 いわゆる運動会の玉入れ方式、両方せーので「いち、に、さん、…」と埋まるマスを数えていって、 先に尽きた方が少ないのでそこで処理を打ち切ります。Ruby等のenumeratorで実装すると打ち切るの楽でした。 少ない方で列挙したマスは実際に全部埋めるので、 この打ち切りはトータル「トータル n2 マス」で抑えられます。
以上。
動的推移閉包
この問題の 表を引く、表を埋める の部分は Dynamic Transitive Closure という名前のついた問題で、いろいろな研究がされている分野のようです。 上に書いた方針は、この分野のはしりとなった "On-line Computation of Transitive Closures of Graphs", Ibaraki and Katoh, 1983 という論文に書いてあるアルゴリズムそのままでした（さっき気づきました）。
Dynamic Transitive Closure をソートキラーに応用しようとすると、
- 一般のグラフではなくDAGである
- 更新を最後まで処理すると全順序になる
- (クエリ:x-y, クエリ:y-x, falseなら 更新:x-y(またはy-x))* という操作列しか来ない
という意味で一般の場合よりは限定されていることが使えないか等が気になります。 逆に、更新で何マス埋まるか（あるいは何か別の基準で、どちら向きで更新した方がソートを遅くできるか） の判定も高速にできて欲しい、という要求があるのは、問題を難しくしています。 Ibaraki&Katoh の方法は埋まるマス数の比較にもほぼストレートに適用できましたが、 もっと複雑なアルゴリズムではそうとも限らない。
さてさて。しかし、Transitive Closure をほぼ部分問題として含んでいるとなると、 n3 が限界かなあという気はしてきます。とりあえず DAGの場合の研究 を読んでみたりしているところです。
