Карта сайта Kansoftware
НОВОСТИУСЛУГИРЕШЕНИЯКОНТАКТЫ
Разработка программного обеспечения

Hybrid Radix

Boost , Boost.Sort , Rationale

Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Существует два основных типа сортировки на основе радикса:

Сортировка Radix (MSD) делит данные рекурсивно на основе самых несортированных битов. Этот подход эффективен даже для распределений, которые хорошо делятся и могут быть выполнены на месте (используется ограниченная дополнительная память). Для каждой итерации существуют значительные постоянные накладные расходы для работы с расщепляющейся структурой. Алгоритмы, представленные здесь, используют MSD Radix Sort для сортировки по радиксу. Основным недостатком сортировки MSD Radix является то, что, когда данные разрезаются на мелкие кусочки, накладные расходы на дополнительные рекурсивные вызовы начинают доминировать во время выполнения, и это делает поведение в худшем случае существенно хуже, чем & #119926; (N*log(N)).

В противоположность этому, integer_sort, float_sort и string_sort проверяют, имеет ли сортировка на основе Radix лучшее время выполнения в худшем случае, и делают соответствующий рекурсивный вызов. Поскольку алгоритмы сортировки, основанные на сопоставлении, эффективны на небольших кусочках, тенденция MSD радикс-сорта к уменьшению проблемы до малого превращается в преимущество этими гибридными типами. Трудно представить общий случай использования, когда чистый MSD радикс будет иметь какое-либо существенное преимущество перед гибридными алгоритмами.

Наименее значимый сорт radix (LSD) основан на наименее значимых битах. Для этого требуется полная копия сортируемых данных с использованием дополнительной памяти. Основным преимуществом LSD Radix Sort является то, что помимо некоторых постоянных накладных расходов и распределения памяти, он использует фиксированное количество времени для сортировки каждого элемента, независимо от распределения или размера списка. Это количество времени пропорционально длине радикса. Другим преимуществом LSD Radix Sort является то, что это стабильный алгоритм сортировки, поэтому элементы с тем же ключом сохранят свой первоначальный порядок.

Одним из недостатков является то, что LSD Radix Sort использует то же количество времени для сортировки «легких» проблем сортировки, что и «жесткие» проблемы сортировки, и это время может оказаться больше, чем эффективный алгоритм 𝑶(N*log(N)), такой как introsort, тратит сортировку «жестких» проблем на большие наборы данных, в зависимости от длины типа данных и относительной скорости сравнений, распределения памяти и случайного доступа.

Другим основным недостатком LSD Radix Sort является накладные расходы на память. Это только быстрее для больших наборов данных, но большие наборы данных используют значительную память, которую LSD Radix Sort должен дублировать. ЛСД Радик Сортировка не имеет смысла для элементов переменной длины, таких как строки; она может быть реализована, начиная с конца самого длинного элемента, но будет чрезвычайно неэффективной.

Тем не менее, есть места, где LSD Radix Sort является подходящим и быстрым решением, поэтому было бы целесообразно создать шаблонный LSD Radix Sort, похожий на integer_sort и float_sort. Это было бы наиболее уместно в тех случаях, когда сравнение происходит крайне медленно.


PrevUpHomeNext

Статья Hybrid Radix раздела Boost.Sort Rationale может быть полезна для разработчиков на c++ и boost.




Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.



:: Главная :: Rationale ::


реклама


©KANSoftWare (разработка программного обеспечения, создание программ, создание интерактивных сайтов), 2007
Top.Mail.Ru

Время компиляции файла: 2024-08-30 11:47:00
2025-07-04 22:21:57/0.0049858093261719/0