Соображения относительно компромисса между пространством и временем для парсера на лету/предгенерации

Question

Перевешивают ли преимущества использования оперативного анализатора, связанные с пространством, преимущества предварительно созданной таблицы поиска, связанные со временем?

---

Длинная версия:

Я создаю справочный инструмент по химии и включаю функцию, которая будет автоматически называть формулы, соответствующие определенному шаблону;например C[n]H[2n+2] => [n]ane;где [n] является целым числом для LHS;и индекс массива имен в правой части.(meth, eth, …)

Насколько я вижу, это можно реализовать одним из двух способов:

1. Я предварительно создаю словарь двойного поиска ключ/значение formula <=> name пары;либо при запуске приложения (более медленный запуск), либо статический список, который публикуется вместе с приложением (более медленная загрузка).

2. Формулы оцениваются на лету специальным анализатором.

В подход 1. имя => поиск по формуле становится на порядок проще;но генератор, если я не хочу отправлять десятки мегабайт данных вместе с приложением, должен иметь предустановленное и довольно низкое значение для 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(), которая возвращает только следующий элемент и учитывается.)

Это жадный алгоритм, который не гарантирует наименьшего решения.Это сложнее, но поскольку сами химики имеют разные представления о правильной форме, я бы не стал так сильно беспокоиться об этом.