Анализатор «на лету» / соображения компромисса между пространством и временем перед генерацией - PullRequest
Новая
       48

Анализатор «на лету» / соображения компромисса между пространством и временем перед генерацией

1 голос
/ 16 мая 2011

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

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

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

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

Тогда возникает вопрос:

  1. Есть ли какие-то соображения в обмене, которые я не учел, или подходы, которые я не учел?

  2. Оправдывают ли преимущества использования анализатора «на лету» повышенную сложность реализации?

1 Ответ

1 голос
/ 07 октября 2011

Вы должны пойти со вторым подходом.

Одним из возможных решений является жадный алгоритм.Определите ваш набор преобразований как регулярное выражение (используемое для проверки шаблона) и функцию, которая получает объект соответствия regexp и возвращает преобразованную строку.

Регулярные выражения недостаточно мощны, чтобы справиться схочу напрямую.Вместо этого вам нужно будет сделать что-то вроде: 

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

(плюс еще много для других возможностей)

, а затем встроить это в цикл, который будет выглядеть так:*

(Вам нужно будет обработать случай, когда ничего не совпадает. Один из возможных способов - включить список всех возможных элементов в конце find_replacement (), который возвращает только следующий элемент и считает.)

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

...