串行要七轮,并行要几轮
还是那七个构建任务。这次机器不限:一轮里所有"依赖都做完了"的任务可以同时开工。下面这段把任务分成一层一层,每一层里的任务可以同时开工。输出串行轮数和并行轮数:
DEP = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6)]
N = 7
def layers(edges):
g = {u: [] for u in range(N)}
d = {u: 0 for u in range(N)}
for a, b in edges:
g[a].append(b)
d[b] += 1
cur = sorted(u for u in range(N) if d[u] == 0)
out = []
while cur:
out.append(cur)
nxt = []
for u in cur:
for v in g[u]:
d[v] -= 1
if d[v] == 0:
nxt.append(v)
cur = sorted(nxt)
return out
L = layers(DEP)
print(str(N) + "/" + str(len(L)))
全部评论