Considérations de compromis d'espace d'analyseur / pré-génération / compromis de pré-génération

Question

Les avantages liés à l'espace de l'utilisation d'un analyseur à la volée l'emportent-ils sur les avantages liés au temps d'une table de recherche pré-générée?

---

Version longue:

Je rédige un outil de référence en chimie et j'incluant une fonctionnalité qui nommera automatiquement les formules conformes à un modèle spécifique; par exemple C[n]H[2n+2] => [n]ane; où [n] est un entier pour le LHS; et un index dans un tableau de noms sur le RHS. (meth, eth, …)

Pour autant que je puisse voir, cela peut être mis en œuvre de deux manières:

1. Je pré-génére un dictionnaire de recherche double clé / valeur de formula <=> name paires; Soit lorsque l'application démarre (démarrage plus lent), soit une liste statique publiée avec l'application (téléchargement plus lent).

2. Les formules sont évaluées à la volée par un analyseur sur mesure.

Dans Approche 1. Nom => La recherche de formule devient plus simple par un ordre de grandeur; Mais le générateur, à moins que je veuille expédier des dizaines de mégaoctets de données avec l'application, il faut avoir une valeur préréglée et assez faible pour n.

Composé C'est le fait que les formules peuvent avoir plusieurs termes; tel que C[n]H[2n+1]OC[n']H[2n'+1]; Et pour chacun d'eux, le nombre de correspondances possibles augmente géométriquement avec n. De plus, l'utilisation de cette approche mangerait RAM comme les affaires de personne.

Approche 2. me permet de soutenir des valeurs assez importantes de n Utilisation d'une table de recherche assez petite, mais rend Name => la recherche de formule un peu plus complexe. Comparé à la pré-génération pour déposer une exploition avec l'application, il me permet également de corriger les erreurs dans la logique de génération sans avoir à expédier de nouveaux fichiers de données.

Cela nécessite également que chaque formule soit adaptée à un test superficiel pour plusieurs règles, déterminant s'il pourrait adapter; Ce qui, s'il y a beaucoup de règles, prend du temps qui pourrait entraîner des ralentissements notables dans l'interface.

La question est alors:

1. Y a-t-il des considérations dans le compromis que je n'ai pas pris en compte ou des approches que je n'ai pas envisagées?

2. Les avantages de l'utilisation d'un analyseur à la volée justifient-ils la complexité de mise en œuvre accrue?

Answer 1

Vous devriez aller avec la deuxième approche.

Une solution possible est un algorithme gourmand. Définissez votre ensemble de transformations comme une expression régulière (utilisée pour tester le motif) et une fonction qui est donnée à l'objet de correspondance regexp et renvoie la chaîne transformée.

Les expressions régulières ne sont pas assez puissantes pour gérer ce que vous voulez directement. Au lieu de cela, vous devrez faire quelque chose comme:

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

(plus beaucoup plus pour les autres possibilités)

Ensuite, intégrez cela dans une boucle qui ressemble:

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

(Vous devrez gérer le cas où rien correspond.

Il s'agit d'un algorithme gourmand, qui ne garantit pas la plus petite solution. C'est plus compliqué, mais comme les chimistes eux-mêmes ont des idées différentes de la bonne forme, je ne m'inquiéterais pas autant à ce sujet.