Сортируем сотни млн строк в разы быстрее библиотечных алгоритмов. А не замахнуться ли нам на ммм… на O(n)?

/* ======================================================================================= Пример-иллюстрация реализации алгорима сортировки Индексацией Ранжирования в сравнении со встроеннй сортировкой Arraу.Sort() Модуль предназначен для компилирования под .NET9 на платформе Windows 10 Среда разработки - Visual Studio 2022 Использовать скомпилированную программу: IdxRngSort.exe <кол-во строк> [<путь к каталогу сохранения>] <кол-во строк> - обязательный параметр. Задает кол-во случайно сгенерированных строк для сортировки. Рекомендуется от 1 млн до 100 млн Не задавайте более 100 млн на Home PC, может случиться вылет по памяти Задавать меньше 100 тыс смысла нет - алгоритм эффективен только на больших объемах <путь к каталогу сохранения> - необязательный параметр. Если задан, то в этот каталог сохраняться исходные и сортиртированные данные Например: IdxRngSort.exe 100000000 d:\outdir Данная программа не является каким-то законченным решением, а является только иллюстрирующим примером реализации алгоритма, поэтому использование этого кода - на ваш собственный риск. Авторские права на алгоритм сортировки Индексацией Ранжирования зарегистрированы в 2025 г. Ограничений на использование алгоритма нет, кроме указания авторства: Уфимцев Глеб Вячеславович, г. Москва ======================================================================================= */ 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); } } }