1

Имеется список данных, которые сортируются по полю sortingField, которое является строковым типом с максимальной длинной символов равной 50. Данные сортируются через LINQ OrderBy, поскольку длина строки может достигать 50 символов - не все значения могут быть приведены к числовому типу. Поэтому реализовал в классе сортируемых объектов Compare метод, интерфейса IComparer. метод выглядит так:

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); 
      } 
   } 
}

Первый вопрос: приемлема ли такая реализация или есть подход лучше? Второй вопрос: стоит ли делать приведение к численному типу и сравнивать так, если это возможно или лучше всё сравнивать только строковые значения, какое сравнение в данном случае должно проходить быстрее?

Целью является сделать быстрое сравнение строковых данных, которые состоят только из цифр, но из-за большой длины строки (уменьшить нельзя) невозможно все значения приводить к целочисленному типу, чтобы сортировка проходила по логике сортировки числа.

P.S. также не понятен такой момент. Для вызова метода Compare, который я реализовал, вместо записи .OrderBy(f => int.Parse(f.sortingField)) использую такую запись .OrderBy(f => f.sortingField, new MyClass()). Честно говоря, не понимаю почему нужно вызывать конструктор класса, объекты которого сортирую с реализацией моего метода. И как данный вызов конструктора бьет по производительности?

5
  • а что сортируете? Есть примеры входных данных?
    – tym32167
    26 сен 2018 в 17:38
  • также, кмк, числа занимают меньше памяти и сравниваются побыстрее, чем строки
    – tym32167
    26 сен 2018 в 17:39
  • гляжу на ваш компаратор - почему бы сначала не сравнить длины строк, ведь если одна строка длинней другой, то понятно, что число внутри больше, и не нужно в таком случае парсить стрку в число
    – tym32167
    26 сен 2018 в 17:41
  • Сравнение чисел происходит, конечно, быстрее, чем сравнение строк. Но парсинг строк в числа очень долог, поэтому съедает возможный профит. Так что уберите это нафиг и просто сравнивайте строки. 26 сен 2018 в 17:44
  • Для максимальной производительности используйте параметр StringComparison.Ordinal или метод CompareOrdinal. В линковском OrderBy, соответственно, можно использовать параметр StringComparer.Ordinal. 26 сен 2018 в 17:50

1 ответ 1

4

Я решил немного поковырять вопрос. Возможно, это не будет ответом, но таки хочу поделиться информацией.

Итак, я хочу: сгенерировать большой массив данных, написать несколько сортировок, сравнить производительность.

Генерация данных:

Тут все просто. Есть только 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 очень близок к первой версии - от того, что перекоса в длинах чисел нет.

16
  • Вах! Я как раз читаю Кормена и только вчера прочёл про сортировку подсчетом и поразрядную, но мне даже не пришло в голову, что именно в данном случае она применима. 27 сен 2018 в 1:12
  • @AlexanderPetrov ну вот у вас есть возможность проверить теорию, что LSD тут может справиться лучше, чем MSD. Хотя я так думал вчра в 3 часа ночи, а сегодня с утра уже не уверен, что будут какие то сильные отличия :)
    – tym32167
    27 сен 2018 в 7:25
  • Если ваш GetChar сделать вот таким - int d = pos - maxLength + s.Length; if (d >= -0 && d < s.Length) return s[d] - '0'; else return 0; - то предварительное разбиение по длине строки не потребуется (плюс старшие ноли перестанут быть проблемой) 27 сен 2018 в 7:51
  • @PavelMayorov да, но тогда 1) мне придется делать больше вычислений (так как даже короткие строки будут интепретироваться как длинные, то есть по ним будут запрашиваться индексы, которых у них нет), то есть прога будет медленней. 2) По идее, так как я разбиваю строки на группы одинаковой длины, то можно попробовать вообще избавиться от этой функции, но меня вчера на это не хватило, я и так упоролся до 3 ночи это все писать и тестить :)
    – tym32167
    27 сен 2018 в 8:25
  • @PavelMayorov добавил апдейт
    – tym32167
    27 сен 2018 в 9:55

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.