たまたま、遊びでプログラミング問題を解いてみました。一応解けたのですが、実行速度やメモリ使用量がよろしくなかったので、ちゃんと理解しようと思ってみました。自分のための理解したことのメモです。

問題の内容

循環リストの検出です。循環リストを含むかどうか？というのはどうやって検出するかです。

最初の回答

最初に考えたのは、結局のところ、LinkedList の next に対して、終端（この問題では、null) が存在したら、それは、循環じゃないと判断できます。ただし、循環だった場合は、永遠にループしちゃうので、要素を調べて、すでに出てきたものだったら、循環と判断すれば良いです。要素を、List にぶち込んで、Contains で調べたらええやろと思ってこんな感じでコード書きました。

public class Solution {
    private List<ListNode> list = new List<ListNode>();
    public bool HasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return false;
        }
        if(list.Contains(head)) {
            return true;
        }
        list.Add(head);
        return HasCycle(head.next);
    }
}

うーん。香ばしい。でも、一応動く。ただ、結果は当然のことながらよくなく。遅いし、メモリは使っとるし散々です。ソリューションの欄をみて、模範解答を勉強してみます。

Screen Shot 2019-04-28 at 7.11.47 PM.png

模範解答１(HashSet)

模範解答その１は、考え方は私と全く同じですが、再帰を使っていないのと、Listではなく、HashTableを使ってることです。そらそっちの方が効率がいいですね。O(1) のオーダーで検索してくれるので早いに決まってます。再帰は、やっぱちょい遅いのかなぁ。影響あるのかなと思いつつ、まずは、Hashに。速さはアップですね。まぁいい感じ。でもやっぱメモリがいまいち。そら、ライブラリのHashSet使ってるからそらそうか。じゃあ、再帰はどうなるんだろう。

Screen Shot 2019-04-28 at 8.30.05 PM.png

模範解答１(再帰をやめる）

public class Solution {
    private ISet<ListNode> set = new HashSet<ListNode>();
    public bool HasCycle(ListNode head) {
        while(head != null) {
            if (head == null || head.next == null) {
                return false;
            }
            if (set.Contains(head)) return true;
            set.Add(head);
            head = head.next;
        }
        return false;
    }
}

結果を見ると、速度的には変わらず、メモリ使用量が若干ましのようです。ループと再帰を比べると、スタックに積まれることを考えると、当然の結果もします。ただ、そこまで大きな影響があるわけじゃない様子です。

模範解答２

模範解答その２は、有名なアルゴリズムらしく、ListNode のオブジェクトを２つ作って、最初のものは、Fast と呼んで、速度の係数２に、２つめは、速度の係数を１にすると、最大循環したループの長さで、２つのポインタが出会うというアルゴリズムです。

何故こうなるか？というと、循環のリストは次のようなものです。

1-> 2 -> 3 -> 4 -> 2

この場合、2 -> 3 -> 4 -> 2 -> 3.... といった具合に循環します。循環のループの要素数は３でそれが繰り返されます。さて、１つの要素の速度を２、２つめを１にするとどういうことが起こるか？というと、最初の１をのぞいて、２つめの要素（遅い方）がループに入った時点で、早い方は、すでにループに入っています。その時点で、速いのと遅いのの間にどれぐらい距離があるかわかりません。（ループの長さや、ループに入るまでの距離によります。そのループに入った時点での、遅いのと、速いのの距離がNとすると、１回ロジックが繰り返されるたびに、距離が開いていきます。N,N+1,N+2といった具合です。ただ循環ということは、円になっていますので、循環のループの数をMとすると、N+i がMになった時点で、遅いのと速いのが出会うというわけです。

よくわからないと思うのでコードをみてみましょう。

public class Solution {
    public bool HasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

なんだこれは、凄い効率とスピードじゃないか、、、ライブラリは多くのコードを含むので、メモリはそうだろうなと思ったけど、速度もクソ速い。O(N)のオーダーなのは、前のアルゴリズムと変わらないけど、メモリは、O(1) のオーダーになったはず。同じO(N) のオーダーなのに速い理由はなんだろう。最短で、List size で終了するはずで、ループでも、ポジションP+ 循環要素数で終わるはず。

Screen Shot 2019-04-28 at 8.36.48 PM.png

ちなみに、このアルゴリズムは最初なかなか理解でき戦でしたが、このページで理解できました。

How does Floyd’s slow and fast pointers approach work?

まとめ

アルゴリズムのイディオムすげぇ。こんなの絶対思いつかないから勉強するしかないなぁ。でも理解できて気持ちが良いです。