代码之家 › 专栏 › 技术社区 › ooboo

如何使此代码更有效地处理大的输入?

recursion python

ooboo · 技术社区 · 17 年前

嘿。我知道这不是一个“重构我的代码”站点,但是我制作了这段代码,它在中等大小的输入下非常好地工作,但是它在字符串大小上有问题,比如说,超过2000。

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

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

这是我的密码。它可读性和直观性都很好,但有问题,因为:

它每次都必须复制字符串的一部分,以将其作为参数调用到递归部分。
它必须在高速缓存中存储大量的字符串,所以它非常昂贵,内存方面。
…它是递归的。

非常感谢您的帮助:)

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

4 回复 | 直到 17 年前

Amber 17 年前

尝试使用动态编程方法:

创建一个数组(称为“p”),字符串中每个字符一个元素。
初始化p[0]=1(除非第一个字符为0,在这种情况下,只返回0作为结果)。
如果前两个字符可以像当前字符那样解释为字母,则初始化p[1]=2;否则,如果当前字符为非零,则初始化p[1]=1,否则,结果返回0)。
通过以下规则(伪代码)从左到右填充数组的其余部分:

P[X] ( 如果当前字符为“0” 然后 0, 其他的 P[X-1) + ( 如果前一个字符+当前字符可以解释为字母然后 P[X-2] 其他的 0)

(注意,如果p[x]为0,则返回0,因为这意味着一行中有两个0,而您的规则似乎不允许这样做。)

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

实际上,p[x]等于字符串整体 从启动到位置X 可以解释为字母。由于您可以通过查看以前的结果来确定这一点,因此只需要循环一次字符串的内容—O(n)时间而不是O(2) ⁿ )这是一个巨大的进步。您的最终结果只是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

Alex Martelli 17 年前

递归消除总是一项有趣的任务。在这里,我将重点确保正确填充缓存,然后使用它,如下所示…

import collections

def alpha_code(numbers):
    # populate cache with all needed pieces
    cache = dict()
    pending_work = collections.deque([numbers])
    while pending_work:
      work = pending_work.popleft()
      # if cache[work] is known or easy, just go for it
      if work in cache:
        continue
      if work[:1] == '0':
        cache[work] = 0
        continue
      elif len(work) <= 1:
        cache[work] = 1
        continue
      # are there missing pieces? If so queue up the pieces
      # on the left (shorter first), the current work piece
      # on the right, and keep churning
      n1 = work[1:]
      t1 = cache.get(n1)
      if t1 is None:
        pending_work.appendleft(n1)
      if work[:2] <= '26':
        n2 = work[2:]
        t2 = cache.get(n2)
        if t2 is None:
          pending_work.appendleft(n2)
      else:
        t2 = 0
      if t1 is None or t2 is None:
        pending_work.append(work)
        continue
      # we have all pieces needed to add this one
      total = t1 + t2
      cache[work] = total

    # cache fully populated, so we know the answer
    return cache[numbers]

jmucchiello 17 年前

可以编写一个非递归的算法,但我认为它不会更快。我不是Python专家,所以我只给你一个算法:

Convert the array on numbers to an array of letters using just A thru I and leaving the zeros in place. 
Create two nested loops where you search and replace all the known pairs that represent larger letters. (AA -> K)

这个算法的好处是,您可以通过首先搜索和索引数组中的所有as和bs来优化搜索/替换。

因为您使用的是Python,不管您做什么,您都应该将字符串转换成一个数字列表。数字0-9是Python中的静态对象,这意味着它们可以自由分配。您还可以创建一个到z的可重用字符对象。列表的另一个好处是删除两个元素并插入单个元素的替换操作比反复复制字符串快得多。

Eric O. Lebigot 17 年前

通过不复制字符串,而是传递要研究的第一个字符的原始字符串和索引,可以大大减少内存占用:

def alpha_code(numbers, start_from = 0)
    ....

然后递归调用为:

alpha_code(numbers, start_from + 1)  # or start_from + 2, etc.

这样,您就保留了递归算法的简单性,并节省了大量内存。