こんにちは
今回の学びは
・この問題の肝はサイクリックの判定 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の掛け合わせでクリア
以上です