Инкрементные вычисления, также известные как инкрементные вычисления, являются функцией программного обеспечения, который при изменении фрагмента данных пытается сэкономить время путем пересчета только тех выходных данных, которые зависят от измененных данных. Когда инкрементные вычисления успешны, они могут быть значительно быстрее, чем наивное вычисление новых результатов. Например, программный пакет электронной таблицы может использовать инкрементные вычисления в своей функции пересчета, чтобы обновлять только те ячейки, которые содержат формулы, которые зависят (прямо или косвенно) от измененных ячеек.
Когда инкрементальные вычисления реализованы с помощью инструмента, который может автоматически реализовать его для множества различных фрагментов кода, этот инструмент является примером инструмента анализа программ для оптимизации.
Инкрементальные вычисления выводят новую пару ввода / вывода из одного или нескольких старых отношений ввода / вывода. Для этого ΔP должно соотносить изменение входа с изменением выхода. Потребитель результата может быть заинтересован в полностью обновленном выходе, или дельта-выходе, или обоими.Методы инкрементных вычислений можно в целом разделить на два типа подходов:
Статические подходы пытаются получить инкрементную программу из обычной программы P с использованием, например, либо ручное проектирование и рефакторинг, либо автоматические преобразования программы. Эти программные преобразования происходят до того, как будут предоставлены какие-либо входные данные или изменения входных данных.
Динамические подходы записывают информацию о выполнении программы P на конкретном входе (I1) и используют эту информацию, когда вход изменяется (на I2), для обновления вывода (с O1 на O2). На рисунке показана взаимосвязь между программой P, функцией вычисления изменений ΔP, которая составляет ядро инкрементальной программы, и парой входов и выходов, I1, O1 и I2, O2.
Некоторые подходы к инкрементным вычислениям являются специализированными, а другие - универсальными. Специализированные подходы требуют от программиста явного указания алгоритмов и структур данных, которые будут использоваться для сохранения неизменными подвычислений. С другой стороны, универсальные подходы используют язык, компилятор или алгоритмические методы для придания инкрементного поведения неинкрементным программам.
Учитывая вычисление и потенциальное изменение , мы можем вставить код перед изменением (предварительно производная) и после изменения (пост-производная) для обновления значения быстрее, чем повторный запуск . Пейдж записала список правил для формального разделения программ в SUBSETL.
В системах баз данных, таких как DBToaster, представления определяются с помощью реляционной алгебры. Инкрементное обслуживание представления статически анализирует реляционную алгебру для создания правил обновления, которые быстро поддерживают представление при наличии небольших обновлений, таких как вставка строки.
Инкрементные вычисления могут быть выполнены с помощью построение графа зависимостей всех элементов данных, которые могут нуждаться в пересчете, и их зависимостей. Элементы, которые необходимо обновить при изменении одного элемента, задаются переходным замыканием отношения зависимости графа. Другими словами, если существует путь от измененного элемента к другому элементу, последний может быть обновлен (в зависимости от того, дойдет ли изменение в конечном итоге до элемента). Граф зависимостей может нуждаться в обновлении по мере изменения зависимостей, добавления или удаления элементов из системы. Он используется внутри реализации и обычно не требуется отображать для пользователя.
Захвата зависимостей по всем возможным значениям можно избежать, определив подмножество важных значений (например, результаты агрегирования), по которым можно отслеживать зависимости, и постепенно пересчитывая другие зависимые переменные, тем самым уравновешивая объем информации о зависимостях, чтобы быть отслеживается с объемом повторных вычислений, которые должны быть выполнены при изменении ввода.
Частичная оценка может рассматриваться как метод автоматизации простейшего возможного случая инкрементных вычислений, в котором делается попытка разделить данные программы на две категории : то, что может варьироваться в зависимости от ввода программы, и то, что не может (и наименьшая единица изменения - это просто «все данные, которые могут варьироваться»). Частичная оценка может сочетаться с другими методами инкрементальных вычислений.
С циклами в графике зависимостей одного прохода по графику может быть недостаточно для достижения фиксированной точки. В некоторых случаях полная переоценка системы семантически эквивалентна инкрементной оценке и может быть более эффективной на практике, если не теоретически.