如何提高迭代方法，使其比递归实现更快？

Question

在用Python实现深度优先搜索（DFS）时，我尝试了不同的方法并测量了它们的性能，发现使用递归的DFS相对更快。通常情况下，递归的性能比迭代要差，因为它需要频繁切换上下文，但在DFS的情况下似乎并不是这样。我的分析表明，Python内部将栈结构表示为一个列表，这可能会导致时间消耗很大。这是否意味着在Python中，我们无法像在C语言中那样高效地利用计算机的栈结构呢？我尝试通过使用Python中的deque来改进DFS的栈实现，但递归的DFS速度仍然更快。

我的代码

from collections import deque
import time

def rec_dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    #print(start)
    for i in graph[start]:
        if i not in visited:
            rec_dfs(graph, i, visited)

def itr_dfs(graph, start):
    visited = set()
    stack = deque([start])
    while stack:
        node = stack.pop()  # 마지막 요소를 꺼내어 탐색할 노드로 설정
        if node not in visited:
            visited.add(node)
            #print(node)  # 노드를 방문했음을 출력
            # 그래프의 인접한 노드들을 역순으로 스택에 추가
            stack.extend(reversed(graph[node]))

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': ['P', 'Q'],
    'I': ['R', 'S'],
    'J': ['T', 'U'],
    'K': ['V', 'W'],
    'L': ['X', 'Y'],
    'M': ['Z', 'A1'],
    'N': ['B1', 'C1'],
    'O': ['D1', 'E1'],
    'P': [],
    'Q': [],
    'R': [],
    'S': [],
    'T': [],
    'U': [],
    'V': [],
    'W': [],
    'X': [],
    'Y': [],
    'Z': [],
    'A1': [],
    'B1': [],
    'C1': [],
    'D1': [],
    'E1': []
}

# 시작 노드를 지정하여 DFS 실행
start_node = 'A'

an = input()
t1 = time.time()
for i in range(10000):
    rec_dfs(graph, 'A')
t2 = time.time()
print(t2 - t1)

ans = input()
t3 = time.time()
for i in range(10000):
    itr_dfs(graph, 'A')
t4 = time.time()
print(t4 - t3)

结果：

0.05646324157714844

0.07860183715820312

Answer 1

你提到的两个实现方式都使用了栈。第一个使用的是调用栈，而第二个则是用一个显式的栈。它们之间有几个不同之处，这些不同会影响性能：

1. 调用栈是自动管理的，使用的是编译后的代码（CPython），这比需要用Python代码来管理的栈（比如用extend和pop）要更有优势。

2. 第二个实现并没有完全按照递归的方式来处理。它提前把需要访问的内容放入栈中，这意味着在访问完第一个孩子的子树后，栈的占用空间可能会比递归版本要大。此外，使用reversed迭代器也会增加一些额外的开销，我们还需要考虑到内存分配也会消耗时间。

对于第一个问题，我们没办法做太多，所以用基于栈的迭代实现也不指望能有更好的表现。不过，针对第二个问题，我们可以尝试写一个更接近递归版本的迭代实现：

def itr_dfs2(graph, start):
    visited = set()
    stack = deque()
    current = iter([start])
    try:
        while True:
            for node in current:
                if node not in visited:
                    visited.add(node)
                    stack.append(current)
                    current = iter(graph[node])
                    break
            else:
                current = stack.pop()
    except IndexError:
        pass

在这里，栈里存的是迭代器，而不是节点。这更像是递归实现，其中for循环的状态是栈帧的一部分，当递归调用返回时，这些循环会继续执行。

为了测量代码的执行时间，最好使用timeit，并取多个测量中的最小值（使用timeit.repeat），这样可以排除一些机器负载的影响。所以我把时间测量的代码改成了这样：

import timeit

n = 10000
r = 5
t1 = min(timeit.repeat(lambda: rec_dfs(graph, 'A'), repeat=r, number=n))
t2 = min(timeit.repeat(lambda: itr_dfs(graph, 'A'), repeat=r, number=n))
t3 = min(timeit.repeat(lambda: itr_dfs2(graph, 'A'), repeat=r, number=n))
print(t1)
print(t2)
print(t3)

我得到的结果显示，t3的时间通常（但不是总是）介于t1和t2之间。