动态解析器​​/预生成空间/时间权衡注意事项

Question

使用即时解析器与空间相关的好处是否超过了预先生成的查找表与时间相关的好处？

---

长版：

我正在编写一个化学参考工具，并且包含一个功能，可以自动命名符合特定模式的公式；例如 C[n]H[2n+2] => [n]ane;在哪里 [n] 是 LHS 的整数；以及 RHS 上名称数组的索引。（meth, eth, …)

据我所知，这可以通过以下两种方式之一实现：

1. 我预先生成一个键/值双重查找字典 formula <=> name 成对；当应用程序启动时（启动速度较慢），或者与应用程序一起发布的静态列表（下载速度较慢）。

2. 公式由定制的解析器即时评估。

在 方法1. name => 公式查找变得简单了一个数量级；但是除非我想通过应用程序发送数十兆字节的数据，否则生成器必须有一个预设的且相当低的值 n.

更复杂的是，公式可以有多个项；例如 C[n]H[2n+1]OC[n']H[2n'+1];对于每一个，可能的匹配数量呈几何级数增加 n. 。此外，使用这种方法会消耗内存，这与任何人无关。

方法2。 让我支持相当大的值 n 使用相当小的查找表，但使名称=>公式查找更加复杂。与随应用程序一起交付的预生成文件相比，它还允许我纠正生成逻辑中的错误，而无需交付新的数据文件。

这还要求每个公式都与多个规则的粗略测试相匹配，以确定它是否 可以 合身;如果有很多规则，则需要时间，可能会导致界面明显变慢。

那么问题是：

1. 在权衡中是否有任何我没有考虑到的考虑因素，或者我没有考虑过的方法？

2. 使用即时解析器的好处是否证明增加的实现复杂性是合理的？

Answer 1

您应该采用第二种方法。

一种可能的解决方案是贪心算法。将一组转换定义为正则表达式（用于测试模式）和一个函数，该函数被赋予正则表达式匹配对象并返回转换后的字符串。

正则表达式不够强大，无法直接处理您想要的内容。相反，你必须做类似的事情：

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

（还有更多其他可能性）

然后将其嵌入到一个循环中，如下所示：

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

（您需要处理没有任何匹配的情况。一种可能的方法是在 find_replacement() 末尾包含所有可能元素的列表，该列表仅返回下一个元素并进行计数。）

这是一种贪心算法，不能保证最小解。这更复杂，但由于化学家本身对正确形式有不同的想法，所以我不会太担心。