时间戳

首页 > 解决方案 > 如何并行化贪婪分配问题

python - 如何并行化贪婪分配问题

问题描述

我有一个大的 2D成本矩阵：500K x 500K，我想解决分配问题。除了匈牙利算法，我想使用下面的贪心算法来减少时间：

# H1,H2 in range(500K)
for n1 in H1:
    best = -1
    for n2 in H2:
        if cost[n1,n2] > best and n2 not in matched:
            aligned[n1]=n2
            best = cost[n1,n2]
    matched.append(aligned[n1])

使用一个内核将需要很长时间（对于 5Kx5K，单线程需要 40 分钟）。我想我们不能并行化嵌套循环，因为我们需要最好的变量。正确的？我尝试将此代码并行化，但它给了我许多重复的列。

from joblib import Parallel, delayed
import multiprocessing

inputs = range(500000)
def processInput(i):
    row = cost[i, :]
    # cost[row, col[0][0]] = 10e5 ### not possible as read-only in multiprocessing
    return i,col


num_cores = multiprocessing.cpu_count()
row_col = Parallel(n_jobs=num_cores)(delayed(processInput)(i) for i in inputs)

有什么建议可以更快地运行贪心算法（我的并行解决方案不起作用）？

标签： pythonmultiprocessingmulticorehungarian-algorithm

解决方案

推荐阅读