Python中的递归函数调用与排队

Question

我有一个代码的草图，如下所示：

def func1(c):
    return a,b

def func2(c,x):
    if condition:
        a,b = func1(c)
        x.append(a,b)
        func2(a,x)
        func2(b,x)
    return x

x = []
y = func2(c, x)

从代码中你可能已经发现了问题，就是我希望在条件为真的时候，func2(b) 和 func2(a) 能同时计算。也就是说，在用 func2(a) 生成的新 b 替换掉旧的 b 之前，func2(b) 就应该开始计算。但是根据我的算法，这显然是做不到的，因为新的 b 会影响计算。

我觉得这个问题可能很适合用并行计算的方法来解决。但我之前没有用过这种方法，对它的了解也很有限。不过，我确实尝试过 如何在Python中进行并行编程 的建议，但结果和上面的草图是一样的。

Answer 1

根据你的解释，我感觉不是 b 被更新了（正如DouglasDD所说的那样，它并没有被更新），而是 x 被更新了。为了让两个递归调用都能使用同一个 x，你需要对 x 进行某种快照。最简单的方法是传递一个新添加的元组的索引，像这样：

def func2(c, x, length):
    ...
    x.append(a, b)
    func2(a, x, length + 1)
    func2(b, x, length + 1)

Answer 2

注意：使用线程可能无法达到你想要的并行效果（可以查看这个链接了解关于全局解释器锁的说明），所以你可能需要使用multiprocessing库来实现并行处理（可以查看这个链接）。

...所以我偷懒了，使用了一个不区分线程和进程的术语“任务”。你需要在我提到“任务”的地方选择使用线程还是进程。

def func1(c):
    return a,b

def func2(c,x):
    if condition:
        a,b = func1(c)
        x.append(a,b)
        a_job = None
        if (number_active_jobs() >= NUM_CPUS):
            # do a and b sequentially
            func2(a, x)
        else:
            a_job = fork_job(func2, a, x)
        func2(b,x)
        if a_job is not None:
            join(a_job)

x = []
func2(c, x)
# all results are now in x (don't need y)

...如果你需要一对一的任务同时完成，这样做会比较好。如果你愿意让调度器疯狂一点，你可以把它们都“任务化”，然后在最后join一下：

def func1(c):
    return a,b

def func2(c,x):
    if condition:
        a,b = func1(c)
        x.append(a,b)
        if (number_active_jobs() >= NUM_CPUS):
            # do a and b sequentially
            func2(a, x)
        else:
            all_jobs.append(fork_job(func2, a, x))
        # TODO: the same job-or-sequential for func2(b,x)

all_jobs = []
x = []
func2(c, x)
for j in all_jobs:
    join(j)
# all results are now in x (don't need y)

NUM_CPUS的检查可以用threading.activeCount()来完成，而不需要建立一个完整的工作线程池（可以查看这个链接了解如何获取特定类启动的活动线程数量）。

但是如果使用多进程，你需要处理更多的工作，比如JoinableQueue和一个固定大小的Pool工作池。