Python线程-内存不足

Question

我目前正在处理python中的一个问题，以确定在计划交付时要采用的最佳路线。对我的代码的高级理解是，我读取了所有建筑物（输入中“：”之前的值），然后计算了通往这些建筑物的所有可能性。然后，我针对所生成的每个组合将计算分为一个线程，并返回总时间以返回到“ home”大楼（在所有情况下均为“ abc”大楼）。

下面的代码在较小的数据子集（总共4座建筑物）上可以正常工作，但是当我将代码最多分配到13座建筑物（所需数量）时。执行期间我遇到了Memory Error。

我对如何解决这个问题有些犹豫，以前我从未遇到过以指数级速度爆炸的问题。任何建议/提示将不胜感激。

Input.txt（小的子集）：

abc : 0 5 7 3
def : 4 0 3 6
ghi : 6 4 0 4
jkl : 4 5 6 0

Input.txt（完整数据）：

abc : 0 5 7 3 2 4 6 2 1 5 8 4 5
def : 4 0 3 6 7 2 3 4 5 6 7 8 6
ghi : 6 4 0 4 9 9 9 9 9 9 9 9 7
jkl : 4 5 6 0 2 3 7 8 6 9 2 8 3
mno : 1 2 3 4 0 9 8 7 6 5 3 2 2
pqr : 9 8 3 4 1 0 9 8 3 5 7 9 2
stu : 1 8 9 4 2 1 0 9 8 7 2 1 1
vwx : 3 2 1 9 4 1 5 0 9 8 2 5 8
yza : 1 9 8 2 3 7 4 6 0 1 4 2 6
bcd : 8 9 1 4 6 2 4 2 1 0 9 3 4
efg : 7 7 7 7 8 9 1 2 3 9 0 4 3
hij : 6 1 2 4 9 0 2 1 3 9 1 0 8
klm : 1 6 3 8 3 5 9 4 7 2 1 5 0

当前代码：

import time
import os
import threading
import sys
from itertools import permutations
from functools import reduce


inputFile = 'Input.txt'
outputFile = 'output2.txt'

f=open(inputFile,'r')
line=f.readline()
buildings=[]
timings=[]
results={}

def run_me(TimeMatrix,combination,results,buildingDict):
    my_lock.acquire()
    results[' '.join(map(str, combination))] = GenerateTiming(TimeMatrix,combination,buildingDict)
    my_lock.release()

def GenerateTiming(TimeMatrix,combination,buildingDict):
    current=combination
    mySum=[]
    for i in range(len(current)-1):
        currentBuilding=buildingDict[current[i]]
        nextBuilding=buildingDict[current[i+1]]
        mySum.append(TimeMatrix[currentBuilding-1][nextBuilding])
    result=sum(mySum)
    return(result)


while line: 
    b=line.split(":")[0]
    t=line.split(":")[1]
    b=b.strip()
    t=t.strip()
    buildings.append(b)
    timings.append(t)
    home=buildings[0]
    line=f.readline()



combinations=[]
first, *rest = buildings
for p in permutations(rest):
    combinations.append([first,*p,first])

bldLKP=combinations[0]
buildingDict={}

for i in range(1,len(bldLKP)):
    buildingDict[bldLKP[i-1]] = i
    i=i+1


TimeMatrix=[[i] + [int(n) for n in s.split()] for i, s in enumerate(timings, 1)]

#Threading Section
my_lock=threading.Lock()
my_threads=list()


for comb in combinations:
    my_threads.append(threading.Thread(target=run_me,args=(TimeMatrix,comb,results,buildingDict)))

for current_thread in my_threads:
    current_thread.start()

for current_thread in my_threads:
    current_thread.join()


lowest=min(results.values())
final=[key for key in results if results[key]==lowest]

print(' '.join(map(str, final)),lowest)

编辑：我应该提一下，我相信问题出在以下代码中，我正在确定所有可能的建筑物组合。但是，我不确定如何以其他方式执行此操作，因为需要检查每条路径以获得最快的路线。

combinations=[]
first, *rest = buildings
for p in permutations(rest):
    combinations.append([first,*p,first])

Answer 1

在您的代码中，您创建排列，然后运行线程以计算每个路线的总和（时间）。您的代码运行的线程数量是

小子集（4座建筑物）

您为其余建筑物（不包括第一个建筑物）创建排列，因此数量将为（4-1）！ = 3 * 2 * 1 = 6

完整数据（13座建筑物）（13-1）！ = 479001600（应创建这种数量的线程。

我建议在这种情况下不要使用线程。

我编写了简单的递归函数来实现所需的功能。我对排列的性能有了很大的提高。如果当前时间大于最小时间，则不会更深。请看一下我的实现

time_matrix = {}
buildings = []

with open('input.txt', 'r') as f:
    lines = []
    for row in f.readlines():
        building, line = row.split(':')
        building = building.strip()
        buildings.append(building)
        lines.append(line.strip())
        time_matrix[building] = {}

for building, line in zip(buildings, lines):
    for index, time_to_reach in enumerate(line.split(' ')):
        to_building = buildings[index]
        time_matrix[building][to_building] = int(time_to_reach)

first, *rest = buildings
min_time = None
min_path = None

def calculate(current_building, to_visit_buildings, current_path, current_time):
    global min_path, min_time

    if min_path and min_time < current_time:
        return

    if not to_visit_buildings:
        current_time += time_matrix[current_building][first]
        if min_time is None or min_time > current_time:
            min_time = current_time
            min_path = [first, *current_path, first]
            return

    for building in to_visit_buildings:
        new_to_visit_buildings = [b for b in to_visit_buildings if b != building]
        new_current_path = [*current_path, building]
        new_current_time = current_time + time_matrix[current_building][building]
        calculate(building, new_to_visit_buildings, new_current_path, new_current_time)

calculate(first, rest, [], 0)

print(min_path, min_time)

对于完整数据，它输出：[“ abc”，“ yza”，“ bcd”，“ ghi”，“ jkl”，“ efg”，“ stu”，“ hij”，“ vwx”，“ def”，“ pqr”，“ mno”，“ klm'，'abc'] 20