Гибридный алгоритм - Hybrid algorithm
Гибридный алгоритм представляет собой алгоритм , который сочетает в себе два или более другие алгоритмы , которые решают ту же проблему, и в основном используются в языках программирования , как C ++ , либо выбрать один ( в зависимости от данных), или переключаться между ними в течение алгоритма. Обычно это делается для объединения желаемых функций каждого из них, чтобы общий алгоритм был лучше, чем отдельные компоненты.
«Гибридный алгоритм» не относится к простому объединению нескольких алгоритмов для решения другой проблемы - многие алгоритмы можно рассматривать как комбинации более простых частей - а только к объединению алгоритмов, которые решают одну и ту же проблему, но отличаются другими характеристиками, особенно производительностью.
Примеры
В информатике гибридные алгоритмы очень распространены в оптимизированных реальных реализациях рекурсивных алгоритмов , особенно в реализациях алгоритмов « разделяй и властвуй» или « уменьшай и властвуй» , где размер данных уменьшается по мере продвижения в рекурсию. В этом случае для общего подхода (для больших данных) используется один алгоритм, но в глубине рекурсии он переключается на другой алгоритм, который более эффективен для небольших данных. Типичный пример - алгоритмы сортировки , где сортировка вставкой, которая неэффективна для больших данных, но очень эффективна для небольших данных (скажем, от пяти до десяти элементов), используется в качестве последнего шага после первичного применения другого алгоритма, такого как сортировка слиянием или быстрая сортировка . Сортировка слиянием и быстрая сортировка асимптотически оптимальны для больших данных, но накладные расходы становятся значительными при их применении к небольшим данным, поэтому в конце рекурсии используется другой алгоритм. Высокооптимизированный алгоритм гибридной сортировки - это Timsort , который сочетает сортировку слиянием, сортировку вставкой вместе с дополнительной логикой (включая двоичный поиск ) в логике слияния.
Общая процедура для простого гибридного рекурсивного алгоритма заключается в сокращении базового случая, также известном как рекурсия на расстоянии вытянутой руки . В этом случае, приведет ли следующий шаг к базовому случаю, проверяется перед вызовом функции, избегая ненужного вызова функции. Например, в дереве вместо повторного перехода к дочернему узлу с последующей проверкой, является ли он нулевым, проверяя нулевое значение перед рекурсивным выполнением. Это полезно для повышения эффективности, когда алгоритм обычно встречается с базовым случаем много раз, как во многих древовидных алгоритмах, но в остальном считается плохим стилем, особенно в академических кругах, из-за дополнительной сложности.
Другим примером гибридных алгоритмов по соображениям производительности являются introsort и introselect , которые объединяют один алгоритм для быстрой средней производительности, используя другой алгоритм, чтобы гарантировать (асимптотически) оптимальную производительность в худшем случае. Introsort начинается с быстрой сортировки , но переключается на сортировку в куче, если быстрая сортировка не продвигается должным образом; аналогично introselect начинается с quickselect , но переключается на медианное значение медианы, если quickselect не продвигается должным образом.
Централизованные распределенные алгоритмы часто можно рассматривать как гибридные алгоритмы, состоящие из отдельного алгоритма (запускаемого на каждом распределенном процессоре) и алгоритма комбинирования (запускаемого на централизованном распределителе) - они соответствуют соответственно запуску всего алгоритма на одном процессоре или запуску все вычисления на распределителе, объединяющие тривиальные результаты (одноэлементный набор данных от каждого процессора). Базовым примером этих алгоритмов являются сортировки распределения , особенно используемые для внешней сортировки , которые разделяют данные на отдельные подмножества, сортируют подмножества, а затем объединяют подмножества в полностью отсортированные данные; примеры включают сортировку по корзине и флэш- сортировку .
Однако в общем случае распределенные алгоритмы не обязательно должны быть гибридными, поскольку отдельные алгоритмы или алгоритмы объединения или связи могут решать разные проблемы. Например, в таких моделях, как MapReduce , этапы Map и Reduce решают разные проблемы и объединяются для решения другой, третьей проблемы.