SortedList против SortedDictionary vs. Sort() - программирование

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

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

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

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

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

Любые другие оптимизации, которые следует учитывать spring?

Ответ 1

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

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

Так заполняется 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 является сохранение сортировки коллекции после вставок. Если вы только беспокоитесь о заполнении, но не мутируете, вы не должны использовать эти коллекции.