Derive Your Dreams

about me
Twitter: @kinaba

01:19 13/07/06

ソートキラー改

ここまでのあらすじ:

→ ソートの実装を渡すと、 自動でその実装の苦手な入力を作ってくれる ソートキラーを作りました
→ でも遅い。元々のソート処理が O(f(n)) として O(n2 f(n)) 時間かかる。
→ あっ O(n3 + f(n)) になった!

…という最後のステップを、コードは書いたのだけど説明どこにも書いてなかったのでメモ書きです。 本当にメモ書きであんまりわかりやすく書いてないので、気になる人だけ読んで下さい。 あと、特にたいしたことではないのでアルゴリズム得意な人には自明だと思われます。

説明

古いバージョンも新しいバージョンも、やっていることの流れは、こうです。

この一連の操作は、x-y から連鎖的に埋まるものを探すときに、確定済みの a-x と y-b について a-b ペア全てに影響します。つまり最悪で O(n2) 時間、というわけで O(n2 f(n))、 というのが最初の記事を書いた時点での評価。実際の実装もそれだけかかっていました。

ところで、一回あたりの最悪は確かに O(n2) なのですが、 そもそも埋めるマスが全部で n2 マスしか存在しないことを考えると、 全部のコストを合わせると、O(n2 × 回数) ではなく、もっと少なくできそうです。

実際これは可能で、"x-y:小さい" を埋めるときにどこまで辿れば良いかというと

くらいで、"まだ埋まってなければ"で外れを引く可能性があるのが曲者ですが、 それにしても、(実際に埋めた数 × 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 をソートキラーに応用しようとすると、

という意味で一般の場合よりは限定されていることが使えないか等が気になります。 逆に、更新で何マス埋まるか(あるいは何か別の基準で、どちら向きで更新した方がソートを遅くできるか) の判定も高速にできて欲しい、という要求があるのは、問題を難しくしています。 Ibaraki&Katoh の方法は埋まるマス数の比較にもほぼストレートに適用できましたが、 もっと複雑なアルゴリズムではそうとも限らない。

さてさて。しかし、Transitive Closure をほぼ部分問題として含んでいるとなると、 n3 が限界かなあという気はしてきます。とりあえず DAGの場合の研究 を読んでみたりしているところです。

presented by k.inaba (kiki .a.t. kmonos.net) under CC0