В информатике in-place алгоритм — это алгоритм , который работает непосредственно со структурой входных данных , не требуя дополнительного пространства, пропорционального размеру входных данных. Другими словами, он изменяет входные данные на месте, не создавая отдельную копию структуры данных. Алгоритм, который не находится на месте, иногда называют not-in-place или out-of-place .
In-place может иметь немного разные значения. В своей самой строгой форме алгоритм может иметь только постоянное количество дополнительного пространства , считая все, включая вызовы функций и указатели . Однако эта форма очень ограничена, так как простое наличие индекса для массива длины n требует O (log n ) бит. В более широком смысле, in-place означает, что алгоритм не использует дополнительное пространство для манипулирования входными данными, но может потребовать небольшое, хотя и непостоянное дополнительное пространство для своей работы. Обычно это пространство составляет O (log n ) , хотя иногда допускается все, что находится в o ( n ) . Обратите внимание, что сложность пространства также имеет различные варианты в отношении того, следует ли считать длины индексов как часть используемого пространства. Часто сложность пространства задается в терминах количества необходимых индексов или указателей, игнорируя их длину. В этой статье мы ссылаемся на общую сложность пространства ( DSPACE ), подсчитывая длины указателей. Поэтому требования к пространству здесь имеют дополнительный фактор log n по сравнению с анализом, который игнорирует длину индексов и указателей.
Алгоритм может учитывать или не учитывать вывод как часть своего использования пространства. Поскольку алгоритмы на месте обычно перезаписывают свой ввод выводом, никакого дополнительного пространства не требуется. При записи вывода в память только для записи или поток может быть более целесообразным учитывать только рабочее пространство алгоритма. В теоретических приложениях, таких как сокращение логарифмического пространства , более типично всегда игнорировать выходное пространство (в этих случаях более существенно, чтобы вывод был только для записи ).
Предположим , что нам нужен массив a из n элементов, содержащий те же элементы в обратном порядке, и мы хотим избавиться от оригинала. Один из, казалось бы, простых способов сделать это — создать новый массив равного размера, заполнить его копиями из aв соответствующем порядке, а затем удалить a.
функция обратная(a[0..n - 1]) выделить b[0..n - 1] для i от 0 до n - 1 б[n − 1 − i] := а[i] возвращение б
К сожалению, это требует O ( n ) дополнительного пространства для того, чтобы массивы aи bбыли доступны одновременно. Кроме того, выделение и освобождение часто являются медленными операциями. Поскольку нам больше не нужно a, мы можем вместо этого перезаписать его собственным обращением, используя этот алгоритм на месте, которому потребуется только постоянное число (2) целых чисел для вспомогательных переменных iи tmp, независимо от размера массива.
функция reverse_in_place(a[0..n-1]) для i от 0 до floor((n-2)/2) тмп := а[i] а[я] := а[n − 1 − я] а[n − 1 − i] := тмп
В качестве другого примера, многие алгоритмы сортировки перестраивают массивы в отсортированный порядок на месте, включая: пузырьковую сортировку , сортировку гребенкой , сортировку выбором , сортировку вставкой , пирамидальную сортировку и сортировку Шелла . Эти алгоритмы требуют всего несколько указателей, поэтому их пространственная сложность составляет O (log n ) . [1]
Быстрая сортировка работает на месте с сортируемыми данными. Однако быстрая сортировка требует O (log n ) указателей стекового пространства для отслеживания подмассивов в своей стратегии «разделяй и властвуй» . Следовательно, быстрой сортировке требуется O (log 2 n ) дополнительного пространства. Хотя это непостоянное пространство технически выводит быструю сортировку из категории сортировки на месте, быстрая сортировка и другие алгоритмы, которым требуется только O (log n ) дополнительных указателей, обычно считаются алгоритмами на месте.
Большинство алгоритмов выбора также работают, хотя некоторые из них существенно перестраивают входной массив в процессе поиска окончательного результата постоянного размера.
Некоторые алгоритмы обработки текста, такие как обрезка и реверс, могут быть реализованы на месте.
В теории вычислительной сложности строгое определение алгоритмов на месте включает все алгоритмы с O (1) пространственной сложностью, класс DSPACE (1). Этот класс очень ограничен; он равен обычным языкам . [2] Фактически, он даже не включает ни один из примеров, перечисленных выше.
Алгоритмы обычно рассматриваются в L , классе задач, требующих O (log n ) дополнительного пространства, чтобы быть на месте. Этот класс больше соответствует практическому определению, поскольку он допускает числа размера n в качестве указателей или индексов. Однако это расширенное определение по-прежнему исключает быструю сортировку из-за ее рекурсивных вызовов.
Идентификация алгоритмов на месте с L имеет некоторые интересные последствия; например, это означает, что существует (довольно сложный) алгоритм на месте для определения того, существует ли путь между двумя узлами в неориентированном графе , [3] проблема, которая требует O ( n ) дополнительного пространства с использованием типичных алгоритмов, таких как поиск в глубину (посещенный бит для каждого узла). Это, в свою очередь, дает алгоритмы на месте для таких задач, как определение того, является ли граф двудольным , или проверка того, имеют ли два графа одинаковое количество связных компонентов .
Во многих случаях требования к пространству алгоритма можно радикально сократить, используя рандомизированный алгоритм . Например, если кто-то хочет узнать, находятся ли две вершины в графе из n вершин в одном и том же компоненте связности графа, не существует известного простого, детерминированного алгоритма на месте для определения этого. Однако, если мы просто начнем с одной вершины и выполним случайное блуждание примерно из 20 n 3 шагов, вероятность того, что мы наткнемся на другую вершину, при условии, что она находится в том же компоненте, очень высока. Аналогично, существуют простые рандомизированные алгоритмы на месте для проверки простоты, такие как тест простоты Миллера–Рабина , а также существуют простые рандомизированные алгоритмы факторизации на месте, такие как алгоритм Полларда rho .
Функциональные языки программирования часто не поощряют или не поддерживают явные in-place алгоритмы, которые перезаписывают данные, поскольку это тип побочного эффекта ; вместо этого они позволяют только создавать новые данные. Однако хорошие компиляторы функциональных языков часто распознают, когда создается объект, очень похожий на существующий, а затем старый отбрасывается, и оптимизируют это в простую мутацию «под капотом».
Обратите внимание, что в принципе возможно тщательно сконструировать алгоритмы на месте, которые не изменяют данные (если только данные больше не используются), но на практике это делается редко.