Diferentes resultados de rendimiento vs retorno

Question

Realmente no entiendo cómo funciona la declaración yield en esta situación. El problema dice que, dada una expresión sin paréntesis, escriba una función para generar todas las posibles expresiones entre paréntesis (FP). Say, la entrada es '1+2+3+4' que debe ser generado a 5 FP expresiones:

1. (1+ (2+ (3 + 4)))
2. (1 + ((2 + 3) +4))
3. ((1 + 2) + (3 + 4))
4. ((1+ (2 + 3)) + 4)
5. (((1 + 2) +3) +4)

Mi código es el siguiente.

OPS = ('+', '-', '*', '/') 
def f(expr): 
    """ 
    Generates FP exprs 
    Recursive formula: f(expr1[op]expr2) = (f(expr1) [op] f(expr2)) 
    """ 
    if expr.isdigit(): yield expr 
#  return [expr] 

# ret = [] 
    first = '' 
    i = 0 
    while i < len(expr): 
     if expr[i] not in OPS: 
      first += expr[i] 
      i += 1 
     else: 
      op = expr[i] 
      i += 1 
      second = expr[i:] 
      firstG, secondG = f(first), f(second) 
      for e in ('(' + e1 + op + e2 + ')' for e1 in firstG for e2 in secondG): 
       yield e 
#    ret.append(e) 
      first += op 
# return ret 

Si uso return declaración (las líneas comentadas), a continuación, el código funciona como se esperaba. Sin embargo, cuando cambio a la declaración yield como muestra el código, solo obtengo los primeros 4 resultados. Si aumenta el número de operandos de la expresión de entrada, entonces, por supuesto, se perderán más resultados. Por ejemplo, para la entrada '1+2+3+4+5', solo me dan 8 en lugar de 14.

finalmente averiguar la manera de hacer que el código comentando la línea de firstG, secondG = f(first), f(second) y reemplazar la línea

for e in ('(' + e1 + op + e2 + ')' for e1 in firstG for e2 in secondG):

por

for e in ('(' + e1 + op + e2 + ')' for e1 in f(first) for e2 in f(second)):

Eso significa que algunos 'información' del generador se pierde debido a la línea firstG, secondG = f(first), f(second) pero No puedo entender la verdadera razón. ¿Podrían darme algunas ideas?

Answer 1

El problema es que está iterando sobre generadores en lugar de listas en la versión de rendimiento, específicamente secondG que se agota después de un bucle. Cambie la línea a esto y funciona:

firstG, secondG = f(first), list(f(second)) 

O bien, puede cambiar su bucle:

for e in ("(%s%s%s)" % (e1, op, e2) for e1 in f(first) for e2 in f(second)): 
#        new generator object every loop ^^^^^^^^^ 

La versión no-rendimiento funciona porque regrese listas, que pueden repetirse otra vez, a diferencia de generadores. También tenga en cuenta que solo iterará más de firstG una vez, por lo que no se verá afectado.

recordar que esto:

r = [v for a in A for b in B] 

es equivalente a:

r = [] 
for a in A: 
    for b in B: 
    r.append(v) 

Lo que demuestra más claramente el bucle se repite una B.

Otro ejemplo:

def y(): 
    yield 1 
    yield 2 
    yield 3 
def r(): 
    return [1, 2, 3] 

vy = y() 
for v in vy: 
    print v 
for v in vy: 
    print v 

print "---" 

vr = r() 
for v in vr: 
    print v 
for v in vr: 
    print v