Специализация алгоритма времени выполнения

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

В информатике специализация алгоритмов времени выполнения — это методология создания эффективных алгоритмов для ресурсоемких вычислительных задач определенных видов. Методология берет свое начало в области автоматизированного доказательства теорем и , в частности, в проекте Vampire Theorem Prover .

Идея вдохновлена ​​использованием частичной оценки при оптимизации трансляции программ. Многие основные операции в доказывателях теорем демонстрируют следующую закономерность. Предположим, что нам нужно выполнить некоторый алгоритм в ситуации, когда значение фиксировано для потенциально многих различных значений . Чтобы сделать это эффективно, мы можем попытаться найти специализацию для каждого фиксированного , т. е. такой алгоритм , выполнение которого эквивалентно выполнению .${\displaystyle {\mathit {алг}}(A,B)}$${\displaystyle А}$ ${\displaystyle Б}$${\displaystyle {\mathit {алг}}}$${\displaystyle А}$${\displaystyle {\mathit {алг}}_{А}}$${\displaystyle {\mathit {alg}}_{A}(B)}$${\displaystyle {\mathit {алг}}(A,B)}$

Специализированный алгоритм может быть более эффективным, чем общий, поскольку он может использовать некоторые особые свойства фиксированного значения . Как правило, может избегать некоторых операций, которые пришлось бы выполнять, если известно, что они избыточны для этого конкретного параметра . В частности, мы часто можем определить некоторые тесты, которые являются истинными или ложными для , развернуть циклы и рекурсию и т. д.${\displaystyle А}$${\displaystyle {\mathit {alg}}_{A}(B)}$${\displaystyle {\mathit {алг}}(A,B)}$${\displaystyle А}$${\displaystyle А}$

Ключевое различие между специализацией во время выполнения и частичной оценкой заключается в том, что значения , на которых выполняется специализация, статически неизвестны, поэтому специализация происходит во время выполнения .${\displaystyle А}$${\displaystyle {\mathit {алг}}}$

Также есть важное техническое различие. Частичная оценка применяется к алгоритмам, явно представленным в виде кодов на каком-либо языке программирования. Во время выполнения нам не нужно никакого конкретного представления . Нам нужно только представить , когда мы программируем процедуру специализации. Все, что нам нужно, — это конкретное представление специализированной версии . Это также означает, что мы не можем использовать какие-либо универсальные методы для специализации алгоритмов, что обычно имеет место при частичной оценке. Вместо этого нам приходится программировать процедуру специализации для каждого конкретного алгоритма . Важное преимущество этого заключается в том, что мы можем использовать некоторые мощные специальные приемы, эксплуатирующие особенности и представления и , которые находятся за пределами досягаемости любых универсальных методов специализации.${\displaystyle {\mathit {алг}}}$ ${\displaystyle {\mathit {алг}}}$ ${\displaystyle {\mathit {алг}}_{А}}$${\displaystyle {\mathit {алг}}}$${\displaystyle {\mathit {алг}}}$${\displaystyle А}$${\displaystyle Б}$

Специализированный алгоритм должен быть представлен в форме, которую можно интерпретировать. Во многих ситуациях, обычно когда необходимо вычислить множество значений подряд, мы можем записать его как код специальной абстрактной машины , и мы часто говорим, что он скомпилирован . Затем сам код может быть дополнительно оптимизирован с помощью преобразований, сохраняющих ответ, которые полагаются только на семантику инструкций абстрактной машины.${\displaystyle {\mathit {alg}}_{A}(B)}$${\displaystyle Б}$${\displaystyle {\mathit {алг}}_{А}}$${\displaystyle А}$

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

Интерпретация выполняется путем извлечения инструкций в некотором порядке, определения их типа и выполнения действий, связанных с этим типом. В C или C++ мы можем использовать оператор switch для связывания некоторых действий с различными тегами инструкций. Современные компиляторы обычно компилируют оператор switch с целочисленными метками из узкого диапазона довольно эффективно, сохраняя адрес оператора, соответствующего значению в -й ячейке специального массива. Это можно использовать, беря значения для тегов инструкций из небольшого интервала целых чисел.${\displaystyle я}$${\displaystyle я}$

Бывают ситуации, когда многие экземпляры предназначены для долговременного хранения, а вызовы происходят с разными в непредсказуемом порядке. Например, нам может потребоваться сначала проверить, затем , затем и так далее. В таких обстоятельствах полномасштабная специализация с компиляцией может оказаться неподходящей из-за чрезмерного использования памяти. Однако иногда мы можем найти компактное специализированное представление для каждого , которое можно хранить с или вместо . Мы также определяем вариант , который работает с этим представлением, и любой вызов заменяется на , предназначенный для более быстрого выполнения той же работы.${\displaystyle А}$${\displaystyle {\mathit {алг}}(A,B)}$${\displaystyle Б}$${\displaystyle {\mathit {алг}}(A_{1},B_{1})}$${\displaystyle {\mathit {алг}}(A_{2},B_{2})}$${\displaystyle {\mathit {алг}}(A_{1},B_{3})}$${\displaystyle A^{\prime}}$${\displaystyle А}$${\displaystyle А}$${\displaystyle {\mathit {алг}}^{\prime }}$${\displaystyle {\mathit {алг}}(A,B)}$${\displaystyle {\mathit {alg}}^{\prime }(A^{\prime },B)}$

• Psyco , специализированный компилятор времени выполнения для Python
• многоэтапное программирование

• А. Воронков, «Анатомия вампира: реализация процедур снизу вверх с помощью деревьев кодов», Журнал автоматизированного рассуждения, 15(2), 1995 ( оригинальная идея )

• А. Рязанов и А. Воронков , «Эффективная проверка ограничений порядка термов», Proc. IJCAR 2004, Lecture Notes in Artificial Intelligence 3097, 2004 ( компактная, но самодостаточная иллюстрация метода )
• А. Рязанов и А. Воронков, Эффективный поиск экземпляров с помощью стандартного и реляционного индексирования путей, Информация и вычисления , 199(1-2), 2005 ( содержит еще одну иллюстрацию метода )
• А. Рязанов, «Реализация эффективного средства доказательства теорем», докторская диссертация, Манчестерский университет, 2003 г. ( содержит наиболее полное описание метода и множество примеров )