Памятка без массива

В разделе 15.3 « Элементы динамического программирования» Кормена и др. « Введение в алгоритмы» объясняется запоминание следующим образом:

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

И добавляет, как сноску:

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

Существуют ли какие-либо известные проблемы DP, которые требуют (или упрощают) сохранение запомненных значений в словаре, а не в (многомерном) массиве?

Предыстория: если это имеет какое-либо применение, причина этого вопроса в том, что я пытаюсь мотивировать понятие (самоуравновешенных) деревьев двоичного поиска людям, которые только что видели динамическое программирование.

Вероятно, есть лучшие примеры, но вот один из них:

$S,T$$\le d$$>d$

Я хотел бы привести 2 примера.

0-1 рюкзак проблема

В случае проблемы ранца 0-1 (где W - вместимость рюкзака, а N - количество предметов), иногда лучше использовать динамическое программирование сверху вниз с запоминанием, а не систематическое перечисление снизу вверх всего двумерного массива размера WxN (особенно в случае, когда вместимость ранца W велика, но мощность набора разрешенных комбинаций весов предметов значительно меньше W ).

В этом случае ради экономии памяти можно использовать словарь для запоминания вместо двумерного массива.

Алгоритм парсинга Эрли

Алгоритм парсинга Эрли можно использовать для парсинга операторов, принадлежащих к контекстно-свободной грамматике. В отличие от алгоритма CYK (который основан на подходе DP снизу вверх и использует 2D-таблицу для заметок) - анализатор Earley использует подход сверху вниз в сочетании с диаграммой синтаксического анализа для заметок.

Диаграмма синтаксического анализа содержит частично разобранные грамматические произведения (например, с учетом произведения X → AB и после успешного сопоставления части A этого произведения, мы сохраняем частично сопоставленное произведение внутри диаграммы анализа: X → A • B , где точки указывают к уже подобранной части).

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

Следовательно, более удобно реализовать диаграмму синтаксического анализа на основе структуры данных словаря.

В области обработки естественного языка обычно удобнее использовать pareser Earley, поскольку он не требует нормальной грамматической формы Хомского для грамматики (а в CYK такое требование есть).

По моему опыту конкурентного программирования, использование хеш-таблицы (Python dictили аналогичной) часто более удобно, чем использование массива, потому что любой тип данных с хэшированием можно использовать в качестве ключа, например, строки, наборы ( frozensetв Python) или кортежи, подобные (string, int)и т. Д. При использовании массива вы должны вручную перевести все ключи в целые числа (начиная с 0), что требует дополнительной работы и, как отмечает ваш источник, может оказаться невозможным, если вы заранее не знаете пространство ключей. Таким образом, словари являются более общими, чем массивы.

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