请问用什么方法能进一步提高运行速度

Question

请问我编写如下的两个程序怎样提高运行速度

def fibonacci(n):
    a, b = 1, 1
    for i in range(n):
        yield pow(a, 2)
        a, b = b, a + b


num = int(input())
result = list(fibonacci(num))
print(sum(result) % 1000000007)

while True:
    try:
        a = 0
        b = 0
        c = 0
        d = 0
        mod = 1e9 + 7
        str1 = input()
        for i in range(len(str1)):
            if str1[i] == '2':
                a += 1
            if str1[i] == '0':
                b = (b + a) % mod
            if str1[i] == '1':
                c = (c + b) % mod
            if str1[i] == '9':
                d = (d + c) % mod
        print(int(d))
    except EOFError:
        break

Answer 1

望采纳

优化fibonacci函数，由于每次调用pow函数都会带来较大的计算量，因此可以考虑使用快速幂算法来替代pow函数，以提高计算效率。

可以使用缓存来存储已计算过的斐波那契数列值，以避免重复计算:

def fibonacci(n):
    a, b = 1, 1
    cache = {}
    for i in range(n):
        if i in cache:
            a, b = b, cache[i]
        else:
            cache[i] = a**2
            a, b = b, a + b
        yield a**2

第2个程序可以使用缓存来存储已计算过的结果，以避免重复计算。

def count_chars(s):
    char_count = {'2': 0, '0': 0, '1': 0, '9': 0}
    for c in s:
        char_count[c] += 1
    return char_count

cache = {}

while True:
    try:
        s = input()
        if s in cache:
            print(cache[s])
            continue
        char_count = count_chars(s)
        a, b, c, d = char_count['2'], char_count['0'], char_count['1'], char_count['9']
        mod = 1e9 + 7
        c = (c + b) % mod
        d = (d + c) % mod
        cache[s] = d
        print(int(d))
    except EOFError:
        break