いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 207 course schedule

投稿日:

こんにちは

今回の学びは

この問題の肝はサイクリックの判定  and サイクリックの判定はdfsでできる!

・グラフでサイクリックの判定はどうする?(easy問題に出てきそう。これがとけるかどうか。まだやってないけど)

・グラフ問題への変換ができるかどうか?

・グラフとcacheの掛け合わせでクリア

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

nコース取らないといけないです。

コースにはprerequisites(前提科目)があるものあります。

(全てのコースにprerequisitesがあるわけではない)

prerequisitesはpairの形で表される。

 

アイデアは

この前提科目は、グラフ構造にして、サイクリックな状態があれば、、その

時点でアウトと考えられないか?とい発想です

 

dfsなんでO(n)でいけるはず、

 

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は 

と、

実装始めるも

ちょっと正直最初の発想よりも、何か複雑に考えてしまっている様子

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        logging.debug("nc:%s, prere:%s" % (numCourses, prerequisites))
        length = len(prerequisites)
        buffer = length * 2
        visit = [False] * buffer
        needs = [[]] * buffer
        stack = []
        if length <= 0: return True
        for i, pair in enumerate(prerequisites):
            try:
                c, p = pair
            except:
                continue
            logging.debug("course:%s, preprequisite:%s" % (c, p))
            #visit[i] = True
            needs[c] = needs[c] + [p]
            stack.append(c)

        if sum([len(x) for x in needs]) == 0: return True
        if len(stack) <= 0: return False

        non_cyclic = 0
        tmp = 0
        while len(stack) > 0:
            c = stack.pop()
            if visit[c]:
                non_cyclic -= tmp
                tmp = 0
                return False
            else:
                visit[c] = True
                for pc in needs[c]:
                    stack.append(pc)
            non_cyclic += 1
            tmp += 1
        return True

という

時は、一回深呼吸して

もう一度やり直す。ふん。時間は10分!お願いします

 

擬似コード描いてみました。

prerequisitesごとに、サイクリックかどうかを確認していく方法です

。。。

実際の実装はこちら

こちら正解は出せてますが、LTEします。

timespace analysisは O(n * len(prerequisites))になりまして、ダメと言われましたので

前回の記事を読んでくれた方で覚えている人もいるかと思いますが、LTEになったなら喜んでください

大きなヒントですから!

一応、LTEの実装を記載しました。これを今から O(len(prerequistes))で動かしていきたいと思います。

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        logging.debug("nc:%s, prere:%s" % (numCourses, prerequisites))
        length = len(prerequisites)
        paths = defaultdict(list)
        # warm up run, to instansiate all key and its value.
        # otherwise, during the paths.items, RuntimeError : dictionary changed size during iterration
        for i in range(numCourses):
            paths[i] = []
        for prerequisite in prerequisites:
            if len(prerequisite) == 0: continue # []
            c, s = prerequisite
            paths[c].append(s)
        logging.debug("paths:%s" % paths)

        def dfs_cyclic_check(edges, i, sofar=""):
            logging.debug("dfs_cyclic_check(edges, %s, %s" % (i, sofar))
            if len(edges[i]) == 0: return True
            for j in edges[i]:
                if str(j) in sofar.split(","):
                    return False
                else:
                    tmp = dfs_cyclic_check(edges, j, sofar+"%s,"%j)
                    if tmp == False: return False
            return True

        edges = list(paths.values())
        for i in range(len(edges)):
            if not dfs_cyclic_check(edges, i, "%i,"%i):
                return False
        return True

 

 

はいー

頑張りましたー、その結果

やっときたー。

キャッシュを設けてうまくいきました。cacheを入れてLTEになったサンプルケース(2000コース)が

ちゃんと早くなっているか確認していけたので提出しました。やっと通りました。

実装はこちら

sys.setrecursionlimit(1000000)
class Solution:
    @timeit
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        logging.debug("nc:%s, prere:%s" % (numCourses, prerequisites))
        length = len(prerequisites)
        paths = defaultdict(list)
        # warm up run, to instansiate all key and its value.
        # otherwise, during the paths.items, RuntimeError : dictionary changed size during iterration
        for i in range(numCourses):
            paths[i] = []
        for prerequisite in prerequisites:
            if len(prerequisite) == 0: continue # []
            c, s = prerequisite
            paths[c].append(s)
        logging.debug("paths:%s" % paths)
        cache = {}
        def dfs_cyclic_check(edges, i, sofar=""):
            logging.debug("dfs_cyclic_check(edges, %s, %s" % (i, sofar))
            if i in cache:
                logging.debug("cache hit for %s and it is %s" % (i, cache[i]))
                return cache[i]
            if len(edges[i]) == 0:
                cache[i] = True
                return True
            for j in edges[i]:
                if str(j) in sofar.split(","):
                    return False
                else:
                    tmp = dfs_cyclic_check(edges, j, sofar+"%s,"%j)
                    if tmp == False:
                        cache[i] = False
                        return False
            cache[i] = True
            return True

        edges = list(paths.values())
        for i in range(len(edges)):
            if not dfs_cyclic_check(edges, i, "%i,"%i):
                return False
        return True

 

ちなみにこれは二回目なのでメモ化( pythonで競技プログラミングをする際のチップ )しておきます。

sys.setrecursionlimit(1000000)

 

 

実装後です。timespace analysis (時間とスペースの分析)は ◯◯

ちょっと自信ないのですが、

もともとO( n * len(prerequisites)) のアルゴに

キャッシュをつけて、O (n)になったかと思っています。速度的にも、めっちゃ早くなったし。

例えば2000コースだったら一個一個潰していくうちにdfsで一回通ったところはサイクリックかどうか、判定すみ、という感じで毎回 len(preprequiste)を回らなくても

一回回ればもうキャッシュ使うよってことで、正確には O(n + len(prerequistes))みたいな感じですかね。掛ける(*)ではなく足す(+)なので、bigO分析的にはO(n)ですね。

 

実装にはめちゃくちゃ時間がかかります。

これがソフトウェアエンジニアの生産性の違いでしょうか。

猛者たちはめっちゃ早いです。私もこれまでの練習で幾分早くなってきました。

ので、これは成長しているといことでいいと思います。

もっと積み重ねて早くしていきたいです。

そのためには問題からのパターンや学びをしっかりと習得して覚えることが大切です。

 

ということで今回の学びは

この問題の肝はサイクリックの判定をどうするか?の一言です。

まとめ

この問題の肝はサイクリックの判定  and サイクリックの判定はdfsでできる!

・グラフでサイクリックの判定はどうする?(easy問題に出てきそう。これがとけるかどうか。まだやってないけど)

・グラフ問題への変換ができるかどうか?

・グラフとcacheの掛け合わせでクリア

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.