python - tutorial - Calcular el "cierre" de los atributos de un objeto con funciones que cambian los atributos

the django project

Question

Tengo un objeto obj y una serie de funciones

    def func1(obj):
    #...

    def func2(obj):
    #...

    def func3(obj):
    #...

que cada cambio los valores de los atributos de obj .

Quiero que mi entrada sea algo así como

obj = MyObject()
obj.attr=22

Esto se debe pasar a un closure() función closure() que computa todas las posibles aplicaciones de las funciones anteriores, lo que significa func1(func2(obj)) , func3(func1(func1(obj))) etc. hasta una determinada condición de detención (p. Ej. más de 20 composiciones de funciones).

La salida debe ser una lista de todas las salidas posibles junto con todas las rutas que conducen allí. Entonces, digamos que 104 y 93 son las salidas finales posibles si obj.attr=22 , y hay dos formas de llegar a 104 y una para llegar a 93 . Entonces

print closure(obj)

debería ser algo así como

[22, 64, 21, 104] #first path to 104 through , func1(obj),func1(func1(obj)), func1(func1(func3(obj)))

[22, 73, 104] #second path to 104 through , func3(obj),func3(func2(obj)), 

[22, 11, 93] #the only path to arrive at 94

¿Cómo podría implementar esto? Como se sugirió en los comentarios, esto se hace mejor con árboles, pero aunque probé 2 días, casi no hice ningún progreso al implementar eso (¡soy nuevo en Python / programación)!
Mi ejemplo es tan simple que en lugar de func(obj) podríamos usar func(22) directamente, pero el ejemplo en el que necesito trabajar es más complicado, donde definitivamente necesitaré usar objetos, por lo que este sería solo un ejemplo mínimo de trabajo para eso.

El árbol probablemente no será un árbol arborescente completo, ya que cada aplicación de función contendrá una prueba si se puede aplicar al estado actual (de los atributos) de obj y en algunos casos la prueba fallará dejando (los atributos de ) obj sin cambios.

Answer 1

Aquí hay un ejemplo simple que trata de encontrar si un número ( goal ) es un predecesor de otro ( inital_state ) al aplicar la regla en la conjetura de Collatz .

En su ejemplo, obj es el state , y [func1, func2, ...] es functions en mi ejemplo. Esta versión devolverá una ruta a una salida final, minimizando el número de aplicaciones de función. En lugar de buscar, puede enumerar todos los estados eliminando la prueba de objetivo y devolviendo los prev_states después de que prev_states el ciclo.

from collections import deque

def multiply_by_two(x):
    return x * 2

def sub_one_div_three(x):
    if (x - 1) % 3 == 0:
        return (x - 1) // 3
    else:
        return None # invalid


functions = [multiply_by_two, sub_one_div_three]

# find the path to a given function
def bfs(initial_state, goal):
    initial_path = []
    states = deque([(initial_state, initial_path)])     # deque of 2-tuples: (state, list of functions to get there)
    prev_states = {initial_state}                       # keep track of previously visited states to avoid infinite loop

    while states:
        # print(list(map(lambda x: x[0], states)))      # print the states, not the paths. useful to see what''s going on
        state, path = states.popleft()

        for func in functions:
            new_state = func(state)

            if new_state == goal:                       # goal test: if we found the state, we''re done
                return new_state, path + [func]

            if (new_state is not None and           # check that state is valid
                new_state not in prev_states):      # and that state hasn''t been visited already
                states.append((new_state, path + [func]))
            prev_states.add(new_state)              # make sure state won''t be added again
    else:
        raise Exception("Could not get to state")

print(functions)
print(bfs(1, 5))

# prints (5, [<function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function sub_one_div_three at 0x000002E7493C9400>]). You can extract the path from here.

Answer 2

Suena divertido, dividámoslo en pasos.

1. Descubre las posibles combinaciones de funciones.

2. Evaluar posibles combinaciones de funciones.

Averiguar posibles combinaciones

Una forma de hacerlo es usar generadores. Son eficientes en términos de memoria, por lo que no termina creando un montón de valores y maximizando el montón.

Entonces, ¿cómo obtenemos todas las combinaciones? Una búsqueda rápida de documentos de Python sugiere el uso de itertools. Así que hagámoslo.

from itertools import combinations

def comb(fns, n):
     return combinations(fns, n)

Hasta ahora tenemos un generador que puede darnos todas las combinaciones (sin reemplazo) de una lista de funciones. Cada combinación proporcionada sería una lista de funciones n grande. Simplemente podemos llamar a cada uno por turno y podemos obtener el resultado compuesto.

Ese es un nivel en el árbol. ¿Cómo conseguimos el siguiente nivel? Bueno, podríamos obtener todas las combinaciones de tamaño 1 y luego todas las combinaciones de tamaño 2 y así sucesivamente. Como los generadores son flojos, debemos ser capaces de hacer esto sin explotar al intérprete.

def combo_tot(fns):
    start=1
    while (start <= len(fns)):
        for c in comb(fns, start):
            yield c
        start += 1

Evaluar posibles combinaciones

Entonces ahora tenemos todas las combinaciones posibles que tienen sentido. Usemos esto para evaluar cosas.

def evalf(fns_to_compose, initval):
    v = initval
    for fn in fns_to_compose:
        v = fn(v)
    return v

Entonces esa es la segunda parte. Ahora todo lo que necesitas hacer es encadenar em.

def results(fns, init):
    return (evalf(fn, init) for fn in combo_tot(fns))

Ahora solo tome tantos resultados como necesite.

Abajo

Lo mismo que con cualquier método que no clone el obj . Va a mutar el objeto. Además, tenemos la sobrecarga de los generadores (que puede ser un poco más lenta que los bucles for). También tenemos éxito en la legibilidad (especialmente si alguien no está familiarizado con los generadores).

Descargo de responsabilidad: Estoy escribiendo esto en un teléfono. Pueden existir errores menores de ortografía, etc.