python - 如何让这段代码更有效地处理大输入？

Question

嘿。我知道这不是一个“重构我的代码”网站，但我制作了这段代码，它在中等大小的输入下工作得很好，但它在字符串大小(比如超过 2000)时会出现问题。

它的作用 - 它以一串数字作为参数，并返回可以将其解释为一串字母的方式的数量，其中英文字母表中的每个字母根据其词法分配一个数值位置:A -> 1, B-> 2, Z-> 26 等

由于某些字母表示为两个数字，因此后缀树不是唯一的，因此可以有多种解释。例如，“111”可以是“AAA”、“KA”和“AK”。

这是我的代码。它相当易读且简单明了，但存在问题，因为:

1. 它每次都必须复制部分字符串以将其作为递归部分的参数调用。
2. 它必须在缓存中存储大量字符串，因此在内存方面非常昂贵。
3. ...它是递归的。

帮助非常感谢:)

cache = dict()
def alpha_code(numbers):
    """
    Returns the number of ways a string of numbers
    can be interpreted as an alphabetic sequence.
    """
    global cache
    if numbers in cache: return cache[numbers]

    ## check the basic cases
    if numbers.startswith('0'): return 0
    if len(numbers) <= 1: return 1

    ## dynamic programming part

    ## obviously we can treat the first (non-zero)
    ## digit as a single letter and continue -
    ## '342...' -> C + '42...'
    total = alpha_code(numbers[1:])

    ## the first two digits make for a legal letter
    ## iff this condition holds
    ## '2511...' -> Y + '11...'
    ## '3711...' -> illegal
    if numbers[:2] <= '26':
        total += alpha_code(numbers[2:])

    cache[numbers] = total
    return total

Answer 1

尝试使用动态规划方法:

1. 创建一个数组(称之为“P”)，字符串中每个字符有 1 个元素。
2. 初始化 P[0] = 1(除非第一个字符为 0，在这种情况下只返回 0 作为结果)。
3. 如果前两个字符和当前字符一样可以被解释为字母，则初始化 P[1] = 2；否则如果当前字符非零则返回 1，否则返回结果 0)。

4. 通过以下规则(伪代码)从左到右填充数组的其余部分:

   P[x] = (如果当前字符为'0'，则 0，否则 P[x-1]) + (if 前一个字符 + 当前字符可以解释为一个字母 然后 P[x-2] 其他 0)

(请注意，如果 P[x] 永远为 0，您应该返回零，因为这意味着连续有两个 0，而您的规则似乎不允许。)

和的第一部分是处理当前字符被解释为字母的情况；求和的第二部分是处理最近的 2 个字符被解释为字母的情况。

本质上，P[x] 将等于整个字符串从开始到位置 x 可以解释为字母的方式的数量。由于您可以通过查看以前的结果来确定这一点，因此您只需要循环遍历字符串的内容一次 - O(N) 时间而不是 O(2^N)，这是一个巨大的改进.您的最终结果只是 P[len(input)-1] 因为“从开始到结束的所有内容”与“整个字符串”相同。

“111”的基本输入案例运行示例:

• P[0] = 1(因为 1 非零)
• P[1] = 2(因为11是一个有效字母，1也是一个有效字母)
• P[2] = 3(因为最近的两个字符加起来是一个有效字母，且当前字符不为零，所以P[0]+P[1] = 1+2 = 3)

因为 P[2] 是我们最后的结果，它是 3，所以我们的答案是 3。

如果字符串是“1111”，我们将继续下一步:

• P[3] = 5(由于最近两个字符是有效字母，且当前字符非零，所以P[1]+P[2] = 2+3 = 5)

答案确实是 5 - 有效的解释是 AAAA、KK、AKA、AAK、KAA。请注意这 5 个可能的答案是如何从“11”和“111”的潜在解释中构建出来的:

'11':AA 或 K '111': AAA 或 KA 或 AK

'111'+A:AAA+A 或 KA+A 或 AK+A '11'+K:AA+K 或 K+K