python:涉及幂级数的问题的效率

Question

问题定义:

这是codewars的问题.

定义一个自反转电源序列，S，为:

S(0) = 0
S(1) = 1
S(2) = 1^2 + 2 = 3
S(3) = 1^3 + 2^2 + 3 = 8
...
S(n) = 1^n + 2^(n-1) + ... + (n-1)^2 + n

实现一个带有 2 个参数(num_dig 和 ord_max)的函数，并找到序列中小于 num dig 的最小数字，它也有 ord_max 个数字。

如果有一个数字的位数正确，结果应该是一个数组，格式如下:

[True, smallest found term] 

[False, -1]

这些是一些例子:

n-th Term    Term Value
1              0
2              1
3              3
4              8
5              22
6              65
7              209
8              732
9              2780
10             11377
11             49863
12             232768
13             1151914
14             6018785

因此示例测试包括:

min_length_num(5, 10) == [True, 10]   # 10th term has 5 digits
min_length_num(7, 11) == [False, -1]  # no terms before 13th has 7 digits
min_length_num(7, 14) == [True, 13]   # 13th term already has 7 digits

我的方法:

我创建了一个生成器，它生成幂级数 S 的所有值，直到值 n:

def seq(n):
    for i in range(n):
        s = range(i+1)
        j = i+1
        tot = 0
        while j > 0:
            for k in s:
                tot += k**j
                j -=1
            break
        yield tot

然后我检查生成器的值，并且:要么在遇到第一个具有所需位数的值时立即返回 True，否则返回 False:

def min_length_num(num_dig, ord_max): 
    i = 1
    for n in seq(ord_max):
        if len(str(n)) == num_dig:
            return [True, i]
        elif len(str(n)) > num_dig:
            break
        i +=1
    return [False, -1]

这通过了所有测试，但由于超时而未完成测试过程。输入范围假定 ord_max <= 1000。

我对生成器不是很精通，所以也许我在那里做错了什么，或者做得不合适。我会很感激一些帮助。谢谢。

编辑:另一个解决方案。

因为我知道 ord_max <= 1000，所以我可以预先计算所有值并修改代码如下:

p = [n for n in seq(1000)]

def min_length_num(num_dig, ord_max): 
    i = 1
    for k in p[:ord_max]:
        if len(str(k)) == num_dig:
            return [True, i]
        elif len(str(k)) > num_dig:
            break
        i +=1
    return [False, -1]

这更快并且解决了我的问题，但我发现它是一个非常丑陋的解决方案，更像是一个肮脏的 hack。我想要更好的东西。

Answer 1

不是完整的解决方案，而是一些优化提示:

您不需要一次又一次地计算自然数的所有幂 - 我怀疑取幂是相当长的操作。而是存储当前功率列表，并在每一步将 power[k] 乘以 k

 1  4  3       //3rd stage
 1  8  9  4    //4th stage

并用新旧功率之差更新和值

 S(4) = S(3) + (8-4) + (9-3) + 4 = 22

同时预先计算所需位数的目标值

  powten = 10**(num_dig-1)  //1 000 000 for num_dig=7

并在不转换为字符串的情况下将总和与 powten 进行比较