Cтраница 1
Мемо-таблицы и их элементы рассматриваются сборщиком мусора как ячейки особого вида. [1]
Регулировщики таблиц регулируют рост мемо-таблиц путем удаления определенных элементов таблиц при вводе новых. [2]
При таком подходе разрастание ленивых мемо-таблиц может быть в некоторой мере ограничено. [3]
Выигрыш пространства, даваемый динамическим регулированием мемо-таблиц, достигается за счет небольшого увеличения стоимости выполнения операции вставки, так как теперь необходимо каждый раз инициировать регулировщик таблиц. Однако для работы регулировщиков таблиц не требуется дополнительных ( инструментальных) средств, поскольку они просто выражены в компилируемом функциональном языке и являются нерекурсивными. При выполнении мемо-функции основные условные выражения проверяются до выполнения просмотра. При истинности данного условия мемо-функция возвращает результат базового случая и не изменяет мемо-таблицу. В противном случае выполняется просмотр для установления того, известен ли данный результат. В связи с тем что элементы, относящиеся к базовому случаю, никогда не заносятся в мемо-таблицу, то для регулировщика таблиц нет необходимости проверять их. [4]
Мт) - Таким образом, как только мемо-таблица достигает своего максимального размера, то при добавлении нового элемента будет удаляться один старый, или, альтернативно, старый элемент таблицы будет заменяться новым. [5]
Однако наиболее серьезным ограничением запоминания является то, что мемо-таблицы бесконечно наращиваются при добавлении каждого нового элемента, и даже если данный аргумент никогда больше не будет использован мемо-функцией, он все равно продолжает храниться в таблице. [6]
Если не предпринимать никаких действий для удаления неиспользуемых элементов из мемо-таблицы, то ее наращивание будет происходить непрерывно; при применении ассоциированной с ней функции к новому аргументу к ней будет прибавляться новый элемент. Именно эти излишние затраты памяти помешали запоминанию сразу же стать широко используемым видом оптимизации; в последнее время в решении этой проблемы достигнуты некоторые успехи. Существуют два пути контроля роста мемо-таблицы. Первый состоит в расширении функ-ций сборщика мусора для восстановления неиспользуемых элементов мемо-таблицы; мы обсудим это в разд. [7]
Описанный выше вид локального запоминания не позволяет осуществлять динамическое управление мемо-таблицами, при котором по мере добавления новых элементов таблицы устаревшие и ненужные элементы удаляются из нее, причем полного разрушения таблицы при этом не происходит. Это позволяет сохранять размер мемо-таблиц в разумных контролируемых пределах; во многих случаях это небольшое фиксированное число элементов. Мы сосредоточим наше внимание главным образом на локальном запоминании, при котором мемо-таблица создается для каждого применения верхнего уровня мемо-функ-ции, а запоминание происходит лишь для применений этих функций, входящих в описывающие ее уравнения, а также в уравнения других функций, вызываемые из них. Некоторая ограниченность подобного подхода проявляется, например, в том, что два применения верхнего уровня функции fib ( 20) будут выполняться за линейное время каждая при локальном запоминании в то время, как второе применение может быть выполнено за постоянное время при простом поиске и нахождении своего результата в мемо-таблице первой функции, если эта таблица не была разрушена. Далее мы увидим, что при этом ограничении компилятор способен во многих случаях автоматически определять стратегию динамического удаления путем простого грамматического анализа выражения, описывающего мемо-функцию. [8]
Вспомогательные операции in memo table, lookup и insert работают с мемо-таблицей. [9]
Когда мемо-функция вновь применяется к тому же аргументу, то результат ищется в мемо-таблице, а не вычисляется заново. [10]
В нашем примере с циклическим списком единиц в предыдущей главе очень важно, чтобы мемо-таблица оставалась неповрежденной в течение времени обработки данной циклической структуры некоторой функцией. С другой стороны, бесконечный список может быть вычислен обычным путем, без использования запоминания. [11]
Функция Фибоначчи, естественно, удовлетворяет этим условиям, как мы указывали выше LCC sub2, мемо-таблица не содержит более двух элементов, а время выполнения функции линейно зависит от аргумента. Это же относится и ко всем другим функциям, удовлетворяющим условиям теоремы о линеаризации - эти условия включают в себя условия, необходимые для запоминания и некоторые другие. [12]
Ленивые мемо-функции были введены для использования их в ленивых реализациях функциональных языков; они упрощают представление в мемо-таблицах тех аргументов, хранение которых в полном вычисленном виде больше не является необходимым. При этом устраняются многие трудности, связанные с рекурсивной проверкой на равенство и хэшированием, так что эта методика также годится и для строгих реализаций. Основная мысль заключается в смягчении тех требований, которым должна удовлетворять мемо-функция; мы скоро увидим, что все мемо-функции могут быть заданы через ленивые мемо-функции; другими словами, использование ленивой методики не приводит к потере общности. Обычные мемо-функции, которые мы будем называть полными мемо-функциями, требуются для повторного использования уже вычисленных результатов, если они применяются к аргументам, равным тем, которые были использованы накануне. [13]
На самом же деле, как мы увидим, модификация сборщика мусора, необходимая для корректной обработки им элементов мемо-таблиц и их результатов, не является чрезмерно сложной. [14]
В приведенном выше представлении запоминания мы предполагали, что во время прогона поддерживаются все примитивы, необходимые для доступа и создания мемо-таблиц, а именно операции in memo table, lookup и insert. Можно объединить первые две из этих операций в одну функцию, возвращающую пару величин: булеву величину, указывающую, насколько успешно прошел просмотр таблицы ( был ли успешным просмотр или нет), и результат, если он был обнаружен, а в противном случае - неопределенное значение. Операция вставки insert должна использовать регулировщик таблиц, созданный для этой мемо-функции ( либо непосредственно программистом, либо компилятором для вырожденной мультилинейной функции), а затем создать новый элемент таблицы после, возможно, удаления одного старого. [15]