Уважаемые читатели, в своей разработческой деятельности я люблю творчески рассуждать за пределами общепринятых рамок, ограничений, постулатов, мнений влиятельных экспертов и т. п., пытаясь рассуждать как можно шире, заглядывать за «горизонт». Увлечение такое. Не только на работе (там, конечно, приходится считаться с ограничениями — с дисциплиной и самодисциплиной у меня всё в порядке ещё с армии), но особенно в личное время, где полёт мысли ничто не сдерживает. Хотя и на работе эти мои творческие особенности иногда позволяли продуцировать весьма эффективные решения, было такое и не раз. Но описываемое явление скреативилось в личное время.
Кто-то в личное время покоряет Эверест, кто-то стрит-драйвит, кто-то на нижней Волге ловит спиннингом судаков и жерехов (я тоже, кстати, раз в году), кто-то разводит мадагаскарских шипящих тараканов, а кто-то развлекает себя эзотерикой. А я вот внерабочее время развлекаю себя тем, что напрягаю свой мозг математическими и алгоритмическими проблемами. Придумываю что-нибудь эдакое, необычное. Жаль, что за эту деятельность не платят. Говорят, такое напряжение мозга поможет в старости спастись от болезни Альцгеймера. Во всяком случае, весьма на это надеюсь.
И, рассуждая совсем о другой проблеме, но где имеет место быть сортировка большого количества объектов, в плане алгоритма сортировки объектов, меня осенило. Быстренько проверил кодом — ого, работает! Рассчитываю, что вам понравится.
Упорядочиваем чёрную кассу
Начнем с наглядного абстрактного примера:
У нас в кучке хаотично лежат монетки межгалактических грошей разного достоинства: 5, 15, 1, 10, 3, 25, 2. Задача — отсортировать их по достоинству.
Заготавливаем место под сортированные монетки — линию с метками от 1 до 25. Берём каждую монетку и по её достоинству помещаем в линию на место с меткой, соответствующей достоинству. После того как мы проделали это со всеми монетками, в линии у нас будут лежать монетки в отсортированном виде: 1, 2, 3, 5, 10, 15, 25 грошей.
И мы это сделали за один проход, что означает вычислительную сложность O(n). А если монетки перемещает многорукая Шива одновременно все, то эта сортировка ещё и хорошо распараллеливается.
Волшебство? Нет. Этот алгоритм сортировки был известен ещё в древности, он наглядно описан в книге Дональда Кнута «Искусство программирования», в 3-м томе «Сортировка и поиск» под названием «Сортировка распределением». Только там был пример с игральными картами. Межгалактические гроши во время написания книги ещё не были известны:)
Но почему этот алгоритм не используется в распространённых библиотеках, а используются алгоритмы со сложностью O(n log n): QuickSort, сортировка слиянием, пирамидальная сортировка..?
Всё дело в универсальности. Библиотечные алгоритмы требуют от сортируемых объектов только одного свойства — сравнения с другим таким же: больше, равно, меньше.
Но если мы об объекте сортировки знаем больше, то, выйдя за пределы парадигмы универсальности, открываются новые горизонты для творческого полёта мысли, и становится возможным применять линейные или специализированные алгоритмы. В примере с монетками мы знаем их мерную характеристику — достоинство монетки, а также пределы этой меры: минимально 1 и максимально 25. Что и позволило нам так эффективно отсортировать их.
Вот бы такое применить для программно сортируемых списков объектов?
Берём быка за рога
Давайте подумаем, какие объекты обладают мерными характеристиками? Большинство!
Числа — обладают, и пределы их известны для разных типов данных.
Даты — обладают.
Все объекты с весовыми, объемными или стоимостными характеристиками.
А как же строки?
А вот здесь придётся немножко поразмышлять,
как натянуть сову на глобускак наиболее эффективно (применительно к задаче) набор символов превратить в мерную характеристику с известными предельными значениями.
Вариантов превращения наборов символов в числа более чем достаточно, надо только подобрать наиболее подходящий под конкретные условия с учётом необходимых правил сортировки строки.
Начну сразу с достигнутого результата, чтобы дальше читалось нескучно. На скорую руку собрана программа, сортирующая строки тремя способами: встроенным библиотечным алгоритмом, предлагаемым алгоритмом и предлагаемым алгоритмом с добавленным распараллеливанием. Вот результаты (объяснение обязательно будет ниже):
В примере сгенерировано 100 млн строк стопроцентной хаотичности.
Вот такого вида:
MNgm5xRHTC5ixtgqFnOxPPUYYGnalyzVzgpwyRPO3gL
sApqeZzDWmLnZQFX
EkApnzSqcirxq0Fn5nhig8VaQ+bDd+g
qCz+ljE56yAf/nB1oEEOkhmdXiqZa2d22TqtesnBkH4hmwv+pD5xfoVQNG0lwOQFD
26wP1+FqY9jgEVQkweKu3hKz3nFf76C+Wa7FCuZa/MhtWl0xO7RUI0U479kWYrQpq5MnwTtQxD6B9NJc1FpxJ2PyMz8avRJZ4e3fksJgwKI6R
c3hfDPgZPmR
s70f8qO1vYAA52oLTXFSfNL82inz2gqcyveT39WCpijtaIt06fLpz6TzxbJ
yYf6rtNeOiIchM+GmId2OR8S0SIYCCujDUjSWlBpMhZ1f1R7AF
nUw+RPZE9X+/ehQIA29p0vPmPsC3R9hL7Wv8
Далее для сравнения список сортируется встроенным сортировщиком (в .NET метод Array.Sort()), где на таком объёме работает алгоритм «Пирамидальная сортировка» (а на меньшем объёме — QuickSort) (алгоритмы со сложностью O(n log n)). Как мы видим, встроенная сортировка справилась за 5 минут.
Следом идёт сортировка преобразованным линейным алгоритмом «Сортировка распределением» в гибридный. Преобразование заключается в адаптации мерности объектов в заготовленные места для распределения и досортировке объектов, попавших на одинаковые места. Рабочее название такого гибридного алгоритма — «Сортировка индексацией ранжирования».
И здесь мы видим феноменально меньшее время сортировки — в разы! И это всего лишь в сыром примере, написанном за пару вечеров, буквально «на коленке». Представьте, какую производительность можно достичь, если хорошо проработать код под заданные условия и использовать на мощных многопроцессорных серверах.
А вот третий случай — это когда к сортировке «Индексацией Ранжирования» добавлено распараллеливание. Результат, хоть и улучшился, но, однако, меня удручает. Ожидал большего. Возможно, дело в однопроцессорном домашнем PC, а на серверах с 96 процессорами это будет выглядеть бодрее и веселее.
Для каждого этапа сортировки исходный сгенерированный несортированный список случайных строк копируется в свой отдельный список для сортировки. Таким образом, исходные условия для каждой сортировки идентичны.
У гибридного алгоритма «Индексацией Ранжирования» есть достоинства и недостатки.
Достоинства | Недостатки |
Высокая производительность на больших объёмах. | Не универсален. Пригоден только для объектов, имеющих мерность, по которой нужно сортировать, и известные либо заданные пределы мерности. |
Позволяет учитывать особенности объектов для достижения минимального времени сортировки. | На малых объёмах уступает библиотечным алгоритмам по времени из-за накладных расходов. Из полученной практики — нецелесообразно применять этот алгоритм при количестве сортируемых объектов менее 100 тысяч. |
Допускает распараллеливание и масштабируемость по процессорам. | Для списков с частично или полностью отсортированными объектами требуется доработка алгоритма, ибо это пока не учтено, и производительность на таких списках страдает. Но это исправимый недостаток — ещё есть над чем поработать. |
Масштабируемость по оперативной памяти. Чем больше памяти можно выделить под сортировку, тем быстрее она произойдет. |
Таким образом, применимость данного алгоритма — это случаи, когда необходимо наиболее эффективно отсортировать огромное количество объектов заранее известного типа. Например, в СУБД, где все объекты — это кортежи значений заранее известных типов с понятными мерными свойствами.
Оцените перспективу — СУБД вашей разработки выполняет
ORDER BYна огромной выборке на порядок быстрее конкурирующих СУБД! Разумеется, если не поскупиться пригласить меня возглавить разработку реализации:)
Сравнительные результаты в секундах:
Количество строк | Встроенная сортировка в NET 9 - Array.Sort() со сложностью O(n log n) | Сортировка «Индексацией Ранжирования» | Сортировка «Индексацией Ранжирования» с распараллеливанием |
100’000 | 0.126 | 0.037 | 0.022 |
1’000’000 | 1.540 | 0.731 | 1.500 |
10’000’000 | 20.608 | 7.273 | 5.848 |
20’000’000 | 46.415 | 13.695 | 10.193 |
50’000’000 | 134.396 | 29.895 | 19.756 |
100’000’000 | 312.317 | 54.251 | 32.640 |
Можно увидеть, что в диапазоне от 1 млн до 100 млн строк алгоритм «Индексацией Ранжирования» фактически работает тем быстрее, чем больше сортируемых строк (время делится на количество строк). Но эта магия обусловлена удачным выбором размера буфера под сортировку для данного диапазона, а также Меркурием в ретрограде, как авторитетно утверждают астрологи. Другого объяснения не нахожу (пока ещё). Однако выведенную в заголовок сложность O(n) — отрицать сложно.
Факты говорят за себя.
Больше 100 млн строк не удалось сгенерировать — не хватает памяти на обычном домашнем компьютере, а другого под боком нет, чтобы можно было провести масштабные исследования для усовершенствования реализации алгоритма. Но, согласитесь, даже эти результаты примерной реализации алгоритма, собранной на скорую руку, впечатляют.
Генератор строк, кстати, выдернут из моей предыдущей статьи (ссылка ниже). Теперь всем становится понятно, почему я не уделил ему достаточно внимания и он встретил столько критики.
Описание алгоритма сортировки «Индексацией Ранжирования»
№1. Определяем мерность сортируемых объектов, и её границы. Для строк — соответственно для требуемых правил сортировки (регистрочувствительность, акценточувствительность, порядок спецсимволов и знаков препинания) — определяем правила перевода начальных символов в числовые данные. Эти же правила понадобятся на шаге 7.
№2. Выделяем массив, размер которого мы можем себе позволить в данных условиях. Чем больше массив, тем быстрее сортировка. Для примера, результаты которого приведены выше, длина массива составляла 16 777 216.
Элементами массива должны быть динамические списки сортируемых объектов, но при создании массив должен быть пустым. Например, для среды .NET массив должен быть заполнен значениями null, что обеспечивается по умолчанию.
№3. Создаём функцию индексного ранжирования. Входным параметром является мерность объекта, а на выходе — целочисленный индекс в диапазоне значений от 0 до размера массива минус один. Внутри функции вычисляется индекс путём перемасштабирования мерности объекта. Очевидно, и алгоритм это предусматривает, что объекты с близкой мерностью могут вычисляться в одинаковый индекс. Объекты с одинаковыми индексами являются «коллизиями», которые будут решаться отдельным мероприятием.
№4. Проходим по всем объектам из несортированного списка последовательно или параллельно в разных потоках. Для каждого объекта применяем функцию индексного ранжирования. Помещаем объект по вычисленному индексу в массив. При этом:
Если элемент массива пустой, то создается список и помещается как элемент массива по этому индексу.
Объект добавляется в этот список. В этом месте есть возможность оптимизации для частично отсортированных объектов — применить метод с названием «галопирование», когда часть отсортированных объектов копируется сразу списком.
№5. Таким образом, в итоге у нас массив списков, где часть элементов пустые. Списки при этом не сортированные, но при этом короткие, в норме — по несколько объектов-«коллизий», если размер массива достаточен. Чем больше будет выбран массив, тем короче будут эти списки, вплоть до единичных, без коллизий.
№6. В параллельных потоках каждый список коллизий сортируется любым простым алгоритмом сортировки. Поскольку в норме (в случае эффективной реализации алгоритма) в каждом списке всего несколько «коллизий», то рекомендуется алгоритм сортировки вставкой, дающий наилучшее время на маленьких списках.
№7. По порядку элементов (а каждый элемент это уже отсортированный список) из массива, пропуская пустые элементы, все элементы-списки копируются пакетами в итоговый список объектов, который и является результатом сортировки.
Пример программы реализации алгоритма
Как уже упоминалось, программа собрана на скорую руку, поэтому глубокий критический разбор её не предполагается. Конечно, если покорпеть подольше, можно сделать гораздо эффективнее. Но цель была — продемонстрировать алгоритм примером, и эта цель достигнута.
Скрытый текст
/* =======================================================================================
Пример-иллюстрация реализации алгорима сортировки Индексацией Ранжирования
в сравнении со встроеннй сортировкой Arraу.Sort()
Модуль предназначен для компилирования под .NET9 на платформе Windows 10
Среда разработки - Visual Studio 2022
Использовать скомпилированную программу:
IdxRngSort.exe <кол-во строк> [<путь к каталогу сохранения>]
<кол-во строк> - обязательный параметр. Задает кол-во случайно
сгенерированных строк для сортировки.
Рекомендуется от 1 млн до 100 млн
Не задавайте более 100 млн на Home PC, может случиться вылет по памяти
Задавать меньше 100 тыс смысла нет - алгоритм эффективен только на больших объемах
<путь к каталогу сохранения> - необязательный параметр. Если задан,
то в этот каталог сохраняться исходные и сортиртированные данные
Например:
IdxRngSort.exe 100000000 d:\outdir
Данная программа не является каким-то законченным решением,
а является только иллюстрирующим примером реализации алгоритма,
поэтому использование этого кода - на ваш собственный риск.
======================================================================================= */
using System;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading.Tasks;
using System.IO;
using System.Text;
using System.Runtime.CompilerServices;
using System.Threading;
internal static class Program
{
private static void Main(string[] args)
{
(bool result, int cnt, string dir) = ProcessCommand(args);
if (!result)
return;
first_chars = cnt switch
{
<= 10000 => 2,
<= 100000 => 3,
_ => 4,
};
buffer_size = (int)Math.Pow(64, first_chars) + 1;
// генерируем случайные строки
string[] src = RandomStrings2(cnt, dir);
return;
// Сортируем встроенным способом
SortByAlgorithm(src, SortingAlg.Builtin, dir);
// Сортируем сортировкой Индексацией Ранжирования
SortByAlgorithm(src, SortingAlg.IndexingRanges, dir);
// Сортируем сортировкой Индексацией Ранжирования с распараллеливанием
SortByAlgorithm(src, SortingAlg.ParallelIndexingRanges, dir);
Console.WriteLine("\r\nPress a key ...");
Console.ReadKey();
}
// Тип сортировки
private enum SortingAlg : byte
{
Builtin = 1, // Встроенная сортировка Array.Sort()
IndexingRanges = 2, // Сортировка Индексацией Ранжирования
ParallelIndexingRanges = 3 // Сортировка Индексацией Ранжирования с распараллеливанием
}
// Обеспечиванием правила сравнения строк такие же, как во встроенном Array.Sort()
private static readonly Dictionary<char, int> SortRules = GetSortRules();
private static int buffer_size; // размер буфера
private static int first_chars; // кол-во первых символов строк для вычисления индекса ранга. Особенность реализации данного примера. Не является обязательной частью алгоритма
// функция старта сортировки заданным алгоритмом
private static void SortByAlgorithm(string[] src, SortingAlg alg, string dir)
{
GC.Collect();
var lst = new List<string>();
lst.AddRange(src);
string name = alg switch
{
SortingAlg.Builtin => "built-in",
SortingAlg.IndexingRanges => "idx_rng",
SortingAlg.ParallelIndexingRanges => "parallel_idx_rng",
_ => throw new NotImplementedException()
};
Console.Write($"\r\nStarting {name} sorting ... ");
DateTime tml = DateTime.Now;
switch (alg)
{
case SortingAlg.Builtin:
lst.Sort();
break;
case SortingAlg.IndexingRanges:
IdxRngSort(lst);
break;
case SortingAlg.ParallelIndexingRanges:
IdxRngSort(lst, true);
break;
default:
throw new NotImplementedException();
}
Console.WriteLine("done");
Console.WriteLine($"Spent for {name} sorting: {DateTime.Now - tml}");
SaveIf(lst, $"{name}_sorted", dir);
}
// Пример реализации алгоритма сортировки Индексацией Ранжирования, с распараллеливанием и без
private static void IdxRngSort(List<string> list, bool parallel = false)
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void add_str(List<string>[] arr, string str, object[] syncarr = null)
{
int idx = GetRangeIdx(str);
if (syncarr is not null)
Monitor.Enter(syncarr[idx]);
try
{
if (arr[idx] is null)
arr[idx] = [str];
else
arr[idx].Add(str);
}
finally
{
if (syncarr is not null)
Monitor.Exit(syncarr[idx]);
}
}
// тот самый массив (буфер)
List<string>[] arr = new List<string>[buffer_size];
if (parallel)
{
// печально, но нужны объекты синхронизации. Возможно, тут надо придумать что-то более элегантное.
object[] syncarr = new object[arr.Length];
Parallel.For(0, arr.Length, idx => { syncarr[idx] = new(); });
// раскидываем строки в массив, в параллелях
Parallel.ForEach(list, str => add_str(arr, str, syncarr));
}
else
{
// раскидываем строки в массив
list.ForEach(str => add_str(arr, str));
}
// сортируем коллизии
Parallel.ForEach(source: arr.Where(lst => lst is not null && lst.Count > 1), body: lst => lst.Sort()); // согласно хелпа, до 16 элементов работает сортировка вставкой, свыше - QuickSort
list.Clear();
// заполняем итоговый список с отсортированными объектами
// копируем все последовательно, не нарушая сортировки
foreach (var lst in arr)
{
if (lst is not null)
{
// Add работает заметно быстрее чем AddRange, поэтому вставки одиночных объектов и списка разделены
if (lst.Count == 1)
list.Add(lst[0]);
else
list.AddRange(lst);
}
}
}
// функция вычисления индексного ранга ("Ранжирующая функция")
// специфично именно для данного вида строк. Для других объектов нужна другая реализация.
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int GetRangeIdx(string str)
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static bool idx_part(ReadOnlySpan<char> span, int num, ref int range)
{
if (span.Length > num)
{
range += SortRules[span[num]] << ((first_chars - 1 - num) * 6);
return false;
}
return true;
}
int sz = str.Length >= first_chars ? first_chars : str.Length;
ReadOnlySpan<char> span = str.AsSpan(0, sz);
int range = 0;
for (int i = 0; i < first_chars; i++)
{
if (idx_part(span, i, ref range))
break;
}
return range;
}
// заполнение правил сравнения строк. Функция выполняется 1 раз при старте приложения, поэтому можно не беспокоится о производительности
private static Dictionary<char, int> GetSortRules()
{
Dictionary<char, int> dict = new() { { '/', 1 }, { '+', 2 } };
for (char c = '0'; c <= '9'; c++)
{
dict.Add(c, Convert.ToByte(c) - 45); // 48-57 -> 3-12
}
for (char c = 'a'; c <= 'z'; c++)
{
dict.Add(c, Convert.ToByte(c) - 84); // 97-122 -> 13-38
}
for (char c = 'A'; c <= 'Z'; c++)
{
dict.Add(c, Convert.ToByte(c) - 52); // 65-90 -> 13-38
}
return dict;
}
// Генератор случайных строк
// На машине с 32Гб памяти вылетает из-за нехватки памяти, если задать больше 150 млн строк, а вплоть до 150 млн отрабатывает
private static string[] RandomStrings(int count, string dir)
{
Console.Write($"Generating {count} random strings ... ");
DateTime tm = DateTime.Now;
Random rand = Random.Shared;
ConcurrentBag<string> bag = [];
Parallel.ForEach(Enumerable.Range(1, count), num =>
{
string str = Convert.ToBase64String(SHA512.HashData(Guid.NewGuid().ToByteArray()));
bag.Add(str[..(1 + rand.Next(str.Length - 1))]);
});
Console.WriteLine("done");
Console.WriteLine($"Spent for generation: {DateTime.Now - tm}");
SaveIf(bag, "unsorted", dir);
return [.. bag];
}
private static string[] RandomStrings2(int count, string dir)
{
Console.Write($"Generating {count} random strings ... ");
DateTime tm = DateTime.Now;
Random rand = Random.Shared;
string[] arr = new string[count];
byte[] barr = Guid.NewGuid().ToByteArray();
BitConverter.GetBytes(idx);
Parallel.ForEach(Enumerable.Range(0, count), new ParallelOptions() {MaxDegreeOfParallelism = 20000 }, idx =>
{
string str = Convert.ToBase64String(SHA512.HashData(Guid.NewGuid().ToByteArray()));
arr[idx] = str[..(1 + rand.Next(str.Length - 1))];
});
Console.WriteLine("done");
Console.WriteLine($"Spent for generation: {DateTime.Now - tm}");
SaveIf(arr, "unsorted", dir);
return arr;
}
// функция сохранения списка в файл, если задан каталог
// Если было задано 100 млн строк, то файлы будут весить в районе 4 Гб
private static void SaveIf(IEnumerable<string> list, string name, string dir)
{
if (!string.IsNullOrWhiteSpace(dir))
{
Console.Write($"\r\nSaving \"{name}\" ... ");
using StreamWriter sw = new(dir + "\\" + name + ".txt", false, Encoding.Default);
foreach (string str in list)
sw.WriteLine(str);
sw.Flush();
sw.Close();
Console.WriteLine($"done");
}
}
// Обработчик ключей командной строки
private static (bool result, int cnt, string dir) ProcessCommand(string[] args, bool show_header = true)
{
if (show_header)
Console.WriteLine("\r\n Sample of implementation Indexing Ranges Sorting algorithm. \r\n Gleb V. Ufimtsev (C) 2025, Moscow\r\n");
if (args.Length == 0)
{
Console.WriteLine("Usage:\r\n IdxRngSort.exe <count_of_string> [<output_dir>]\r\n");
Console.WriteLine(" <count_of_string> - quantity of random generated strings for sorting, 100000000 for example");
Console.WriteLine(" <output_dir> - optional, a folder for saving files with unsorted and sorted strings");
Console.WriteLine("\r\nFor example:\r\n IdxRngSort.exe 100000000 d:\\out_dir\r\n");
Console.WriteLine($"It's not recommend to set more than 100 millions due to problems with lack of RAM");
Console.WriteLine("\r\nPress a key ...");
Console.ReadKey();
return (false, 0, "");
}
try
{
int cnt = int.Parse(args[0]);
string dir = "";
if (args.Length > 1)
{
dir = args[1];
if (!Directory.Exists(dir))
Directory.CreateDirectory(dir);
}
return (true, cnt, dir);
}
catch (Exception e)
{
Console.WriteLine(e.Message);
Console.WriteLine(e.StackTrace);
Console.WriteLine();
return ProcessCommand([], false);
}
}
}Статьи, которые могут быть интересны:
Как дизайнеру с помощью макетов оптимизировать процессы и сэкономить время
Как у нас почти получилось сделать автономного робота для «Битвы Роботов»
База об организации процесса разметки: команда, онбординг, метрики
Подписывайтесь на блог и Телеграм-канал Alfa Digital — там мы постим новости, опросы, видео с митапов, краткие выжимки из статей, иногда шутим.
