时间戳

首页 > 解决方案 > 查找列表中小于某个数字的最大组合的低效代码

python - 查找列表中小于某个数字的最大组合的低效代码

问题描述

我正在尝试 Codewars 问题，但出现超时错误，这表明我的代码执行时间过长且效率低下。老实说，我不知道如何调整我当前的代码以使其更快，但希望得到一些帮助。代码的目的是k在列表中找到元素组合，该组合ls导致下面的总和最高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)

标签： python

解决方案

性能更高的版本：

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

推荐阅读