Стоит ли сортировать список при получении или настройке?

Question

Решение, с которым я часто сталкиваюсь, заключается в том, когда сортировать список элементов. При добавлении элемента, сохранении списка отсортированным всегда или при обращении к списку.

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

Answer 1

Я привык думать так:

• Если список заполняется все сразу и только после того, как он прочитан, то добавьте элементы в несортированном порядке и отсортируйте их только в конце заполнения (в терминах сложности это требует O(n log n) плюс сложность заполнения, и это обычно быстрее, чем сортировка при добавлении элементов)
• И наоборот, если список необходимо прочитать до того, как он будет полностью заполнен, то вам нужно добавить элементы в отсортированном порядке (возможно, с помощью какой-то специальной структуры данных, выполняющей работу за вас, например, отсортированный список, красно-черное дерево и т. Д.)

Answer 2

Сортировка списка при каждом доступе - плохая идея. У вас должен быть флаг, который вы устанавливаете при изменении коллекции. Только если этот флаг установлен, вам нужно отсортировать, а затем сбросить флаг.

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

Я не знаю, какую платформу / фреймворк вы используете. Я знаю, что .NET предоставляет класс SortedList, который управляет таким алгоритмом сортировки вставок.

Answer 3

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

Если вы хотите повысить производительность при доступе / поиске элементов, хорошим решением будет сохранение списка, отсортированного с помощью InsertionSort (http://en.wikipedia.org/wiki/Insertion_sort).

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

Но есть много других опций: например, поддерживать переменную, которая говорит: «списоксортировать "и сортировать при каждой n-й вставке, при простое или при доступе (если вам нужно).