python - 在列表中查找小于特定数字的最大组合时代码效率低下

Question

我正在尝试提出 Codewars 问题，但出现超时错误，这表明我的代码执行时间太长且效率低下。老实说，我不知道如何调整当前的代码以使其更快，但需要一些帮助。该代码的目的是在列表 ls 中找到 k 元素的组合，从而得出低于 t 的最高总和。我的代码如下:

def choose_best_sum(t, k, ls):
    from itertools import product
    lists = [(s, sum(s)) for s in product(ls, repeat=k)]
    highest_sum = 0
    res = None
    for i in range(len(lists)):
        if lists[i][1]<t and lists[i][1]>highest_sum:
            highest_sum = lists[i][1]
            res = lists[i][0]
    return res

例如，choose_best_sum(174, 3, [50, 55, 57, 58, 60]) 应返回 (55,58,60)

Answer 1

性能更高的版本:

import timeit

def find_best_sum(threshold, k, ls):
    from itertools import combinations
    highest_sum = 0
    res = None
    for t in combinations(ls, r=k):
        s = sum(t)
        if s < threshold and s > highest_sum:
            highest_sum = s
            res = t
    return res


print(find_best_sum(174, 3, [50, 55, 57, 58, 60]))   # (55, 58, 60)

<小时/>

比较:

print('choose_best_sum', timeit.timeit('choose_best_sum(174, 3, [50, 55, 57, 58, 60])',
                    setup='from __main__ import choose_best_sum', number=1000))

print('find_best_sum', timeit.timeit('find_best_sum(174, 3, [50, 55, 57, 58, 60])',
                    setup='from __main__ import find_best_sum', number=1000))

输出(连续):

choose_best_sum 0.053198210999999995
find_best_sum 0.004936765999999981