Python методы для сокращения времени работы алгоритма KTNS

Question

Я пытался разработать алгоритм, который называл инструмент нужным как можно скорее, но во время моделирования я понял, что для его запуска требуется слишком много времени.

Я хочу уменьшить время выполнения и проверить другие предыдущие вопросы о том, как ускорить кодирование на 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

Answer 1

Одна рекомендация - постарайтесь свести к минимуму использование словарей. Похоже, что многие из ваших словарей могут быть списками. Доступ к словарю намного медленнее, чем доступ к списку в python.

Похоже, что вы можете просто сделать Tools, Lin и Tin списками, например. Lin = [] вместо Lin = {}, и я ожидаю, что вы увидите резкое улучшение производительности.

Вы знаете размеры своих 3 словарей, поэтому просто инициализируйте их в нужном вам размере. Создайте Лин и Инструменты следующим образом:

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 мксек на цикл

Просто изменив словари в список, вы получите почти двукратное улучшение. Ваша 65-секундная задача теперь будет занимать около 35 секунд.

Кстати, ознакомьтесь с Python wiki для советов по улучшению скорости , включая множество ссылок на то, как профилировать вашу функцию.