Гибридный алгоритм
 |
Гибридный алгоритм — это алгоритм , который объединяет два или более других алгоритма, решающих одну и ту же задачу, либо выбирая один на основе какой-либо характеристики данных, либо переключаясь между ними в ходе работы алгоритма. Обычно это делается для объединения желаемых функций каждого из них, чтобы общий алгоритм был лучше, чем отдельные компоненты.
«Гибридный алгоритм» не относится к простому объединению нескольких алгоритмов для решения другой проблемы — многие алгоритмы можно рассматривать как комбинации более простых частей — а только к объединению алгоритмов, которые решают одну и ту же проблему, но различаются по другим характеристикам, особенно по производительности.
Примеры [ править ]
В информатике гибридные алгоритмы очень распространены в оптимизированных реальных реализациях рекурсивных алгоритмов , особенно реализациях в Алгоритмы «разделяй и властвуй» или «уменьшай и властвуй» , где размер данных уменьшается по мере углубления в рекурсию. В этом случае для общего подхода (на больших данных) используется один алгоритм, но в глубине рекурсии он переключается на другой алгоритм, который более эффективен на небольших данных. Типичным примером являются алгоритмы сортировки , где сортировка вставкой, которая неэффективна для больших данных, но очень эффективна для небольших данных (скажем, от пяти до десяти элементов), используется в качестве последнего шага после первоначального применения другого алгоритма, такого как сортировка слиянием или быстрая сортировка . Сортировка слиянием и быстрая сортировка асимптотически оптимальны для больших данных, но накладные расходы становятся значительными, если применять их к небольшим данным, поэтому в конце рекурсии используется другой алгоритм. Высоко оптимизированный алгоритм гибридной сортировки — Timsort , который сочетает в себе сортировку слиянием, сортировку вставкой и дополнительную логику (включая двоичный поиск ) в логике слияния.
Общая процедура для простого гибридного рекурсивного алгоритма — это короткое замыкание базового случая, также известное как рекурсия на расстоянии вытянутой руки . В этом случае перед вызовом функции проверяется, приведет ли следующий шаг к базовому случаю, что позволяет избежать ненужного вызова функции. Например, в дереве вместо того, чтобы рекурсивно обращаться к дочернему узлу и затем проверять, имеет ли он значение NULL, перед рекурсией следует проверять значение NULL. Это полезно для повышения эффективности, когда алгоритм обычно много раз сталкивается с базовым случаем, как во многих древовидных алгоритмах, но в противном случае это считается плохим стилем, особенно в научных кругах, из-за дополнительной сложности.
Другим примером гибридных алгоритмов по соображениям производительности являются introsort и introselect , которые объединяют один алгоритм для быстрого усреднения производительности с использованием другого алгоритма для обеспечения (асимптотически) оптимальной производительности в худшем случае. Интросорт начинается с быстрой сортировки , но переключается на сортировку кучей, если быстрая сортировка не продвигается хорошо; аналогично introselect начинается с fastselect , но переключается на медиану медиан, если быстрый выбор не выполняется должным образом.
Централизованные распределенные алгоритмы часто можно рассматривать как гибридные алгоритмы, состоящие из отдельного алгоритма (выполняемого на каждом распределенном процессоре) и комбинированного алгоритма (выполняемого на централизованном распределителе) – они соответствуют соответственно запуску всего алгоритма на одном процессоре или запуску все вычисления на распределителе, объединяющие тривиальные результаты (одноэлементный набор данных от каждого процессора). Базовым примером этих алгоритмов являются сортировки по распределению , особенно используемые для внешней сортировки , которые делят данные на отдельные подмножества, сортируют подмножества, а затем объединяют подмножества в полностью отсортированные данные; примеры включают сегментную сортировку и флэш-сортировку .
Однако в целом распределенные алгоритмы не обязательно должны быть гибридными алгоритмами, поскольку отдельные алгоритмы или алгоритмы объединения или связи могут решать разные проблемы. Например, в таких моделях, как MapReduce , этапы Map и Reduc решают разные проблемы и объединяются для решения другой, третьей проблемы.