'rendimiento' dentro de un procedimiento recursivo

8

Digamos que tengo una lista de Python que representa rangos para algunas variables:

conditions = [['i', (1, 5)], ['j', (1, 2)]]

Esto representa que la variable ivaría de 1 a 5, y dentro de esa variable de bucle jvaría de 1 a 2. Quiero un diccionario para cada combinación posible:

{'i': 1, 'j': 1}
{'i': 1, 'j': 2}
{'i': 2, 'j': 1}
{'i': 2, 'j': 2}
{'i': 3, 'j': 1}
{'i': 3, 'j': 2}
{'i': 4, 'j': 1}
{'i': 4, 'j': 2}
{'i': 5, 'j': 1}
{'i': 5, 'j': 2}

La razón es que quiero iterar sobre ellos. Pero debido a que todo el espacio es demasiado grande, no quiero generarlos todos, almacenarlos y luego iterar sobre esa lista de diccionarios. Pensé en usar el siguiente procedimiento recursivo, pero necesito ayuda con la yieldparte. Donde debe ser ¿Cómo evito los generadores anidados?

def iteration(conditions, currentCondition, valuedIndices):
    if currentCondition == len(conditions):
        yield valuedIndices
    else:
        cond = conditions[currentCondition]
        index = cond[0]
        lim1 = cond[1][0]
        lim2 = cond[1][1]
        for ix in range(lim1, lim2 + 1):
            valuedIndices[index] = ix
            yield iteration(conditions, currentCondition + 1, valuedIndices)

Ahora me gustaría poder hacer:

for valued_indices in iteration(conditions, 0, {}):
    ...
Noel Arteche
fuente
3
Simplemente reemplace yieldcon yield fromen la última línea de su función.
jfaccioni

Respuestas:

5

Este es un caso en el que podría ser más fácil dar un paso atrás y comenzar de nuevo.

Comencemos separando las claves y los intervalos, usando un truco bien conocido que involucra zip:

>>> keys, intervals = list(zip(*conditions))
>>> keys
('i', 'j')
>>> intervals
((1, 5), (1, 2))

(La correspondencia entre los dos conserva el emparejamiento original; intervals[i]es el intervalo para la variable keys[i]para todos i).

Ahora, creemos objetos de rango adecuados a partir de esos intervalos

>>> intervals = [range(x, y+1) for x, y in intervals]
>>> list(intervals[0])
[1, 2, 3, 4, 5]
>>> list(intervals[1])
[1, 2]

Podemos calcular el producto de estos rangeobjetos.

>>> for v in product(*intervals):
...   print(v)
...
(1, 1)
(1, 2)
(2, 1)
(2, 2)
(3, 1)
(3, 2)
(4, 1)
(4, 2)
(5, 1)
(5, 2)

que debe reconocer como los valores a utilizar para cada dict. Puede comprimir cada uno de esos valores con las claves para crear un conjunto apropiado de argumentos para el dictcomando. Por ejemplo:

>>> dict(zip(keys, (1,1)))
{'i': 1, 'j': 1}

Al unir todo esto, podemos iterar sobre el producto para producir cada uno dicta su vez, produciéndolo.

def iteration(conditions):
    keys, intervals = zip(*conditions)
    intervals = [range(x, y+1) for x, y in intervals]
    yield from (dict(zip(keys, v)) for v in product(*intervals))
chepner
fuente
0

Quizás pueda simplificar un poco con una comprensión interna del generador y yield from:

def dict_factory(i, j):
    r1 = range(1, i + 1)
    r2 = range(1, j + 1)
    dictgen = ({'i':x, 'j':y} for x in r1 for y in r2)
    yield from dictgen

usar como:

foo = dict_factory(5, 2)
while True:
    print(next(foo))
neutrino_logic
fuente
Dadas las condiciones se pasan como una lista de listas, sospecho que el OP necesita una solución que funcione para N número de condiciones no codificadas en 2
Chris Doyle
@Chris Doyle buen punto, la función probablemente debería estructurarse como dict_factory(*args)entonces ... Hmmm ...
neutrino_logic
0

No estoy seguro de si necesita usar la recursión específicamente o no, pero podría generarlos utilizando el método del producto itertools para generar todas las combinaciones. esto está escrito de tal manera que puede tener condiciones de 1 a n y aún debería funcionar y devolverle artículo por artículo.

from itertools import product


def iterations2(conditions):
    labels, ranges = list(zip(*conditions))
    ranges = [range(item[0], item[1] + 1) for item in ranges]
    for nums in product(*ranges):
        yield dict(zip(labels, nums))


conditions = [['i', (1, 5)], ['j', (1, 2)], ['z', (3, 6)]]
for valued_indices in iterations2(conditions):
    print(valued_indices)

SALIDA

{'i': 1, 'j': 1, 'z': 3}
{'i': 1, 'j': 1, 'z': 4}
{'i': 1, 'j': 1, 'z': 5}
{'i': 1, 'j': 1, 'z': 6}
{'i': 1, 'j': 2, 'z': 3}
{'i': 1, 'j': 2, 'z': 4}
{'i': 1, 'j': 2, 'z': 5}
{'i': 1, 'j': 2, 'z': 6}
{'i': 2, 'j': 1, 'z': 3}
{'i': 2, 'j': 1, 'z': 4}
{'i': 2, 'j': 1, 'z': 5}
{'i': 2, 'j': 1, 'z': 6}
{'i': 2, 'j': 2, 'z': 3}
{'i': 2, 'j': 2, 'z': 4}
{'i': 2, 'j': 2, 'z': 5}
{'i': 2, 'j': 2, 'z': 6}
{'i': 3, 'j': 1, 'z': 3}
{'i': 3, 'j': 1, 'z': 4}
{'i': 3, 'j': 1, 'z': 5}
{'i': 3, 'j': 1, 'z': 6}
{'i': 3, 'j': 2, 'z': 3}
{'i': 3, 'j': 2, 'z': 4}
{'i': 3, 'j': 2, 'z': 5}
{'i': 3, 'j': 2, 'z': 6}
{'i': 4, 'j': 1, 'z': 3}
{'i': 4, 'j': 1, 'z': 4}
{'i': 4, 'j': 1, 'z': 5}
{'i': 4, 'j': 1, 'z': 6}
{'i': 4, 'j': 2, 'z': 3}
{'i': 4, 'j': 2, 'z': 4}
{'i': 4, 'j': 2, 'z': 5}
{'i': 4, 'j': 2, 'z': 6}
{'i': 5, 'j': 1, 'z': 3}
{'i': 5, 'j': 1, 'z': 4}
{'i': 5, 'j': 1, 'z': 5}
{'i': 5, 'j': 1, 'z': 6}
{'i': 5, 'j': 2, 'z': 3}
{'i': 5, 'j': 2, 'z': 4}
{'i': 5, 'j': 2, 'z': 5}
{'i': 5, 'j': 2, 'z': 6}
Chris Doyle
fuente