Ускорение list.contains

Question

У нас есть класс библиотеки C#, который портится из списка, но медленный, потому что List.Contains работает медленно. Мы не можем изменить класс, чтобы наследовать от чего-то другого, такого как Dictionary или HashSet, потому что много клиентского кода зависит от этого класса, и он слишком вовлечен в изменение интерфейса. Есть ли простой способ ускорить этот метод без его изменения? Некоторые из списков очень большие, поэтому нам не нужны две копии в памяти. Мы также не хотим переопределять все методы List.

public class UniqueList<T> : List<T>, IList<T> 
{ 
    public new void Add(T item) 
    { 
     if (!this.Contains(item) && item != null) 
     { 
      base.Add(item); 
     } 
    } 

Answer 1

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

Answer 2

Наследование из списка очень плохая идея, так как вы не имеете контроля, как ваш класс используется кодом клиента

List.Contains является о (п) операции. Dictionary.ContainsKey - это O (1), поэтому я считаю, что использование Словаря - лучший совет, но если вы действительно не хотите его использовать, еще одна возможность - сохранить список, отсортированный для получения O (log п)

public void Add(T item) 
{ 
    int index = BinarySearch(item); 
    if (index < 0) 
    { 
     Insert(~index, item); 
    } 
} 

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

Использование BinarySearch не может быть возможно в вашем сценарии, так как это зависит от того, что T может быть: http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

Этот метод использует Comparer.Default компаратор по умолчанию для типа T, чтобы определить порядок элементов списка. Свойство Comparer.Default проверяет, реализует ли тип T универсальный интерфейс IComparable и использует эту реализацию, если таковая имеется. Если нет, Comparer.Default проверяет, реализует ли тип T интерфейс IComparable. Если тип T не реализует ни один из интерфейсов, Comparer.Default вызывает исключение InvalidOperationException.

Answer 3

В короткой п

Поскольку вы унаследовав от List<> вы существенно ввинчивается, потому что даже если вы Тень содержит метод, который вы не можете остановить клиентский код от прохождения UniqueList к способу который принимает List<>, это скроет ваши новые Содержит и использует существующий.

Необходимо устранить этот трудный путь, удалить наследование на List<>, реализовать свои собственные. Содержит, повторно реализует любые методы, которые вам нужны из списка (внутри вы можете использовать private List<> для хранения и просто делегировать его там, где это необходимо), и исправить весь код, который это изменение нарушает.

В то время как вы нарушаете вещи, вы можете взглянуть на классы коллекции C5, которые способствуют разработке против интерфейсов, помогая вам не ударить по этой проблеме (я знаю, больше закрытия двери сарая после того, как лошадь заперта)

Я знаю, что это не тот ответ, который вы ищете, но вы не получите ответ, который вы хотите (там действительно нет возможности запрограммировать это, вы можете попробовать что-то вроде Castle Interceptors, но я не думайте, что они будут работать в этом случае ...но тогда я не могу быть уверен, что они этого не сделают)

Опять же, извинения за то, что не смогли реально помочь.