如何优化我的代码 ("How many ways can you make the sum of a number?")

Question

我有下一个代码（这是对“你可以用多少种方法求和？”这个问题的答案）：

import itertools


def exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    res = []
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                res.extend(set(sorted(itertools.permutations(tup, i))))
    res = [tuple(sorted(q)) for q in res]
    print(len(set(res)))


exp_sum(int(input()))

如何将这段代码加速几倍？

（如果输入是11，运行时间是~23s）

Answer 1

你做了很多不需要的排序。我给你性能更好的函数。

与输入 11 比较：

11.680076 # Your Function
0.10761999999999716 # a better Function keeping the tuples 
0.10596200000000522 # a function don't keep the tuples

import time
import itertools


t = time.process_time()

elapsed_time = time.process_time() - t

def more_better_exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    counter = 0
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                counter += 1
    print(counter)
        

def better_exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    res = []
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                res.append(tup)
    print(len(res))
        


        
def exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    res = []
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                res.extend(set(sorted(itertools.permutations(tup, i))))
    res = [tuple(sorted(q)) for q in res]
    print(len(set(res)))

x = int(input())


#YOur Version
t = time.process_time()
exp_sum(x)
print(time.process_time() - t)


# Number and tuples 
t = time.process_time()
better_exp_sum(x)
print(time.process_time() - t)

# Just the number 
t = time.process_time()
more_better_exp_sum(x)
print(time.process_time() - t)

Answer 2

您可以将问题视为从 n 中移除 i，对于每个 i 从 1 到 n，并递归解决剩下的问题，n - i，但删除不超过 i 或 n - i，以较小者为准，以避免重复，直到没有任何东西可以删除，在这种情况下，只有一种方法可以删除任何东西：

from functools import lru_cache

@lru_cache(None)
def exp_sum(n, m=float('inf')):
    if not n:
        return 1
    return sum(exp_sum(n - i, i) for i in range(1, min(n, m) + 1))

编辑：感谢@donttalkjustcode 的缓存版本，它在给定 n = 11 的情况下将代码加速了大约 3 倍。

下面的基准测试表明，这种方法比@Kartoffelkultur 的解决方案快 3,000 倍，给定 n = 11:

161263.009 μs  Kartoffelkultur
77.217 μs  blhsing
54.968 μs  blhsing2
52.836 μs  blhsing3

160772.200 μs  Kartoffelkultur
65.117 μs  blhsing
51.606 μs  blhsing2
50.769 μs  blhsing3

224365.012 μs  Kartoffelkultur
62.634 μs  blhsing
50.885 μs  blhsing2
49.874 μs  blhsing3

Run the benchmark online

如何优化我的代码 ("How many ways can you make the sum of a number?")

How to optimize my code ("How many ways can you make the sum of a number?")

python

sum

set

itertools