如何提高Python实现课程表问题中周期检测的运行速度？

Question

我的目的是提高我的Python代码的速度，该代码已经成功地被接受在 闰码问题，课程表.

我知道算法，但即使我使用O(1)数据结构，我的运行时间仍然很差：大约200ms。

我的代码使用了字典和集合。

from collections import defaultdict


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        course_list = []
        pre_req_mapping = defaultdict(list)
        visited = set()
        stack = set()
        def dfs(course):
            if course in stack:
                return False
            stack.add(course)
            visited.add(course)
            for neighbor in pre_req_mapping.get(course, []):
                if neighbor in visited:
                    no_cycle = dfs(neighbor)
                    if not no_cycle:
                        return False
            stack.remove(course)
            return True
        # for course in range(numCourses):
        #     course_list.append(course)
        for pair in prerequisites:
            pre_req_mapping[pair[1]].append(pair[0])
        for course in range(numCourses):
            if course in visited:
                continue
            no_cycle = dfs(course)
            if not no_cycle:
                return False
        return True

我还能做些什么来提高速度？

Answer 1

你正在调用 dfs() 对于特定 course 多次.但它的返回值不会改变.所以我们有一个机会来 追忆 it.Change your algorithmic approach (here, to dynamic programming)for the big win.It's a space vs time tradeoff.EDIT:Hmmm, you are. 已经 记忆大部分的计算与 visited所以 lru_cache 将主要改善 clarityr而不是运行时.它只是一个熟悉的缓存结果的成语。

如果能增加一个 # 注释中引用了您所实现的算法的引用。

这是一个非常好的表达式，有默认值。pre_req_mapping.get(course, [])如果你使用 时机 你可能会发现，一个空元组生成的字节码为 () 比空列表的效率要高一点。[]好了，接下来是一些风格上的小问题，与运行时无关。

作为一个旁观者，youAreMixingCamelCase和_snake_case.PEP-8请你坚持只用snake_case。

这是一个不错的标识符名称选择。

    for pair in prerequisites:

但不要用神秘的 [0], [1] 解引用，读取元组解包会更容易。

    for course, prereq in prerequisites:

if not no_cycle: 是笨拙的，可以考虑反转dfs的返回值的含义，或者将赋值改写成。

        cycle = not dfs(course)

Answer 2

我认为你的方法很好，但是由于Python是一种解释型语言，与CC++和Java等编译型语言相比，运行速度慢是正常的，尤其是对于大的输入。

比如试着用CC++写同样的代码，比较一下它们之间的速度。