Parser On-the-Fly / PRE-Generation Space / Time Tradeoff Considerazioni

Question

I benefici relativi allo spazio dell'utilizzo di un parser on-the-fly superano i vantaggi relativi al tempo di una tabella di ricerca pre-generata?

---

.

Versione lunga:

Sto creando uno strumento di riferimento della chimica e sto includendo una funzione che chiamerà automaticamente le formule conformi a uno schema specifico; per esempio. C[n]H[2n+2] => [n]ane; dove [n] è un intero per il LHS; e un indice in una serie di nomi su RHS. (meth, eth, ...)

Per quanto posso vedere, questo può essere implementato in due modi:

.

1. I Pre-generare un dizionario chiave a doppia ricerca di coppie formula <=> name; O quando l'applicazione avvia (avvio più lento) o un elenco statico pubblicato con l'applicazione (download più lento).

2. Le formule vengono valutate al volo da un parser personalizzato.

   in approccio 1. Nome=> La ricerca della formula diventa più semplice da un ordine di grandezza; Ma il generatore non lo farà, a meno che non voglia spedire dozzine di megabyte di dati con l'applicazione, devi avere un preset, e abbastanza basso, valore per n.

   Compasto Questo è il fatto che le formule possono avere diversi termini; come C[n]H[2n+1]OC[n']H[2n'+1]; E per ciascuno di questi, il numero di corrispondenze possibili aumenta geometricamente con n. Inoltre, l'utilizzo di questo approccio mangerebbe la RAM come il business di nessuno.

   APPROCCIO 2. Consente di supportare valori abbastanza grandi di n utilizzando una tabella di ricerca abbastanza piccola, ma fa nome=> Ricerca formula in qualche modo più complessa. Rispetto alla pre-generazione di file per la spedizione con l'applicazione, consente inoltre di correggere gli errori nella logica di generazione senza dover spedire nuovi file di dati.

   Ciò richiede anche che ogni formula sia abbinata a un test cursale per diverse regole, determinare se potrebbe in forma; Che, se ci sono molte regole, richiede tempo che potrebbe portare a notevoli rallentamenti nell'interfaccia.

   La domanda allora, è:

   .

   1. Ci sono considerazioni nel compromesso che non sono riusciti a spiegare o approcci che non ho preso in considerazione?

   2. I benefici dell'utilizzo di un parser on-the-fly giustificano la maggiore complessità di implementazione?

Answer 1

Dovresti andare con il secondo approccio.

Una possibile soluzione è un algoritmo avido.Definisci il tuo set di trasformazioni come espressione regolare (utilizzata per testare il modello) e una funzione che viene data l'oggetto della partita di regexp e restituisce la stringa trasformata.

Le espressioni regolari non sono abbastanza potenti da gestire ciò che vuoi direttamente.Invece dovrai fare qualcosa come:

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

.

(più molto di più per le altre possibilità)

Quindi incorporalo in un ciclo che sembra:

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

.

(Dovrai gestire il caso in cui nulla corrisponde. Un modo possibile includere un elenco di tutti gli elementi possibili alla fine di find_replacement (), che restituisce solo il prossimo elemento e conta.)

Questo è un algoritmo avido, che non garantisce la soluzione più piccola.È più complicato, ma poiché i chimici stessi hanno idee diverse della forma giusta, non mi preoccuperei così tanto.