python - 减少运行时间的 Python 方法 KTNS 算法
问题描述
我一直在尝试开发一种算法,称为尽快保持所需工具,但在模拟过程中,我意识到运行需要太多时间。
我想减少运行时间并检查有关如何快速 Python 编码的其他问题 Python是否比 Java/C# 慢?[关闭]我找到了几种解决方案,但我不知道如何在我的代码中实现它们。
在我的电脑上它需要 0.004999876022338867 秒,但主要问题是对于整个程序,这个函数被调用了 13,000 次。
在这里我附上我的整个代码,如果您有任何改进它的建议,请随时与我分享。
import sets
import numpy
import copy
import time
J= {1: [6, 7],2: [2, 3], 3: [1, 6, 9], 4: [1, 5, 9], 5: [5, 8, 10], 6: [1, 3, 6, 8], 7: [5, 6, 8, 9], 8: [5, 7, 8], 9: [1, 4, 5, 8], 10: [1, 2, 4, 10]}
def KTNS(sigma=[10, 9, 4, 1, 6, 3, 7, 5, 2, 8], Jobs=J, m=10 ,capacity=4 ):
t0=time.time()
Tools = {}
Lin={}
n=len(sigma)
for i in range(1,m+1):
for e in sigma:
if i in Jobs[e]:
Tools[i]=sets.Set([])
count = 1
available_tools=sets.Set()
for e in sigma:
for i in Jobs[e]:
Tools[i].add(count)
available_tools.add(i)
count+=1
Tin=copy.deepcopy(Tools)
for e in Tin:
Lin[e]=min(Tin[e])
count=1
J = numpy.array([0] *m)
W = numpy.array([[0] * m] * n)
while count<=len(sigma):
for e in Tools:
if len(available_tools)<capacity:
reference=len(available_tools)
else:
reference=capacity
while numpy.count_nonzero(J == 1) <reference:
min_value = min(Lin.itervalues())
min_keys = [k for k in Lin if Lin[k] == min_value]
temp = min_keys[0] #min(Lin, key=Lin.get)
if min_value>count:
if len(min_keys)>=2:
if count==1:
J[temp - 1] = 1
Lin[temp] = '-'
else:
J0=W[count-2]
k=0
for elements in min_keys: #tested
if numpy.count_nonzero(J == 1) < reference:
if J0[elements-1]==1:
J[elements-1]=1
Lin[elements]='-'
k=1
else:
pass
else:
pass
if k==0:
J[temp - 1] = 1
Lin[temp] = '-'
else:
J[temp - 1] = 1
Lin[temp] = '-'
else:
J[temp-1]=1
Lin[temp] = '-'
Tin[e].discard(count)
for element in Tin:
try:
Lin[element] = min(Tin[element])
except ValueError:
Tin[element]=sets.Set([len(sigma)+1])
Lin[element]=len(sigma)+1
W[count-1]=J
J= numpy.array([0] *m)
count+=1
Cost=0
for e in range(1,len(sigma)):
temp=W[e]-W[e-1]
temp[temp < 0] = 0
Cost+=sum(temp)
return Cost+capacity,time.time()-t0
解决方案
一项建议 - 尽量减少对字典的使用。看起来您的许多字典都可以是列表。字典访问比 python 中的列表访问慢得多。
看起来您可以简单地将 Tools、Lin 和 Tin 全部设为列表,例如,Lin = []
而不是Lin = {}
,我希望您会看到性能的显着提升。
您知道 3 个字典的大小,因此只需将它们初始化为您需要的大小。创建 Lin 和工具如下:
Lin = [None] * m+1
Tools = [None] * m+1
Tin = [None] * m+1
这将创建一个 m+1 个元素的列表(这是您从 1 到 m+1 的循环所得到的)。由于您正在执行基于 1 的索引,因此它会在 Lin[0]、Tools[0] 等中留下一个空白位置,但您将能够访问 Lin[1] - Lin[10],就像您一样目前正在做。您可以自己尝试的简单示例:
python3 -m timeit -s 'foo = [x for x in range(10000)]' 'foo[500]'
100000000 个循环,3 个中最好的:每个循环 0.0164 微秒
python3 -m timeit -s 'foo = {x: x for x in range(10000)}' 'foo[500]'
10000000 个循环,3 个中最好的:每个循环 0.0254 微秒
只需将您的字典更改为列表,您就会获得几乎 2 倍的改进。您的 65 秒任务现在大约需要 35 秒。
顺便说一句,查看 python wiki 以获取有关提高速度的提示,包括许多关于如何分析函数的参考。
推荐阅读
- javascript - 为什么@chakra-ui/gatsby-plugin 会使 gatsby 崩溃?
- javascript - 更改滑块项目数(Owl Carousel v2)
- javascript - Fetch 不会返回任何结果
- javascript - 我可以在 PHP 中添加条件以仅在大屏幕上显示 JS 吗?
- kotlin - Kotlin for android - 第一个按钮有效,第二个无效?
- node.js - 如何将 Uint8Array 转换为 CanvasImageSource?
- java - 自定义链表中的垃圾回收
- python-3.x - 在python中右对齐循环文本
- c# - 如何使用 Xamarin Forms 在 C# 中以编程方式为 Picker 设置 ItemDisplayBinding?
- react-native - 在 React Native 中,如何将键盘位置置于所有其他元素之上?