Überlegungen zum On-the-Fly-Parser/Raum/Zeit-Kompromiss vor der Generation

Question

Überwiegen die platzbezogenen Vorteile der Verwendung eines On-the-fly-Parsers die zeitbezogenen Vorteile einer vorgenerierten Nachschlagetabelle?

---

Lange Version:

Ich schreibe ein Chemie-Nachschlagewerk und füge eine Funktion hinzu, die automatisch Formeln benennt, die einem bestimmten Muster entsprechen;z.B. C[n]H[2n+2] => [n]ane;Wo [n] ist eine ganze Zahl für die linke Seite;und ein Index in ein Array von Namen im RHS.(meth, eth, …)

Soweit ich sehen kann, kann dies auf zwei Arten umgesetzt werden:

1. Ich generiere vorab ein Schlüssel/Wert-Dual-Lookup-Wörterbuch von formula <=> name Paare;entweder beim Start der Anwendung (langsamerer Start) oder eine statische Liste, die mit der Anwendung veröffentlicht wird (langsamerer Download).

2. Formeln werden im laufenden Betrieb von einem speziell entwickelten Parser ausgewertet.

In Ansatz 1. name => Formelsuche wird um eine Größenordnung einfacher;Aber der Generator muss, sofern ich nicht Dutzende Megabyte an Daten mit der Anwendung versenden möchte, einen voreingestellten und relativ niedrigen Wert für haben n.

Erschwerend kommt hinzu, dass Formeln mehrere Begriffe haben können;wie zum Beispiel C[n]H[2n+1]OC[n']H[2n'+1];und für jede davon erhöht sich die Anzahl der möglichen Übereinstimmungen geometrisch mit n.Darüber hinaus würde die Verwendung dieses Ansatzes RAM verschlingen, was niemanden etwas angehen würde.

Ansatz 2. lässt mich ziemlich große Werte unterstützen n Verwendung einer relativ kleinen Nachschlagetabelle, macht die Suche nach Name => Formeln jedoch etwas komplexer.Im Vergleich zur Vorgenerierung der Datei zum Versand mit der Anwendung kann ich damit auch Fehler in der Generierungslogik korrigieren, ohne neue Datendateien versenden zu müssen.

Dies erfordert auch, dass jede Formel mit einem oberflächlichen Test für mehrere Regeln abgeglichen wird, um festzustellen, ob dies der Fall ist könnte fit;Dies nimmt bei vielen Regeln Zeit in Anspruch und kann zu spürbaren Verlangsamungen der Benutzeroberfläche führen.

Die Frage ist dann:

1. Gibt es bei dem Kompromiss Überlegungen, die ich nicht berücksichtigt habe, oder Ansätze, die ich nicht berücksichtigt habe?

2. Rechtfertigen die Vorteile der Verwendung eines On-the-Fly-Parsers die erhöhte Komplexität der Implementierung?

Answer 1

Sie sollten den zweiten Ansatz wählen.

Eine mögliche Lösung ist ein Greedy-Algorithmus.Definieren Sie Ihren Transformationssatz als regulären Ausdruck (der zum Testen des Musters verwendet wird) und als Funktion, die das Regexp-Match-Objekt erhält und die transformierte Zeichenfolge zurückgibt.

Reguläre Ausdrücke sind nicht leistungsfähig genug, um direkt zu verarbeiten, was Sie wollen.Stattdessen müssen Sie Folgendes tun:

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

(und noch viel mehr für die anderen Möglichkeiten)

Dann betten Sie das in eine Schleife ein, die so aussieht:

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

(Sie müssen sich mit dem Fall befassen, in dem nichts übereinstimmt.Eine Möglichkeit besteht darin, am Ende von find_replacement() eine Liste aller möglichen Elemente einzufügen, die nur das nächste Element zurückgibt und zählt.)

Dies ist ein gieriger Algorithmus, der nicht die kleinste Lösung garantiert.Das ist komplizierter, aber da Chemiker selbst unterschiedliche Vorstellungen von der richtigen Form haben, würde ich mir darüber keine großen Sorgen machen.