Como fazer este método não-recursivo?

votos
2

Ei. Este exemplo é bastante específica, mas eu acho que poderia ser aplicada a uma ampla gama de funções. É tirada de algum concurso de programação online.

Não é um jogo com uma condição de vitória simples. Empate não é possível. O jogo não pode durar para sempre, porque cada movimento leva você mais perto da condição de terminação. A função deve, dado um estado, determinar se o jogador que está a mover agora tem uma estratégia vencedora. No exemplo, o estado é um número inteiro. Um jogador escolhe um diferente de zero dígitos e subtrai-lo a partir do número: o novo estado é o novo inteiro. O vencedor é o jogador que chega a zero.

I codificado esta:

from Memoize import Memoize

@Memoize
def Game(x):
    if x == 0: return True
    for digit in str(x):
        if digit != '0' and not Game(x-int(digit)):
            return True
    return False

Eu acho que está claro como ele funciona. Eu também percebo que para este jogo específico que provavelmente há uma solução muito mais inteligente, mas a minha pergunta é geral. No entanto, isto faz python ficar louco mesmo para relativamente pequenas entradas. Existe alguma maneira de fazer este trabalho de código com um loop?

obrigado

Isto é o que eu quero dizer, traduzindo em um loop:

def fac(x):
    if x <= 1: return x
    else: return x*fac(x-1)

def fac_loop(x):
    result = 1
    for i in xrange(1,x+1):
        result *= i
    return result

## dont try: fac(10000)
print fac_loop(10000) % 100 ## works
Publicado 27/08/2009 em 07:33
fonte usuário
Em outras línguas...                            


4 respostas

votos
4

Em geral, só é possível converter funções recursivas em loops quando eles são primitivo-recursiva ; Isto significa basicamente que eles se chamam apenas uma vez no corpo. Sua função chama a si mesmo várias vezes. Tal função realmente precisa de uma pilha. É possível fazer a pilha explícita, por exemplo, com listas. Uma reformulação de seu algoritmo usando uma pilha explícita é

def Game(x):
    # x, str(x), position
    stack = [(x,str(x),0)]
    # return value
    res = None

    while stack:
        if res is not None:
            # we have a return value
            if not res:
                stack.pop()
                res = True
                continue
            # res is True, continue to search
            res = None
        x, s, pos = stack.pop()
        if x == 0:
            res = True
            continue
        if pos == len(s):
            # end of loop, return False
            res = False
            continue
        stack.append((x,s,pos+1))
        digit = s[pos]
        if digit == '0':
            continue
        x -= int(digit)
        # recurse, starting with position 0
        stack.append((x,str(x),0))

    return res

Basicamente, você precisa fazer com que cada variável local um elemento de um quadro de pilha; as variáveis ​​locais aqui são x, str (x), e o contador de iteração do loop. Fazendo valores de retorno é um pouco complicado - eu escolhi para definir res não-None se uma função acaba de retornar.

Respondeu 27/08/2009 em 08:45
fonte usuário

votos
3

Por "enlouquecer" Eu suponho que você quer dizer:

>>> Game(10000)
# stuff skipped
RuntimeError: maximum recursion depth exceeded in cmp

Você poderia começar na parte inferior em vez - uma mudança bruto seria:

# after defining Game()
for i in range(10000):
    Game(i)

# Now this will work:
print Game(10000)

Isso porque, se você começar com um número alto, você tem que recurse um longo caminho antes de chegar ao fundo (0), para que o seu decorador memoization não ajudar da maneira que deveria.

Ao iniciar a partir do fundo, você garante que cada chamada recursiva atinge o dicionário de resultados imediatamente. Você provavelmente usar o espaço extra, mas você não recurse agora.

Você pode transformar qualquer função recursiva em uma função iterativa usando um laço e uma pilha - essencialmente executando a pilha de chamadas com a mão. Veja esta pergunta ou esta quesstion , por exemplo, para alguma discussão. Pode haver uma solução baseada em loop mais elegante aqui, mas não pular para fora para mim.

Respondeu 27/08/2009 em 07:53
fonte usuário

votos
0

Você pode modificar a sua versão recursiva um pouco:

def Game(x):
    if x == 0: return True
    s = set(digit for digit in str(x) if digit != '0')
    return any(not Game(x-int(digit)) for digit in s)

Desta forma, você não examinar dígitos várias vezes. Por exemplo, se você está fazendo 111, você não tem que olhar para 110 três vezes.

Eu não tenho certeza se isso conta como uma versão interativa do algoritmo original que você apresentou, mas aqui é uma versão iterativa memoized:

import Queue
def Game2(x):
    memo = {}
    memo[0] = True
    calc_dep = {}
    must_calc = Queue.Queue()
    must_calc.put(x)
    while not must_calc.empty():
        n = must_calc.get()
        if n and n not in calc_dep:
            s = set(int(c) for c in str(n) if c != '0')
            elems = [n - digit for digit in s]
            calc_dep[n] = elems
            for new_elem in elems:
                if new_elem not in calc_dep:
                    must_calc.put(new_elem)
    for k in sorted(calc_dep.keys()):
        v = calc_dep[k]
        #print k, v
        memo[k] = any(not memo[i] for i in v)
    return memo[x]

Ele primeiro calcula o conjunto de números que X, a entrada, depende. Em seguida, ele calcula os números, começando na parte inferior e indo em direção x.

O código é tão rápido por causa do teste para calc_dep. Evita calcular várias dependências. Como resultado, ele pode fazer Game (10000) em menos de 400 milissegundos enquanto o original leva - Eu não sei quanto tempo. Muito tempo.

Aqui estão as medições de desempenho:

Elapsed:  1000   0:00:00.029000
Elapsed:  2000   0:00:00.044000
Elapsed:  4000   0:00:00.086000
Elapsed:  8000   0:00:00.197000
Elapsed:  16000   0:00:00.461000
Elapsed:  32000   0:00:00.969000
Elapsed:  64000   0:00:01.774000
Elapsed:  128000   0:00:03.708000
Elapsed:  256000   0:00:07.951000
Elapsed:  512000   0:00:19.148000
Elapsed:  1024000   0:00:34.960000
Elapsed:  2048000   0:01:17.960000
Elapsed:  4096000   0:02:55.013000

É razoavelmente zippy.

Respondeu 27/08/2009 em 21:06
fonte usuário

votos
0

Bem, recursão principalmente é sobre ser capaz de executar algum código sem perder contextos anteriores e sua ordem. Em particular, os quadros da função colocado e guardado na pilha de chamadas durante a recursividade, portanto, dando restrição na profundidade de recursão porque tamanho da pilha é limitado. Você pode a sua profundidade de recursão 'aumento', gerindo / guardar informações necessárias sobre cada chamada recursiva através da criação de uma pilha de estado na memória heap manualmente. Normalmente, a quantidade de memória heap disponível é maior do que a própria pilha. Pense: boas implementações ordenação rápida eliminar recorrência para o lado maior através da criação de um circuito externo com constante mudança variáveis ​​de estado (limites da matriz inferior / superior e pivô em QS exemplo).

Enquanto eu estava escrevendo isso, Martin v. Löwis postou boa resposta sobre a conversão de funções recursivas em loops.

Respondeu 27/08/2009 em 08:58
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more