1

使用动态解析器​​的空间相关优势是否超过了预先生成的查找表的时间相关优势？

长版：

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

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

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

  2. 公式由定制的解析器动态评估。

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

更复杂的是公式可以有多个术语。如C[n]H[2n+1]OC[n']H[2n'+1]; 对于这些中的每一个，可能匹配的数量随着 几何增加n。此外，使用这种方法会像没人管一样吃掉 RAM。

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

这还要求将每个公式与几个规则的粗略测试进行匹配，以确定它是否适合；如果有很多规则，这会花费一些时间，这可能会导致界面明显变慢。

那么问题来了：

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

  2. 使用动态解析器​​的好处是否证明了增加的实现复杂性？

4

1 回答 1

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() 的末尾包含所有可能元素的列表，它只返回下一个元素并计数。）

这是一个贪心算法，它不能保证最小的解决方案。这更复杂，但由于化学家自己对正确形式有不同的想法，我不会太担心。

于 2011-10-07T18:56:04.133 回答