1

Сделал замер, чтобы выяснить создание и итерация какой коллекции быстрее IOrderedEnumerable<T> или SortedSet<T>

internal class User
{
    public string Surname { get; set; }
    public string Name { get; set; }
    public int DocumNumber { get; set; }
}

internal class UserDto : IComparable<UserDto>
{
    public string FullName { get; set; }
    public int DocumNumber { get; set; }
    public int CompareTo(UserDto other)
    {
        return string.Compare(this.FullName, other.FullName, StringComparison.Ordinal);
    }
}
class Program
{
    static void Main(string[] args)
    {
        const int count = 1000000;
        var users = new List<User>();
        for (var i = 0; i < count; i++)
        {
            users.Add(new User
            {
                Name = "Name",
                Surname = "Surname",
                DocumNumber = i
            });
        }

        // IOrderedEnumerable<T>
        var watch = Stopwatch.StartNew();
        var userDtoList = new List<UserDto>();
        foreach (var user in users)
        {
            userDtoList.Add(new UserDto
            {
                FullName = $"{user.Surname} {user.Name}",
                DocumNumber = user.DocumNumber
            });
        }
        var orderedEnumerableUserDto = userDtoList.OrderBy(u => u.FullName);
        foreach (var userDto in orderedEnumerableUserDto)
        {
            // просто делаем некую работу
        }
        watch.Stop();
        Console.WriteLine("IOrderedEnumerable<T>: {0}ms", watch.ElapsedMilliseconds);

        // SortedSet<T>                                                                 
        watch.Restart();
        var sortedSetUserDto = new SortedSet<UserDto>();
        foreach (var user in users)
        {
            sortedSetUserDto.Add(new UserDto
            {
                FullName = $"{user.Surname} {user.Name}",
                DocumNumber = user.DocumNumber
            });
        }
        foreach (var userDto in sortedSetUserDto)
        {
            // просто делаем некую работу
        }
        watch.Stop();
        Console.WriteLine("SortedSet<T>: {0}ms", watch.ElapsedMilliseconds);

        System.Console.ReadKey();
    }
}

По итогу трех замеров средние были таковы:

IOrderedEnumerable<T>: 4661 ms 
SortedSet<T>:          611 ms

почти в 8 раз SortedSet<T> оказался быстрее.


Немного о IOrderedEnumerable

В начале поста я назвал IOrderedEnumerable<T> коллекцией. Знаю был не прав, sorry, просто не знаю, как грамотно оперировать, когда сравниваются коллекция и интерфейс.

Я не понял, как работает этот интерфейс, что за перечислитель он возвращает. Потому что если мы у обоих замеров уберем блок

foreach (var userDto in orderedEnumerableUserDto)
{
    // просто делаем некую работу
}

то увидим, что замеры показывают одинаковые результаты. Уверен, что выражение

var orderedEnumerableUserDto = userDtoList.OrderBy(u => u.FullName);

никакой сортировки не делает в памяти, иначе это заняло бы уйму времени. Там скорее всего происходит просто маркировка объектов — кто в какой очереди будет вызывается интерфейсом перечислителем IOrderedEnumerable, типа

введите сюда описание изображения


Вопрос

Свои мысли по поводу IOrderedEnumerable<T> привел из-за того, что хотел сказать, что если бы понимал, как он работает изнутри, то возможно вопрос не возник. Ну а вопрос в следующем: что из этих двух вариантов лучше возвращает контроллеру, который будет сериализовывать все это добро в JSON, что быстрее будет происходить?

У меня не хватило смекалки как сделать замер скорости сериализации этих двух объектов и был бы благодарен если в качестве ответа был показан такой замер.

14
  • Сериализация использует рефлексию, поэтому, я думаю, структура данных имеет уже второстепенное значение по скорости 4 фев 2018 в 16:59
  • результат OrderBy сортируется в момент вызова foreach, в то время как для SortderSet осуществляется просто вывод, но большие затраты на вставку элементов
    – Grundy
    4 фев 2018 в 17:14
  • @Grundy т.е. сортировка происходит только когда foreach начинает работать? А эта сортировка предполагает создание новой отсортированный коллекции в памяти? 4 фев 2018 в 17:22
  • Конечно предполагает, Linq не изменяет последовательности, а только создаёт новые 4 фев 2018 в 17:23
  • @АндрейNOP , для сериализации в JSON, на сколько мне известно, ASP.NET Web API использует DataContractJsonSerializer. И когда на сериализацию ему будет передан IOrderedEnumerable<T>, то потребуется сначала время на создание отсортированной коллекции в памяти и только затем можно будет приступить к сериализации. Верно я описал конвейер?) 4 фев 2018 в 17:34

1 ответ 1

2

Первая ваша ошибка - вы используете список из миллиона одинаковых элементов. А SortedSet не хранит одинаковые элементы, то есть реально у вас внутри SortedSet хранится всего один элемент.

Если сделать все элементы разными (Name = "Name" + i) - то время работы SortedSet увеличится в 10 раз.

Вторая ваша ошибка - вы в разных методах используете разные алгоритмы сравнения строк!

SortedSet у вас использует наиболее быстрый алгоритм StringComparison.Ordinal, который сравнивает номера символов - в то время как ваш GroupBy использует медленный алгоритм StringComparison.CurrentCulture (который, к примеру, учитывает равенство буквы "е" и обоих форм буквы "ё" при сортировке).

Простое указание для OrderBy использовать быстрое сравнение строк (.OrderBy(u => u.FullName, StringComparer.Ordinal);) заметно ускоряет сортировку.

В результате у меня получилась примерно вот такая картина:

SortedSet: 1214ms

IOrderedEnumerable: 920ms

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


Для подготовки данных перед сериализацией используйте OrderBy. SortedSet использовать не нужно потому что он решает совсем другую задачу.

Если нужно ускорение любой ценой - можете использовать List<T>.Sort, он будет малость по-быстрее.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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