Привет! Это заметка! Борщ! Тут всё и сразу. Надоело из года в год искать про сортировку информацию. А их разнообразие и вообще.
Так что к сути!
Классический пример алгоритма сортировки сегодня с сравнением, гибридный, алгоритм Тима tim_sort написанный еще в 2002-2003; Он стремитсяк O(n*logn) по эффективности; Против классического полного пребора O(n^2)
Мне кажется логичной идеей разбить по алфавиту и обращаться по ссылке к элементу массива с соответствующими элементами. Получается radix_sort
//Пример: Мы берем n=2^30. Тип: 32 байта.
Казалось логично закидать на постоянный носитель(SSD) по первому символу [0X00..0xFF] и обращаться так. Получается условно из 2^30 элементов. Это ~ 1 000 000 0000.
к слову log(n) в нашем случае это условно 20. Т.е. идеальный перебор предполагает получается всего 20 проходов по массиву.
Дак вот, почему это плохая идея в такой реализации, при условии что таблица в результате нужна одна? Потому что ОЗУ условно в 40 раз быстрее пока еще. Плюс еще и SSD изнашивается. Условная планка ОЗУ 3800 дает 30400мб/сек. Может и в 1,5 раза меньше если это к примеру DDR 2400 Mhz. Для первого значения и нашего n, это условно 1 млрд значений в секунду. Т.е. все. Одна секунда и все значения пройдены( на самом деле каждая строка содержит разные другие значения потому что таблица не нормализована и показатель в 10 раз больше по времени и размеру Есть смысл нормализовать таблицу перед сортировкой, или работать с данными как с отдельными).
Но в целом есть смысл сравнивать. Скорость ОЗУ и доступа к SSD(HDD не рассматриваю).
вернемся к алгоритму.
вижу два прохода ssd. что экономит запись на ценный невосполнимый ресурс. первый прогон и второй паралельное объединение кусков. можно в начале 3ий проход, который будет счетчиком частот для Mapping. т.е. три прохода.
Поэтому есть смысл СРАЗУ делать сортировку по мере прохода, кусками. Но вот эти куски возможно есть смысл провести над ними разбиение по алфавиту в массив, желательно в одном файле(?) со смещением. //radix первого элемента.
почему? Потому что 20 проходов tim_sort и иные.
radix
максимально 30 бинарного разбиения для нашего n - 8 на символ(256 вариантов) + 1 на него самого = 23 вариантов.
шаг 2 - 15 бинарного разбиения осталось
шаг 3 - 8 бинарного разбиения. Это 256 условно. Элементов.
Шаг 4. после шага 2-3 в нашем случае, сортируем остаток. предполагается какие то отклонения равномерности.
Получаем в полном варианте: 3 шага + например tim_sort.
3*n + [ 2^8*ln(2^8) * (n/(2^8)) ]= 3 221 225 472 + 5 954 088 943 = ~9B переборов.
Тут надо понять последний шаг будет сортироваться в памяти процессора целиком кэш L2-L3 процессора, а он в свою очередь быстрее Оперативной памяти; В целом надо стараться сортировать на памяти более близкой к процессору.
Условно если допустим L3 в 2 раза быстрее. То в скорости будет не ~9B, а условно 3.2B + 6B/2 = абстрактных 6.2B переборов(во времени). Поэтому это очередное преимущество голого списка, без дополнительных данных в сортируемой таблице/списке - возможность обратиться к L2-L3 кэшу. Если оптимизировать это все дальше.
Если был просто n*log(n) ~ 20B.
В нашем случае переборов 9B.
Т.е. в 2-3 раза быстрее. В идеальном случае полного распределения о котором мы предполагаем, что знаем, будет O(n).
Устанавливайте правильное ПО.
У меня сейчас СУБД MySQL версии аж 5.5! Тут рек.lama перехода к бесплатному Sphinx, или иного предназначенного для этого инструмента. Оптимизированного под такие запросы.
Эффективность без танцев с бубнами(точнее они сразу будут в виде психологического перехода довольно простого и адаптации).
Условно у меня сейчас сортируются данные на MySQL со скоростью 1000 значений, на Sphinx будет условно 10000 значений секунда [ссылка*]
Опять же MySQL сам по себе оптимизруется через my.ini [ссылка*]
Используйте качественное оборудование с умом.
Начнем с того что использовать стоит не обычные SSD, а M.2 NVME. Поскольку пинг меньше между запросами, IOPS выше и т.д.
Вообще можно самостоятельно разносить по банкам памяти SSD, можно сделать RAID массив. И каждому обращаться отдельным ядром процессора паралельно.
Можно использовать все возможности видеокарты. Тогда в помощь Intel Cuda сортировка алгоритмы.
Мораль: сортируйте списки да хоть той же сотировкой Тима.
* а вот тут рекомендуется Radix sort(lsd), RadixIns sort(msd) и имеется таблица с тестами [https://habr.com/ru/post/335920/]
- поразрядная сортировка разобрана/Radix. Мануал, очень подробно с алгоритмом [https://algolist.manual.ru/sort/radix_sort.php]
- тут сравнение скорости полнотекстового поиска на разных СУБД движках. Немного иное, но внизу таблица отлично показывающая разность в скоростях разных движков по данному фактору [http://lib.custis.ru/Сравнение_движков_полнотекстового_поиска]
- тут конкретно radix_sort_lsd(оптимизированный radix). Алгоритм. 32 байтные слова в примере сортируют. [Сразу тыкай сюда][https://habr.com/ru/post/484224/], а тут Часть 2: [https://habr.com/ru/post/533206/] додуманная и L2,L3 кэш и видеокарта. Сортировка 10^8 значений, занимает 0.25 сек. 3200мб/0.25сек. Сравнимо со скоростью SSD получается. Еще ведь расходы на склейку.
Просто не хочется сортировать по 10 дней то, что должно сортироваться бы за максимум 15 минут и быстрее. Счастья.