SortedList против SortedDictionary против Sort () - PullRequest
Новая
       22

SortedList против SortedDictionary против Sort ()

22 голосов
/ 10 января 2010

Это продолжение таких вопросов, как этот .

Есть ли какие-либо рекомендации по настройке производительности? Я не имею в виду выигрыш в биг-о, просто экономя некоторое линейное время.

Например, сколько экономит предварительная сортировка на SortedList или SortedDictionary?

Скажем, у меня есть личный класс с 3 свойствами для сортировки, одним из которых является возраст в годах. Должен ли я сначала положить предметы на возраст?

Должен ли я сначала отсортировать по одному свойству, затем использовать полученный список / словарь для сортировки по двум свойствам и т. Д.

Какие-нибудь другие оптимизации, которые приходят на ум?

1 Ответ

57 голосов
/ 10 января 2010

Ну, это простой выигрыш в SortedList. Для вставки элемента требуется двоичный поиск (O (log (n)), чтобы найти точку вставки, затем List.Insert (O (n)) для вставки элемента. Доминирует Insert (), для заполнения списка требуется O (n). ^ 2). Если входные элементы уже отсортированы, то вставка сворачивается в O (1), но не влияет на поиск. Заполнение теперь O (nlog (n)). Вы не волнуетесь, насколько велик Oh, сортировка во-первых всегда более эффективна. Предполагая, что вы можете позволить себе удвоить требования к хранилищу.

SortedDictionary отличается, он использует красно-черное дерево. Нахождение точки вставки требует O (log (n)). Впоследствии может потребоваться перебалансировка дерева, что также требует O (log (n)). Заполнение словаря, таким образом, занимает O (nlog (n)). Использование отсортированного ввода не меняет усилия по поиску точки вставки или перебалансировке, оно все равно равно O (nlog (n)). Теперь значение Oh имеет значение, однако для вставки отсортированного ввода требуется постоянное перебалансирование дерева. Это работает лучше, если ввод случайный, вам не нужно сортировать ввод.

Таким образом, заполнение SortedList отсортированным вводом и заполнение SortedDictionary несортированным вводом равно O (nlog (n)). Игнорируя стоимость предоставления отсортированного ввода, Oh of SortedList меньше Oh of SortedDictionary. Это деталь реализации из-за того, как List выделяет память. Это нужно сделать только O (log (n)) раз, красно-черное дерево должно выделить O (n) раз. Очень маленький О, кстати.

Примечательно, что ни один из них не сравнивается выгодно с простым заполнением списка и последующим вызовом Sort (). Это также O (nlog (n)). На самом деле, если входные данные уже случайно отсортированы, вы можете обойти вызов Sort (), это сводится к O (n). Анализ затрат теперь должен перейти к усилиям, необходимым для сортировки входных данных. Трудно обойти фундаментальную сложность Sort (), O (nlog (n)). Он может быть невидим, можно отсортировать входные данные, скажем, по запросу SQL. Это займет больше времени, чтобы завершить.

Смысл использования SortedList или SortedDictonary - сохранять коллекцию отсортированной после вставок. Если вы беспокоитесь только о заполнении, но не о мутировании, вам не следует использовать эти коллекции.

...