Частые вставки в отсортированную коллекцию

Question

Я отсортировал коллекцию (список), и мне нужно постоянно сортировать ее.

В настоящее время я использую List.BinarySearch в своей коллекции, а затем вставляю элемент в нужное место. Я также пробовал сортировать список после каждой вставки, но производительность была неприемлемой.

Есть ли решение, которое даст лучшую производительность? Может быть, я должен использовать другую коллекцию.

(мне известен SortedList, но он ограничен уникальными ключами)

Answer 1

Если вы используете .Net 4, вы можете использовать SortedSet<T>

http://msdn.microsoft.com/en-us/library/dd412070.aspx

Для .Net 3.5 и ниже, посмотрите, подходит ли вам SortedList<TKey,TValue>.

http://msdn.microsoft.com/en-us/library/ms132319.aspx

Answer 2

PowerCollections имеет тип OrderedBag, который может подойти для того, что вам нужно.Из документов

Вставка , удаление и поиск элемента выполняются в log (N) + M время , где N - эточисло ключей в дереве, а M - текущее количество копий обрабатываемого элемента.

Однако для встроенных типов .NET 3.5 используйте List.BinarySearch и вставляйте каждый элемент вправильное место - хорошее начало, но оно использует массив изнутри, поэтому ваша производительность будет падать из-за того, что вы копируете при вставке.

Если вы можете сгруппировать вставки в пакеты, которые улучшат ситуацию, но если вы не можете перейти только к одной операции сортировки после всей вставки, вам, вероятно, лучше использовать OrderedBag из PowerCollections, если можете.

Answer 3

Попробуйте объединить вставки в партии и сортировать только в конце каждой партии.