Друзья, по комментариям я понимаю, что вы если и прочитали статью, то не поняли посыл:
1) Я говорю об этом методе не как о боевом продакшн решении, а как об интересном и комфортном академическом методе, который лично мне не попадался ни в литературе, ни в виде учебных материалов, хотя он куда интереснее остальных методов, потому что есть своя изюминка, в каком-то смысле это альтернативный подход к решению;
2) Я в статье обозначил рамки применения метода и в конце даже указал на явные недостатки, а значит я прекрасно понимаю с чем работаю.
Введение в историю
Прошу без излишних эмоций реагировать на провокационное утверждение про игнорирование сортировки подсчётом всеми-всеми, ибо я не истина в последней инстанции, я не учился со всех возможных ВУЗах мира, поэтому я сужу только о себе и том, с чем мне приходилось сталкиваться. А заголовок чууутельку кликбейтный, да простит меня Интернет.
Теорию и технологию программирования я изучал в 90-е в провинциальном ВУЗе, но с весьма неплохим преподавателем, но даже от него я о таком способе сортировки не слышал. Не читал я о нём ни разу до, внимание!!! - 12 апреля 2022 года. Вот таким конём в вакууме я был. И самое интересное, что 12 апреля, как Юрий Гагарин, я "первым" для себя изобрёл этот тип сортировки. Занимался как всегда кодированием информации, сейчас балуюсь со словарями и их представлениями и мне понадобился простой (и быстрый) способ сортировки латинских букв - сиречь байтов.
Так как программирование для меня тема хоббийная, то я с определенной регулярностью что-то изобретаю и вопя "Эврика!" лечу в Интернет проверять. 20-25 лет назад, когда такое случилось впервые, находить что-то было весьма сложно, так как статьи были в основном на неправоверном инглише, поэтому статусом великого изобретателя я себя тешил иногда месяцами. Сейчас же поиск уже давно открытого занимает пару часов (если не минут).
Мне нужно было очень быстро получать из, например, ATLAS слово AALST, так же сортировать целиком файлы "книг". И поскольку байты - мой основной тип данных, то сортировка подсчётом отлично ложилась в основные концепции моих исследований. В частности программа вычисления энтропии файлов, написанная еще в 2020 году, уже пользовалась кодом по подсчёту задействованных байт, так что ядро мысли уже крутилось как волчок в моей голове. И когда я пару недель назад взялся (опять) за словари, то было уже делом времени - когда же волчок превратится в сверхновую.
На просторах интернета - и на Хабре и в Ютубе, по сортировке подсчётом информации весьма мало. С одной стороны там и рассказывать нечего, с другой - дурацкий пузырьковый метод описывают раз за разом, хотя он не несёт никакой практической пользы, он чисто академический и предназначен для демонстрации основного эффекта сортировки.
Реализация
Так как я перешёл на C# с Delphi, то код я дам именно на шарпе. Вот как раз обновился до 2022 студии и ринулся в бой. Скобочки везде оставил для комфортного чтения например новичками:
public static void beSort()
{
byte[] sorted = File.ReadAllBytes(".\filename.txt");
int[] map = new int[256];
for (int i = 0; i < sorted.Length; i++)
{
map[sorted[i]]++;
}
int pos = 0;
for (byte i = 0; i <= 255; i++)
{
if (map[i] > 0)
{
for (var x = pos; x < pos + map[i]; x++)
{
sorted[x] = i;
}
pos += map[i];
}
if (i == 255) break;
}
File.WriteAllBytes("file_beSort.txt", sorted);
}Я не занимался никакими оптимизациями (напишите если там можно что-то улучшить) и сам код прямой как лом, но текущая производительность вполне устраивает, а вам будет во что меня ткнуть носом, всё же пусть красиво и быстро будет бонусом и подарком от специалистов в своём деле.
Чтобы было с чем сравнивать, я взял встроенную сортировку Array.Sort и выполнил работу в ней:
public static void ArraySort()
{
byte[] sorted = File.ReadAllBytes(listfiles[0]);
Array.Sort(sorted);
File.WriteAllBytes("file_ArraySort.txt", sorted);
}Время работы 33 миллисекунды.
Идея сортировки подсчётом
1) Один раз проходим по данным и считаем число вхождений каждого байта, за счёт того что байт может содержать значения от 0 до 255 мы заранее можем создать массив map[256] и в качестве индекса счётчика использовать само значение в массиве байт, в коде это
map[sorted[i]]++;2) Так как исходный массив нам уже не нужен, то используем его для формирование сортированного массива
3) В цикле отсеиваем все значения map[] равные нулю - это байты, которые в файле не представлены
4) Запускаем цикл заполнения массива значением нужного байта i в количестве равном ранее подсчитанному значению из map[i], индексом положения указателя для записи данных используем временную переменную pos, которую всегда после заполнения части массива увеличиваем на значение из msp[i], то есть сколько байт записали, на столько и сдвинуть указатель
Скорость просто сногсшибательная. Тестировал на английской "20000 лье под водой" (20000 Leagues Under the Sea.txt) размером в 841313 байт. Время считал встроенными средствами
Stopwatch sw = new Stopwatch();что вылилось в 1 миллисекунду.
До заключения
Можно изменить код убрав if - следящий за границей байт на преобразование int в byte вот так:
for (int i = 0; i <= 255; i++)
{
if (map[i] > 0)
{
for (var x = pos; x < pos + map[i]; x++)
{
sorted[x] = (byte)i;
}
pos += map[i];
}
//if (i == 255) break;
}На результате это не сказывается:
C:\fc /b file_beSort.txt file_beSort_good_1ms.txt
Сравнение файлов file_beSort.txt и FILE_BESORT_GOOD_1MS.TXT
FC: различия не найдены
Пузырьком тот же файл сортировался 663 ТЫСЯЧИ миллисекунд.
Заключение
Не стал обсуждать аспект сортировки небольших данных, например я в начале упомянул сортировку отдельных слов. Там появляется мысль - не гонять для подсчёта все 256 возможных элементов массива map[], а сделать динамическую структуру, которая индексируется по ключу и расширяется по мере появления новых значений.
Лично я в таких ситуациях прибегаю к помощи Dictionary, но возможно у кого-то будет какая-то интересная идея на этот счёт. С удовольствием ознакомлюсь, а пока буду пользоваться прямым индексированием 256 элементов.
Логичным ограничением применения метода является использование таких типов данных, которые невозможно привести к байту. Например у вас в базе данных 10 миллионов записей вещественных чисел или большие целые числа например 32 или 64 битной разрядности.
Позволил себе метод назвать как beSort(), префикс - это мои инициалы и я ими пользуюсь при написании софта, пусть в сети остаётся след от моих безумств.
Спасибо всем дочитавшим до конца.
PS: в поиске картинки для публикации наткнулся на другое определение сортировки подсчётом - производится подсчёт количества раз, когда значение последовательности больше (или меньше) остальных значений. Это полностью отличается от того что написал я. Предлагаю разобраться вместе.
Комментарии (19)
randomsimplenumber
13.04.2022 11:07+1Сортировать long int не хватит никакой памяти ;)
DimPal
13.04.2022 15:00Ранжируем сначала по старшим битам (например разбив по 8 бит), а затем рекурсивно каждый интервал.
randomsimplenumber
13.04.2022 15:56+1Например?
Есть у нас shortint:
0000, 0001,0100,0101
После прохода счётчика по старшим байтам
Counters[] = {2,2}
Как восстановить интервал для рекурсивной сортировки?
DimPal
14.04.2022 15:26Для объяснения по вашему же примеру лучше разбить по два бита. Если для решения задачи использовать связанные списки, то выделяем дополнительный массив (размером с входной массив) в нем мы храним индекс следующего элемента (или -1 если конец списка). В индекс-массиве из 4 элементов храним первые элементы списка. После первого прохода получаем такое [[0, 1],[-1],[1,2],[-1]]. Каждый подсписок сортируем рекурсивно. Собственно radix-sort позволяет перебирать группы бит как от старших к младшим, так и от младших к старшим, там не принципиально получается.
wataru
13.04.2022 16:56+2Вот вы и изобрели radix sort. Правда хитрость в том, чтобы не сортировать интервалы рекурсивно, а сортировать сначала по младшим битам, потом по средним и в конце — по старшим. Если один этап сортировки сделать стабильным (что очень просто), то в итоге данные будут отсортированны правильно.
pda0
13.04.2022 16:24Если по всему диапазону — да, если разумное конечное подмножество, то можно. Вместо массива используем хеш-таблицу. Правда придётся ещё решить задачу её итерации по возрастанию ключей. Так что алгоритм подсчёта более универсален.
Druj
13.04.2022 16:35Скорее всего человек думал в сторону битового бора, эта структура очень похожа на поразрядный подсчёт битов и, да, действительно позволяет сортировать чиселки почти за O(N), а при правильной реализации памяти требует меньше чем аналогичные структуры
vadimr
13.04.2022 11:15+1В сортировках вообще можно очень большого прогресса добиться в отдельных частных случаях.
Ваш метод экспоненциально зависит по используемой памяти от длины ключа и эффективен по времени только в том случае, когда ключи плотно заполняют множество своих возможных значений. Если у вас дело сведётся к поиску нескольких единичек среди миллиардов и триллионов нулей, то пузырьковая сортировка будет эффективней.
Akon32
13.04.2022 11:42+2Не читал я о нём ни разу до, внимание!!! - 12 апреля 2022 года. Вот таким конём в вакууме я был.
С подключением!
Сортировка подсчётом годится только для значений, которые можно генерировать, и типы которых характеризуются небольшими кардинальными числами (это число значений типа). Числа типа int8,int16, с натяжкой int32 ещё подходят под это ограничение, но произвольные объекты, типа строк или записей в БД - нет.
Вычислительная сложность сортировки подсчётом O(N), а у продвинутых гибридных методов наподобие TimSort - те же O(N) в некоторой доле случаев (O(N logN) в общем случае). Зачастую разница невелика, поэтому сортировка подсчётом используется крайне редко. Я не видел эту сортировку в стандартных библиотеках, да и на практике за много лет применять её мне не приходилось.
AndrChm
13.04.2022 19:48-1Пузырьковая сортировка имеет асимптотическую оценку сложности O(N^2). Самые быстрые алгоритмы сортировки, HeapSort например (сортировка на бинарных деревьях), имеют асимптотическую сложность O(NlogN). Это означает, что все они полиномиальны по сложности. Есть алгоритмы, которые предполагают сортировку отдельных массивов данных с их последующим слиянием. Алгоритм, который Вы рассматриваете, при небольшом массиве сортируемых данных может потребовать очень большой памяти. Если на примере чисел, то всё зависит от того, из какого диапазоне выбираются эти числа.
randomsimplenumber
14.04.2022 07:18Всё равно непонятно, зачем у статьи минус. Да, это велосипед. Да, пригоден только в частном случае. Но для частного случая подходит идеально, и честно изобретён.
BellaLugoshi Автор
15.04.2022 06:33randomsimplenumber, спасибо за объективный взгляд на статью. Мне кажется вы верно уловили мою мысль.
Druj, не согласен что это сжатие/восстановление, иначе таким макаром можно ASCII таблицу назвать способом сжатия любого текстового файла. Так как этот метод сортировки имеет явные ограничения, то никакой магии тут нет. Вы же не пытаетесь обвинять пузырьковый метод несостоятельным например на 1Тб данных? Мои идеи схожи с тем как работают архиваторы и вот в чём - разные алгоритмы дают разный результат по соотношению скорость/степень сжатия, что приводит к тому, что указывая ключ "-mX" например от 0 до 5 вы выбираете алгоритм сжатия, а не вариацию какого-то одного алгоритма. Например у Мэтью Махони в zpaq это выглядит так:
Method Compress Decompress Algorithm1 128 MB 32 MB LZ77
2 450 MB 128 MB LZ77
3 450 MB 400 MB LZ77+CM or BWT
4 550 MB 550 MB LZ77+CM, BWT or CM
5 850 MB 850 MB CMИ очевидно что на разных данных методы 4 и 5 могут делить между собой первенство. Или так - выбор метода неразрывно связан с типом данных, а не со степенью сжатия. Простой пример - создаю файл в 1 мегабайт с рандомным расположением всего двух разных символов "≈с≈≈с≈сссс≈≈≈" (и так 1 Мб). Пакуем zpaq с ключами -m4 и -m5, в итоге 4 метод - файл 4.8 Кб, а пятый - 7.3 Кб. Разговоры в духе "мало кому нужно" не имеют смысла, так как при изучении методов и алгоритмов мы изучаем почти всё до чего можем дотянуться и моё умеренное негодование как раз и вызвано тем, что такой способ никак не представлен, по крайней мере широко, как тот же пузырьковый, хотя именно решение частных задач в определённых контекстах может происходить совершенно разными способами.
vadimr, не проверял, может чуть позже и проверю, например на миллиарде это не составит труда сделать, но на мой взгляд линейное масштабирование этого метода приведёт и к линейному росту сложности. А так как в "моём" методе нет никаких сравнений, то по сути он отработает как O(n), а пузырьковому как минимум потребуется O(2n) даже всего на одной единице среди миллиарда нулей.
Akon32, я не вижу как этот метод может быть хуже того же пузырькового, например в виде статьи в учебнике или в виде примера на Википедии с данными - "0,7,4,6,6,3,32,5,63,3,4,6,6,4,3,5,6,6,4,3,2", и так же никому не помешает в описании плюсов и минусов указать всё что вы написали, наравне с такими же данными для любого другого метода. Я же не предлагаю всё бросить, переписать все библиотеки во всех языках и начать пользоваться этим способом. Но как минимум я, работая с текстовыми файлами и словарями вижу для себя огромный буст от такого метода, потому что впереди у меня задача по сбору статистики по некогда выгруженной библиотеки Машкова, это текстовых файлов на 700 Мб в виде архивов. И я совсем не хочу чтобы прогон тестов на таких объемах упирался в сортировку. Мне и кроме неё много чего делать нужно будет. Поэтому я в этом методе вижу отличное логическое продолжение своей первой статьи, хороший академический метод (поверьте, из тех кто читал описание TimSort весьма мало тех кто реально понимает что там происходит), вы же понимаете что сортировку пузырьком и подсчётом можно объяснить даже школьникам. Я сам всегда что-то сортировал стандартными либами, это просто и удобно, но изобретение чего-либо - это процесс творческий и часто весьма далёк от практического применения, например двигатель Стёрлинга изобрели 200 лет назад, но практически мало используют из-за массы ограничений, при этом само изобретение просто шедевральное и простое.
Резюмируя свой опус скажу, что в первую очередь я предлагаю этот метод к рассмотрению как учебный - безумно простой в реализации. Во вторую - как метод при работе с конкретными данными, как в моём случае с текстом. В третью очередь - это просто интересная разминка для мозга, так как ещё нужна реализация с динамическим массивом
map[]для коротких массивов - зачем плодить сущность в256*sizeof(item)если нужно отсортировать слово длиной в 8 байт? Нужна реализация дляString, которая в C# должна минимизировать количество операций со строками. Возможно всё это имеет смысл оформить уже второй частью статьи.В любом случае спасибо всем за обсуждение.
AndrChm
15.04.2022 12:54пузырьковому как минимум потребуется O(2n) даже всего на одной единице среди миллиарда
Асимптотическая сложность сортировки методом «пузырька» — O(N^2). На всякий случай ещё и напишу: N в квадрате, где N — мощность сортируемого массива данных (количество объектов в нём). Кстати, оценка O(2N) смысла не имеет. Поскольку символ Бахмана так устроен, что учитывает мульпликативные константы, которые могут отличаться для различных реализаций алгоритма, зависеть, например, от платформы и пр.
AndrChm
15.04.2022 14:29Ваш алгоритм сортировки, как я его понимаю, поправьте если что не так, устроен следующим образом. Пусть имеется
объектов, которые необходимо отсортировать в порядке неубывания. Например, это могут быть записи в базе данных. Сортировка осуществляется по ключу, а именно по содержимому некоторого позиционно фиксированного поля в пределах каждой записи и это поле всегда существует. Пусть ключ — это натуральное число. Отмечу, что алгоритм обобщается на целые числа. Ключ принимает значение из диапазона 
. Заранее величины ключа не известны и можно исходить только из минимально и максимального значений указанного диапазона. Это означает, что необходимо зарезервировать 
бит памяти. Назовём ячейкой отдельную порцию 
бит. Тогда для сортировки нам понадобится 
ячеек памяти с прямым доступом и значение ключа — это относительный адрес некоторой ячейки. Для начала мы выполняем подготовительную операцию обнуления — заносим в каждую ячейку значение 0. Затем приступаем непосредственно к сортировке: 1) считываем значение ключа из записи; 2) используем это значение для перехода к нужной ячейке (смещением относительно базового адреса) и увеличиваем её значение на 1 (это счётчик вхождений). Когда все ключи обработаны, нам надо получить результат сортировки. Для этого мы проверяем значение каждой ячейки и формируем отдельный список, в котором напротив значения ключа располагается значение счётчика. Дело сделано. Понятно, что асимптотическая сложность такой сортировки не 
, а 
. При этом, очевидно, что в худшем случае
Если 
— это некоторая экспонента, то асимптотическая сложность такого алгоритма сортировки перестаёт быть полиномиальной.
SharUpOff
15.04.2022 11:45Полагаю, что минусуют Вас в большей степени за тот самый провокационный заголовок. Мотивация привлечь читателя любой ценой объективно понятна, однако такие методы могут вызывать естественное раздражение :) Лично меня статья вместе с комментариями к ней сподвигла освежить в памяти разные методы сортировки, оставив смешанные чувства: отрицательные от финта с заголовком и положительные от содержания самой статьи.
Druj
Не используют потому что формально это не совсем сортировка, скорее метод сжатия/восстановления. Посудите сами, «сортируя» таким способом вы генерируете из 256-и интов последовательность длиной до 256 * 2^32 байтов что похоже на магию. В реальной практике мало где нужна сортировка последовательности примитивных чисел, обычно требуют сортировку по определенному обьекту или результату функции от это этого обьекта, в этом случае метод подсчёта пролетает мимо так как исходный обьекты по их позиции вы восстановить не сможете.
Deosis
Сортировку подсчетом можно модифицировать, чтобы она сортировала исходные данные по некоторому ключу.
Другое дело, что такой ключ очень редко будет иметь значения, для сортироваки подсчетом.
Druj
Это уже будет частным случаем bucket sort, а там другие показатели памяти и промахи кэша.