Consideraciones sobre el equilibrio entre el analizador sobre la marcha y el espacio/tiempo previo a la generación

Question

¿Los beneficios relacionados con el espacio de utilizar un analizador sobre la marcha superan los beneficios relacionados con el tiempo de una tabla de búsqueda generada previamente?

---

Versión larga:

Estoy creando una herramienta de referencia de química e incluyo una función que nombrará automáticamente fórmulas que se ajusten a un patrón específico;p.ej. C[n]H[2n+2] => [n]ane;dónde [n] es un número entero para el LHS;y un índice en una serie de nombres en el RHS.(meth, eth, …)

Por lo que puedo ver, esto se puede implementar de dos maneras:

1. Pregenero un diccionario de búsqueda dual clave/valor de formula <=> name pares;ya sea cuando se inicia la aplicación (inicio más lento) o una lista estática que se publica con la aplicación (descarga más lenta).

2. Las fórmulas se evalúan sobre la marcha mediante un analizador personalizado.

En enfoque 1. nombre => la búsqueda de fórmulas se vuelve más simple en un orden de magnitud;pero el generador, a menos que quiera enviar docenas de megabytes de datos con la aplicación, tendrá que tener un valor preestablecido y bastante bajo para n.

A esto se suma el hecho de que las fórmulas pueden tener varios términos;como C[n]H[2n+1]OC[n']H[2n'+1];y para cada uno de estos, el número de coincidencias posibles aumenta geométricamente con n.Además, utilizar este enfoque consumiría RAM como si no fuera asunto de nadie.

Enfoque 2. me permite soportar valores bastante grandes de n usando una tabla de búsqueda bastante pequeña, pero hace que la búsqueda de nombre => fórmula sea algo más compleja.En comparación con la generación previa del archivo para su envío con la aplicación, también me permite corregir errores en la lógica de generación sin tener que enviar nuevos archivos de datos.

Esto también requiere que cada fórmula se compare con una prueba superficial para varias reglas, determinando si podría adaptar;lo cual, si hay muchas reglas, lleva un tiempo que puede provocar ralentizaciones notables en la interfaz.

La pregunta entonces es:

1. ¿Hay alguna consideración en la compensación que no haya tenido en cuenta o enfoques que no haya considerado?

2. ¿Los beneficios de utilizar un analizador sobre la marcha justifican la mayor complejidad de la implementación?

Answer 1

Deberías optar por el segundo enfoque.

Una posible solución es un algoritmo codicioso.Defina su conjunto de transformaciones como una expresión regular (usada para probar el patrón) y una función a la que se le asigna el objeto de coincidencia de expresión regular y devuelve la cadena transformada.

Las expresiones regulares no son lo suficientemente poderosas para manejar lo que deseas directamente.En su lugar tendrás que hacer algo como:

m = re.match(r"C\[(\d+)\]H\[(\d+)]\]", formula)
if m:
    C_count, H_count = int(m.group(1)), int(m.group(2))
    match_size = len(m.group(0))
    if C_count*2+2 == H_count:
        replacement = alkane_lookup[C_count]
    elif C_count*2 == H_count:
        replacement = alkene_lookup[C_count]
    ...
    else:
        replacement = m.group(0)  # no replacement available

(y mucho más para las otras posibilidades)

luego incruste eso en un bucle que se ve así:

formula = "...."
new_formula = ""
while formula:
    match_size, replacement = find_replacement(formula)
    new_formula += replacement
    formula = formula[match_size:]

(Tendrás que encargarte del caso en el que nada coincida.Una forma posible es incluir una lista de todos los elementos posibles al final de find_replacement(), que solo devuelve el siguiente elemento y cuenta).

Este es un algoritmo codicioso que no garantiza la solución más pequeña.Eso es más complicado, pero como los propios químicos tienen ideas diferentes sobre la forma correcta, no me preocuparía tanto por eso.