Блог

Главная - Вопросы по программированию - Производительность SortedDictionary по сравнению с сортировкой словаря

Производительность SortedDictionary по сравнению с сортировкой словаря

#c# #performance #dictionary #time-complexity #sorteddictionary

Вопрос:

У меня есть список объектов. Эти объекты имеют множество свойств, включая цену и количество. Мне нужно создать новый словарь с ключом «цена» и значением «количество». Если два объекта имеют одинаковую цену, то в результирующем словаре в качестве ключа должна быть указана цена, а в качестве значения-сумма количеств обоих объектов. Насколько мне известно, я могу сделать это двумя способами.

  1. Используя Dictionary структуру данных, и отсортируйте окончательный словарь:
 var result = new Dictionary<int, int>();
foreach(List<object> obj in list) {
    if(result.ContainsKey(obj.price)) {
        result[price]  = quantity;
    }
    else {
        result[price] = quantity;
    }
}
result = result.OrderBy(x => x.Key);
  1. С помощью SortedDictionary :
 var result = new SortedDictionary<int, int>();
foreach(List<object> obj in list) {
    if(result.ContainsKey(obj.price)) {
        result[price]  = quantity;
    }
    else {
        result[price] = quantity;
    }
}

В первом методе временная сложность ContainsKey O(1) равна, а для сортировки по порядку используется быстрая сортировка, которая имеет временную сложность O(nlogn) . Таким образом, общая временная сложность будет такой O(nlogn) . Во втором методе ContainsKey сортировка уже выполняется O(log n) , и, поскольку я повторяю это несколько n раз, общая сложность будет такой O(nlogn) . Согласно моим расчетам, я чувствую, что использование обоих методов должно занять одинаковое время. Пожалуйста, поправьте меня, если я ошибаюсь. И, если я ошибаюсь, какой метод имеет лучшую производительность?

Комментарии:

1. Если бы сортировка путем вставки в сортированный словарь была бы быстрее, чем просто сортировка, разве сортировка не осуществлялась бы через сортированный словарь? Кроме того, сложность в то же время с точки зрения обозначения Big-O не означает, что время выполнения будет одинаковым.

2. Также вы пытались измерить время, потраченное на ваши данные с использованием обоих подходов?

3. @GuruStron Я не измерял время, затраченное на оба подхода. И, возможно, временная сложность не означает, что среда выполнения одинакова, но это здоровый способ программирования, основанный на временной сложности, верно? И, судя по первой половине вашего первого сообщения, вы предполагаете, что метод 1 эффективен?

4. Вы не можете заказать словарь с использованием OrderBy() , потому что он возвращает an IEnumerable<T> , поэтому ваш пример кода не будет компилироваться — следовательно, два подхода НЕ совпадают.

5. @user147504 это здорово, но все же это не должно быть единственным, что нужно учитывать. И в конце концов, вы всегда должны проверять, основываясь на предполагаемом объеме обрабатываемых данных и самих фактических данных.

Ответ №1:

1 обычно будет быстрее. Проще выполнить сортировку один раз, чем вести сортированный словарь.

Сложность Big-O может быть одинаковой, но равная сложность не означает равной производительности.

Контрольные результаты:

 |      Method |     Mean |    Error |   StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------ |---------:|---------:|---------:|-------:|------:|------:|----------:|
|        Dict | 361.7 ns |  7.07 ns |  7.26 ns | 0.1554 |     - |     - |     488 B |
| DictOrderBy | 499.9 ns |  9.66 ns |  9.04 ns | 0.2651 |     - |     - |     832 B |
|  SortedDict | 943.7 ns | 18.26 ns | 22.42 ns | 0.2241 |     - |     - |     704 B |

Код: https://gist.github.com/ptupitsyn/71eefbdb607ce3f9ddfae2f5e099184e

Примечания:

  • TryGetValue исключает дополнительный поиск по словарю
  • Все методы сравнения возвращают результаты, как List в попытке сделать их справедливыми
Метки: