Самый эффективный способ сортировки ObservableCollection <T>с новым элементом в нем

Question

У меня есть класс ViewModel следующим образом:

public class ListViewModel
{
    public ObservableCollection<InfoItem> List { get; set; }
}

public interface InfoItem
{
  int Reference { get; }
  string Name { get; }
}

Коллекция отсортирована по имени, которое отображается в пользовательском интерфейсе. У меня есть сценарий, в котором коллекция содержит пару тысяч элементов, и я добавляю новый элемент в коллекцию.

Какой самый эффективный способ пересортировать мою коллекцию по Имени, чтобы новый элемент появился в нужном месте в списке?

Answer 1

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

Жаль, что нет общего метода BinarySearch для расширения IList<T>, но это не должно бытьслишком сложно писать.Предполагая, что вы захотите написать общий метод для этого (что я бы посоветовал вам сделать - это не будет значительно сложнее, чем написание InfoItem -конкретного), вы бы либо захотеливзять проекцию IComparer<T> или , например

public static int BinarySearch<T>(this IList<T> source, IComparer<T> comparer)

или

public static int BinarySearch<TSource, TKey>(
    this IList<TSource> source,
    Func<TSource, TKey> keySelector)

Я предлагаю вам сделать возвращаемое значение в соответствии с соглашением List<T>.BinarySearch, так что если совпадение не найдено, оно возвращает побитовое отрицание индекса, в который элемент будет вставлен.

Answer 2

Поскольку ваша коллекция уже отсортирована, просто Insert новый элемент в соответствующем месте, которое вы можете обнаружить с помощью двоичного поиска .К сожалению, на IList<T> нет встроенного бинарного поиска, но вы легко можете создать метод расширения, который сделает эту работу.Будьте осторожны при реализации бинарного поиска, чтобы не вводить классическую ошибку (ошибка заключается в возможном переполнении при вычислении среднего значения индексов low и high, поскольку low + high может переполниться).Вы можете использовать List<T>.BinarySearch в качестве шаблона.