Фрагмент кода Python занимает очень много времени .. как повысить эффективность? - PullRequest
Новая
       83

Фрагмент кода Python занимает очень много времени .. как повысить эффективность?

0 голосов
/ 16 февраля 2020

Задача состоит в том, чтобы выбрать элементы из списка (li), чтобы сумма была как можно ближе к заданному числу (м) !. Но метод idk занимает очень много времени для запуска: он никогда не завершается. Когда я компилирую код, метод просто продолжает работать и работать. 

from itertools import combinations, permutations

def idk(typeOfSlices, maxNoOfPizzaSlices):
    length = len(typeOfSlices) + 1
    listToReturn = []
    temporarySum = 0

    for r in range(length):

        pool = tuple(typeOfSlices)
        n = len(pool)
        for indices in permutations(range(n), r):
            if sorted(indices) == list(indices):
                le = tuple(pool[i] for i in indices)
                ts = sum(le)
                if(ts == maxNoOfPizzaSlices):
                    print(le, ":", sum(le))
                    return le

                if(ts > temporarySum and ts <= maxNoOfPizzaSlices):
                    temporarySum = ts
                    listToreturn = le

    print(le, ":", sum(le))
    return listToReturn

m = 4500
li = [7, 12, 12, 13, 14, 28, 29, 29, 30, 32, 32, 34, 41, 45, 46, 56, 61, 61, 62, 63, 65, 68, 76, 77, 77, 92, 93, 94, 97, 103, 113, 114, 114, 120, 135, 145, 145, 149, 156, 157, 160, 169, 172, 179, 184, 185, 189, 194, 195, 195,
]
idk(li, m)

1 Ответ

1 голос
/ 16 февраля 2020

Мои 2 цента ...

  • Работает ли фрагмент кода для меньшего размера массива? Если это не работает для меньшего списка, то у вас может быть плохой алгоритм.

  • Это может хорошо подойти для многопоточности. Вы не изменяете список ввода, поэтому не будет никаких условий гонки. Разделите список вверх, как вы делаете с первым for-l oop, затем каждый поток обрабатывает перестановки.

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

...