Python代码段需要很长时间才能运行。如何提高效率？

Question

任务是从列表（li）中选择元素，以使总和尽可能接近给定的数字（m）!。但是，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)

Answer 1

我的2美分...

• 代码段是否适用于较小的数组大小？如果对于较小的列表不起作用，则可能是算法错误。

• 这可能是多线程的不错选择。您没有修改输入列表，因此不会有任何竞争条件。像对第一个for循环一样对列表进行切片，然后让每个线程处理排列。

• 您对列表进行排序，然后在每次计算排列时都寻找重复的值。更糟糕的是，您甚至没有保存排序列表。我将创建一个专用的数据结构来存储中间结果，以便您减少所需的排序和散列量。