Я решил немного поковырять вопрос. Возможно, это не будет ответом, но таки хочу поделиться информацией.
Итак, я хочу: сгенерировать большой массив данных, написать несколько сортировок, сравнить производительность.
Генерация данных:
Тут все просто. Есть только 1 правило - число в строке не начинается с 0, то есть у числа в строке нет ведущих нулей. Сама генерация данных выглядит так:
private static Random random = new Random();
public static string[] GenerateRandomStringArray()
{
string[] ret = new string[200000];
for(int i=0; i<ret.Length; i++)
ret[i] = GenerateRandomString();
return ret;
}
public static string GenerateRandomString()
{
var sb = new StringBuilder();
var len = random.Next(1, 50);
sb.Append(random.Next(1, 10));
for(var i=0; i<len; i++)
sb.Append(random.Next(0, 10));
return sb.ToString();
}
public static string[] Copy(string[] input)
{
var dest = new string[input.Length];
Array.Copy(input, dest, input.Length);
return dest;
}
Метод Copy нам понадобится попозже.
1) Текущий вариант
Далее, скопирую сортировку из вопроса. Точнее, просто реализую компарер аналогичным образом.
public class Comparer : IComparer<string>
{
public int Compare(string s1, string s2)
{
int x;
if (int.TryParse(s1, out x) && int.TryParse(s2, out x))
{
if (int.Parse(s1) > int.Parse(s2))
{
return 1;
}
if (int.Parse(s1) < int.Parse(s2))
{
return -1;
}
return 0;
}
else
{
if (s1.Length > s2.Length)
{
return 1;
}
else if (s1.Length < s2.Length)
{
return -1;
}
else
{
return string.Compare(s1, s2);
}
}
}
}
Сортировка этим компарером будет выглядеть как то так:
array = array.OrderBy(x => x, new Comparer()).ToArray();
2) Новый компарер
Как мы видели, предыдущий компарер никуда не годится. Слишком много телодвижений с попытками конвертировать текст в число. Попробуем его переписать.
public class NewComparer : IComparer<string>
{
public int Compare(string s1, string s2)
{
var lenCompare = s1.Length.CompareTo(s2.Length);
if (lenCompare != 0) return lenCompare;
return string.CompareOrdinal(s1, s2);
}
}
Получилось компактно и эффективно. Пользоваться так
array = array.OrderBy(x => x, new Comparer()).ToArray();
3) Поразрядная сортировка
Поразрядная сортировка хороша тем, что быстро сортирует строки с разумным ограничением алфавита (а также зависит от минимальной и максимальной длины строки). Но это как раз наш случай - у нас же только цифры в алфавите, то есть размер алфавита - 10.
Вообще, для поразрядной сортировки чисел рекомендуют LSD сортировку, но у меня где то в закромах была реализация MSD, потому я выдумывать не стал ничего и просто прикрутил MSD - по идее, скорость работы должна быть примерно та же, что и у LSD.
И ещё один ньюанс. Перед MSD сортировкой я отсортирую и поделю строки по длине сортировкой подсчетом, так как сама по себе MSD сортировка длину строки не учитывает (точнее, учитывает, но не так, как мне надо). В общем, будет весело :)
Что касается реализации, сначала я добавил функцию, по которой буду получать код символа по индексу из строки. Я накатал для этого функцию, так как запросы могут выходить за рамки строки и надо вернуть -1 в этом случае.
private static int GetChar(string s, int pos)
{
if (pos >= 0 && pos < s.Length) return s[pos] - '0';
else return -1;
}
Далее, сама сортировка:
public static void MSD(string[] inp, string[] tmp, int start, int end, int d)
{
if (end <= start) return;
int r = 10;
int[] count = new int[r + 2];
for (int i = start; i <= end; i++) count[GetChar(inp[i], d) + 2]++;
for (int i = 0; i <= r; i++) count[i + 1] += count[i];
for (int i = start; i <= end; i++) tmp[count[GetChar(inp[i], d) + 1]++] = inp[i];
for (int i = start; i <= end; i++) inp[i] = tmp[i - start];
for (int i = 0; i < r; i++) MSD(inp, tmp, start + count[i], start + count[i + 1] - 1, d + 1);
}
Сортировка подсчетом для учета длин строк + MSD для каждой группы строк одинаковой длины:
public static void CountSortWithMSD(string[] inp, string[] tmp, int start, int end)
{
if (end <= start) return;
int r = 55;
int[] count = new int[r + 2];
for (int i = start; i <= end; i++) count[inp[i].Length + 2]++;
for (int i = 0; i <= r; i++) count[i + 1] += count[i];
for (int i = start; i <= end; i++) tmp[count[inp[i].Length + 1]++] = inp[i];
for (int i = start; i <= end; i++) inp[i] = tmp[i - start];
for (int i = 0; i < r; i++) MSD(inp, tmp, start + count[i], start + count[i + 1] - 1, 0);
}
Основная функция сортировки:
public static void MSD(string[] inp)
{
string[] tmp = new string[inp.Length];
CountSortWithMSD(inp, tmp, 0, inp.Length - 1);
}
Итак, у нас есть 3 реализации сортировки. Как убедиться, что они все работают одинаково? Примерно вот так (код класса MyClass
будет ниже):
var test = new MyClass(); // тут внутри я сгенерирую начальный массив строк
var copy1 = test.LinqOldWay();
var copy2 = test.LinqNewWay();
var copy3 = test.MSDWay();
for (int i = 0; i < copy1.Length; i++)
{
if (string.CompareOrdinal(copy1[i], copy2[i]) != 0
|| string.CompareOrdinal(copy1[i], copy3[i]) != 0)
Console.WriteLine($"{copy1[i]} - {copy2[i]} - {copy3[i]}");
}
По сути, тут при одинаковых входных данных я делаю 3 сортировки и проверяю. что результаты абсолютно одинаковые (если не одинаковые, то выведу разность на экран). Напомню, что входные данные - это 200к рандомных строк длиной от 1 до 50 символа.
Теперь, как проверить, какой из вариантв быстрее? Написать бенчмарк, конечно. Я буду использовать библиотеку BenchmarkDotNet
public class MyClass
{
public MyClass()
{
initialData = GenerateRandomStringArray();
}
string[] initialData;
[Benchmark]
public string[] LinqOldWay()
{
var copy = Copy(initialData);
copy = copy.OrderBy(x => x, new Comparer()).ToArray();
return copy;
}
[Benchmark]
public string[] LinqNewWay()
{
var copy = Copy(initialData);
copy = copy.OrderBy(x => x, new NewComparer()).ToArray();
return copy;
}
[Benchmark]
public string[] MSDWay()
{
var copy = Copy(initialData);
MSD(copy);
return copy;
}
}
Конечно, нельзя сказать, что тест прямо очень честный, так как linq варианты таки создают новые коллекции, а MSD хоть и пользуется доп памятью, но при этом сортирует массив на месте. Но я не думаю, что это будет как то сильно влиять на время работы, учитывая, что мы сортируем 200к элементов. Итак, запускаем тесты:
BenchmarkRunner.Run<MyClass>();
Не буду писать все детали теста, основная таблица выглядит так:
Method | Mean | Error | StdDev |
----------- |------------:|----------:|----------:|
LinqOldWay | 2,223.73 ms | 31.922 ms | 29.860 ms |
LinqNewWay | 276.29 ms | 5.376 ms | 5.029 ms |
MSDWay | 90.88 ms | 1.333 ms | 1.247 ms |
Мы видим, что простая правка компарера ускорила сортировку в 8 раз. А поразрядная сортировка оказалась ещё чуть чуть быстрее - примерно в 3 раза быстрей нового компарера и в 25 раз быстрее начального варианта.
Я уверен, что если чуть чуть больше посвятить этому времени, и вместо MSD использовать LSD после разбития массива на подмассивы одинаковой длины, то результат может быть даже лучше (хотя асимптотика должна быть та же).
UPD По совету @PavelMayorov подправил функцию GetChar, чтобы избавиться от сортировки подсчетом. Выглядит результат так:
private static int GetChar2(string s, int pos, int maxLength)
{
int d = pos - maxLength + s.Length;
if (d >= -0 && d < s.Length) return s[d] - '0'; else return 0;
}
public static void MSD2(string[] inp)
{
string[] tmp = new string[inp.Length];
MSD2(inp, tmp, 0, inp.Length - 1, 0);
}
public static void MSD2(string[] inp, string[] tmp, int start, int end, int d)
{
if (end <= start) return;
if (d > 55) return;
int r = 10;
int[] count = new int[r + 2];
for (int i = start; i <= end; i++) count[GetChar2(inp[i], d, 55) + 2]++;
for (int i = 0; i <= r; i++) count[i + 1] += count[i];
for (int i = start; i <= end; i++) tmp[count[GetChar2(inp[i], d, 55) + 1]++] = inp[i];
for (int i = start; i <= end; i++) inp[i] = tmp[i - start];
for (int i = 0; i < r; i++) MSD2(inp, tmp, start + count[i], start + count[i + 1] - 1, d + 1);
}
Тест
[Benchmark]
public string[] MSDWay2()
{
var copy = Copy(initialData);
MSD2(copy);
return copy;
}
Результаты по сравнению в MSD (тестил на другом компе, потому эти результаты в абсолютных значениях отличаются от предыдущего теста)
Method | Mean | Error | StdDev |
----------- |-----------:|----------:|-----------:|
LinqOldWay | 150.878 ms | 4.7384 ms | 13.7471 ms |
LinqNewWay | 9.986 ms | 0.1962 ms | 0.5204 ms |
MSDWay | 2.245 ms | 0.0449 ms | 0.1084 ms |
MSDWay2 | 10.000 ms | 0.2809 ms | 0.7830 ms |
Видно, что второй метод по скорости примерно такой же, как метод с новым компарером. Это потому, что второй метод будет опрашивать короткие строки также, как и длинные, и вызовов метода GetChar2
будет гораздо больше, чем GetChar
(для 200к рандомных строк GetChar2
вызвался 13354222
раз, когда GetChar
вызвался GetChar
1745584
раз).
UPD распределение строк в зависимости от длины на рандомных данных. Первый столбец - длина строки, второй - количество строк с такой длиной

UPD
Итак, по совету @PavelMayorov я поменял генератор данных.
public static string GenerateRandomString()
{
var sb = new StringBuilder();
for (var i = 0; i < 50; i++)
sb.Append(random.Next(0, 10));
return sb.ToString().TrimStart('0');
}
Теперь распределение равномерное, распределение длин строк:

Тесты те же, количество данных то же самое. Результаты:
Method | Mean | Error | StdDev |
----------- |------------:|-----------:|-----------:|
LinqOldWay | 1,821.69 ms | 62.8858 ms | 58.8234 ms |
LinqNewWay | 177.76 ms | 3.4509 ms | 3.5438 ms |
MSDWay | 71.54 ms | 1.4094 ms | 1.3842 ms |
MSDWay2 | 93.57 ms | 0.8887 ms | 0.7878 ms |
Теперь обновленный MSD очень близок к первой версии - от того, что перекоса в длинах чисел нет.
StringComparison.Ordinal
или методCompareOrdinal
. В линковскомOrderBy
, соответственно, можно использовать параметрStringComparer.Ordinal
.