每次在for循环中调用函数时，它似乎运行得更快
我写了一个非常粗糙的爬坡/贪婪算法来解决旅行商问题。目的是以此为基准，并持续改善运行时间并同时优化解决方案。
如果我在for一个循环中对同一数据运行10次爬山算法（每个爬山都进行10,000次迭代），我会注意到解决方案的运行时间几乎总会下降，最终解决方案会花费约50％第一个解决方案所需的时间。每个解决方案上唯一要计算的是爬坡本身。所有解决方案之前，支持数据（例如距离/时间矩阵和作业列表）都存储在内存中。
因此，前三个功能仅适用于MCVE，可以忽略。
打印的输出是运行时，后跟一个列表，例如搜索解决方案时选择[(iteration_number,
greedy_route_cost)]新变量的迭代编号best_route。运行时间似乎与每次爬山都存储多少条临时路线无关。每个解决方案应独立。有人能在calc_route_cost或中看到这种加速的原因hill_climb吗？我在这里想念的是什么？如何分析这种加速的原因？这是在Python
2.7.9中。
import mathimport random
import datetime
# To generate a random customer name for each fake order
LETTERS = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q',
'r','s','t','u','v','w','x','y','z']
def crow_flies(lat1, lon1, lat2, lon2):
''' For MCVE. Straight-line distance between two locations. Should not affect
run time.
'''
dx1,dy1 = (lat1/180)*3.141593,(lon1/180)*3.141593
dx2,dy2 = (lat2/180)*3.141593,(lon2/180)*3.141593
dlat,dlon = abs(dx2-dx1),abs(dy2-dy1)
a = (math.sin(dlat/2))**2 + (math.cos(dx1) * math.cos(dx2)
* (math.sin(dlon/2))**2)
c = 2*(math.atan2(math.sqrt(a),math.sqrt(1-a)))
km = 6373 * c
return km
def gen_matrix(order_list):
''' For MCVE. Returns dictionary of distance and time between all
location pairs. Should not affect run time.
Returns {(location_id_from, location_id_to): [distance, time]}
'''
matrix = {}
for loc in order_list:
for pair_loc in order_list:
if loc[0] != pair_loc[0]:
distance = crow_flies(loc[1], loc[2], pair_loc[1], pair_loc[2])
matrix[(loc[0], pair_loc[0])] = [distance, distance*random.random()]
return matrix
def gen_jobs(num_jobs, start_time, end_time, lat_low, lat_high, lon_low, lon_high):
''' For MVCE. Creates random jobs with random time windows and locations
'''
job_list = []
for x in range(num_jobs):
lat = random.uniform(lat_low, lat_high)
lon = random.uniform(lon_low, lon_high)
start = random.randrange(start_time, end_time-120, 1)
end = start + 120
faux_start = random.randrange(start, end-60, 1)
faux_end = faux_start + 60
capacity_demand = random.choice([-1, 1])
name_1 = random.choice(LETTERS)
name_2 = random.choice(LETTERS)
name_3 = random.choice(LETTERS)
name_4 = random.choice(LETTERS)
name_5 = random.choice(LETTERS)
NAME = name_1 + name_2 + name_3 + name_4 + name_5
job_list.append([NAME, lat, lon, start, end, faux_start, faux_end,
capacity_demand])
return job_list
def calc_route_cost(start_time, route, matrix):
''' Returns the cost of each randomly generated route '''
cost = 0
# Mileage cost
dist_cost = sum([matrix[(route[x][0], route[x+1][0])][0] for x in
range(len(route)-1)]) * 0.14
cost += dist_cost
# Man-hour cost
time_cost = sum([matrix[(route[x][0], route[x+1][0])][1] for x in
range(len(route)-1)]) * 0.35
cost += time_cost
for x in range(0, len(route)-1):
travel_time = matrix[(route[x][0], route[x+1][0])][1]
arrival = start_time + travel_time
start_time += travel_time
departure = arrival + 10
if arrival < route[x+1][3]:
# Penalise early arrival
arr_cost = (route[x+1][3] - arrival)**2
cost += arr_cost
elif departure > route[x+1][4]:
# Penalise late departure
dep_cost = (departure - route[x+1][4])**2
cost += dep_cost
if arrival < route[x+1][5]:
# Penalise 'soft' early arrival i.e. earlier than a fake prediction
# of arrival
faux_arr_cost = (route[x+1][5] - arrival)**1.2
cost += faux_arr_cost
elif departure > route[x+1][6]:
# Penalise 'soft' late departure
faux_dep_cost = (departure - route[x+1][6])**1.2
cost += faux_dep_cost
return cost
def hill_climb(jobs, matrix, iterations):
''' Randomly generate routes and store route if cheaper than predecessor '''
cost_tracking, iteration_track = [], []
initial_cost = calc_route_cost(480, jobs, matrix)
best_cost = initial_cost
best_route = jobs[:]
changed_route = jobs[:]
for x in range(iterations):
random.shuffle(changed_route)
new_cost = calc_route_cost(480, changed_route, matrix)
if new_cost < best_cost:
best_route = changed_route[:]
best_cost = new_cost
cost_tracking.append(best_cost)
iteration_track.append(x)
return cost_tracking, iteration_track
if __name__ == '__main__':
#random_jobs = gen_jobs(20, 480, 1080, 24, 25, 54, 55)
random_jobs = [['lmizn', 24.63441343319078, 54.766698677134784, 501, 621, 558, 618, 1],
['jwrmk', 24.45711393348282, 54.255786174435165, 782, 902, 782, 842, 1],
['gbzqc', 24.967074991405035, 54.07326911656665, 682, 802, 687, 747, 1],
['odriz', 24.54161147027789, 54.13774173532877, 562, 682, 607, 667, -1],
['majfj', 24.213785557876257, 54.452603867220475, 681, 801, 731, 791, -1],
['scybg', 24.936517492880274, 54.83786889438055, 645, 765, 662, 722, -1],
['betow', 24.78072704532661, 54.99907581479066, 835, 955, 865, 925, -1],
['jkhmp', 24.88461478479374, 54.42327833917202, 546, 666, 557, 617, -1],
['wbpnq', 24.328080543462, 54.85565694610073, 933, 1053, 961, 1021, -1],
['ezguc', 24.292203133848382, 54.65239508177714, 567, 687, 583, 643, -1],
['nlbgh', 24.111932340385735, 54.895627940055995, 675, 795, 711, 771, -1],
['rtmbc', 24.64381176454049, 54.739636798961044, 870, 990, 910, 970, 1],
['znkah', 24.235361720889216, 54.699010081109854, 627, 747, 645, 705, -1],
['yysai', 24.48931405352803, 54.37480185313546, 870, 990, 882, 942, -1],
['mkmbk', 24.5628992946158, 54.219159859450926, 833, 953, 876, 936, -1],
['wqygy', 24.035376675509728, 54.92994438408514, 693, 813, 704, 764, -1],
['gzwwa', 24.476121543580852, 54.13822533413381, 854, 974, 879, 939, 1],
['xuyov', 24.288078529689894, 54.81812092976614, 933, 1053, 935, 995, 1],
['tulss', 24.841925420359246, 54.08156783033599, 670, 790, 684, 744, -1],
['ptdng', 24.113767467325335, 54.9417036320267, 909, 1029, 941, 1001, 1]]
matrix = gen_matrix(random_jobs)
# Below is the loop that appears to accelerate
for p in range(10):
start = datetime.datetime.now()
sim_ann = hill_climb(random_jobs, matrix, 10000)
end = datetime.datetime.now()
# Number of iterations against greedy cost
iteration_count = zip(sim_ann[1], sim_ann[0])
print 'RUNTIME:', str(end - start)
print 'SOLUTION CONVERGENCE:', str(iteration_count)
回答：
此问题与OS /硬件向CPU分配资源有关，与CPU分支预测无关。在Windows 7上，同时运行另一个脚本可以做到：
for x in range(10): a = sum(xrange(10**8))
将大大加速该问题脚本的执行；for p in
range(10):与PC处于空闲状态相比，每次迭代只需花费25％的时间即可运行。在每个循环中，运行时也将保持一致。
，可以通过按照此链接中的
“设置电源配置文件”完全解决此问题。本质上，将“电源配置文件”更改为“高性能”。
我不清楚为什么要sum(xrange(10**8))大幅度加速资源释放，而100,000个迭代爬坡（超过10个迭代）却没有达到成熟度，即使运行时类似并且爬坡更为复杂。滴水速度非常慢。
除了在Windows 7 中设置为“ 高性能”
之外，似乎不可能对算法进行基准测试，除非您停止Windows限制CPU的运行，否则在无限循环中运行此处的hill-
climb脚本将在整个迭代中显示相同的特征。每次调用脚本时，CPU资源似乎都会重置。
以上是 每次在for循环中调用函数时，它似乎运行得更快 的全部内容， 来源链接： utcz.com/qa/413591.html
