List‹T›.Contains() работает очень медленно?

Если вы просто проверяете существование, HashSet<T> в .NET 3.5 - ваш лучший вариант - производительность, подобная словарю, но без пары ключ/значение - только значения:

    HashSet<int> data = new HashSet<int>();
    for (int i = 0; i < 1000000; i++)
    {
        data.Add(rand.Next(50000000));
    }
    bool contains = data.Contains(1234567); // etc

List.Contains — это операция O(n).

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

Я не думаю, что это хорошая идея - иметь список, содержащий миллион записей. Я не думаю, что класс List был разработан для этой цели. :)

Разве нельзя сохранить эти миллионы сущностей, например, в СУБД и выполнять запросы к этой базе данных?

Если это невозможно, я бы все равно использовал словарь.

Я думаю, у меня есть ответ! Да, это правда, что функция Contains() в списке (массиве) равна O(n), но если массив короткий и вы используете типы значений, он все равно должен быть достаточно быстрым. Но с помощью CLR Profiler [бесплатная загрузка с сайта Microsoft] я обнаружил, что Contains() упаковывает значения для их сравнения, что требует выделения кучи, что ОЧЕНЬ дорого (медленно). [Примечание: это .Net 2.0; другие версии .Net не тестировались.]

Вот полная история и решение. У нас есть перечисление под названием «VI» и создан класс под названием «ValueIdList», который является абстрактным типом для списка (массива) объектов VI. Первоначальная реализация была во времена древней .Net 1.1 и использовала инкапсулированный ArrayList. Недавно мы обнаружили в http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx, что универсальный список (List‹VI>) работает намного лучше, чем ArrayList для типов значений (например, наш enum VI), потому что значения не нужно упаковывать. Это правда, и это сработало... почти.

CLR Profiler преподнес сюрприз. Вот часть графика распределения:

• ValueIdList::Содержит bool(VI) 5,5 МБ (34,81%)
• Generic.List::Contains bool(‹UNKNOWN>) 5,5 МБ (34,81%)
• Generic.ObjectEqualityComparer‹T>::Equals bool (‹UNKNOWN> ‹UNKNOWN>) 5,5 МБ (34,88%)
• Ценности.VI 7,7 МБ (49,03%)

Как видите, Contains() неожиданно вызывает Generic.ObjectEqualityComparer.Equals(), что, по-видимому, требует упаковки значения VI, что требует дорогостоящего выделения кучи. Странно, что Microsoft исключила бокс из списка только для того, чтобы снова потребовать его для такой простой операции, как эта.

Наше решение состояло в том, чтобы переписать реализацию Contains(), что в нашем случае было легко сделать, поскольку мы уже инкапсулировали общий объект списка (_items). Вот простой код:

public bool Contains(VI id) 
{
  return IndexOf(id) >= 0;
}

public int IndexOf(VI id) 
{ 
  int i, count;

  count = _items.Count;
  for (i = 0; i < count; i++)
    if (_items[i] == id)
      return i;
  return -1;
}

public bool Remove(VI id) 
{
  int i;

  i = IndexOf(id);
  if (i < 0)
    return false;
  _items.RemoveAt(i);

  return true;
}

Сравнение значений VI теперь выполняется в нашей собственной версии IndexOf(), которая не требует упаковки и работает очень быстро. Наша конкретная программа ускорилась на 20% после этой простой перезаписи. О(н)... нет проблем! Просто избегайте напрасного использования памяти!

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

Конечно, словарь работает только в том случае, если ваши числа уникальны и не упорядочены.

Я думаю, что в .NET 3.5 также есть класс HashSet<T>, он также допускает только уникальные элементы.

Это не совсем ответ на ваш вопрос, но у меня есть класс, который увеличивает производительность Contains() в коллекции. Я создал подкласс очереди и добавил словарь, который сопоставляет хэш-коды спискам объектов. Функция Dictionary.Contains() — это O(1), тогда как List.Contains(), Queue.Contains() и Stack.Contains() — это O(n).

Тип значения словаря — это очередь, содержащая объекты с одинаковым хэш-кодом. Вызывающий объект может предоставить пользовательский объект класса, который реализует IEqualityComparer. Вы можете использовать этот шаблон для стеков или списков. В код потребуется всего несколько изменений.

/// <summary>
/// This is a class that mimics a queue, except the Contains() operation is O(1) rather     than O(n) thanks to an internal dictionary.
/// The dictionary remembers the hashcodes of the items that have been enqueued and dequeued.
/// Hashcode collisions are stored in a queue to maintain FIFO order.
/// </summary>
/// <typeparam name="T"></typeparam>
private class HashQueue<T> : Queue<T>
{
    private readonly IEqualityComparer<T> _comp;
    public readonly Dictionary<int, Queue<T>> _hashes; //_hashes.Count doesn't always equal base.Count (due to collisions)

    public HashQueue(IEqualityComparer<T> comp = null) : base()
    {
        this._comp = comp;
        this._hashes = new Dictionary<int, Queue<T>>();
    }

    public HashQueue(int capacity, IEqualityComparer<T> comp = null) : base(capacity)
    {
        this._comp = comp;
        this._hashes = new Dictionary<int, Queue<T>>(capacity);
    }

    public HashQueue(IEnumerable<T> collection, IEqualityComparer<T> comp = null) :     base(collection)
    {
        this._comp = comp;

        this._hashes = new Dictionary<int, Queue<T>>(base.Count);
        foreach (var item in collection)
        {
            this.EnqueueDictionary(item);
        }
    }

    public new void Enqueue(T item)
    {
        base.Enqueue(item); //add to queue
        this.EnqueueDictionary(item);
    }

    private void EnqueueDictionary(T item)
    {
        int hash = this._comp == null ? item.GetHashCode() :     this._comp.GetHashCode(item);
        Queue<T> temp;
        if (!this._hashes.TryGetValue(hash, out temp))
        {
            temp = new Queue<T>();
            this._hashes.Add(hash, temp);
        }
        temp.Enqueue(item);
    }

    public new T Dequeue()
    {
        T result = base.Dequeue(); //remove from queue

        int hash = this._comp == null ? result.GetHashCode() : this._comp.GetHashCode(result);
        Queue<T> temp;
        if (this._hashes.TryGetValue(hash, out temp))
        {
            temp.Dequeue();
            if (temp.Count == 0)
                this._hashes.Remove(hash);
        }

        return result;
    }

    public new bool Contains(T item)
    { //This is O(1), whereas Queue.Contains is (n)
        int hash = this._comp == null ? item.GetHashCode() : this._comp.GetHashCode(item);
        return this._hashes.ContainsKey(hash);
    }

    public new void Clear()
    {
        foreach (var item in this._hashes.Values)
            item.Clear(); //clear collision lists

        this._hashes.Clear(); //clear dictionary

        base.Clear(); //clear queue
    }
}

Мой простой тест показывает, что мой HashQueue.Contains() работает намного быстрее, чем Queue.Contains(). Выполнение тестового кода со счетчиком, установленным на 10 000, занимает 0,00045 секунды для версии HashQueue и 0,37 секунды для версии Queue. При подсчете 100 000 версия HashQueue занимает 0,0031 секунды, тогда как очередь занимает 36,38 секунды!

Вот мой тестовый код:

static void Main(string[] args)
{
    int count = 10000;

    { //HashQueue
        var q = new HashQueue<int>(count);

        for (int i = 0; i < count; i++) //load queue (not timed)
            q.Enqueue(i);

        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 0; i < count; i++)
        {
            bool contains = q.Contains(i);
        }
        sw.Stop();
        Console.WriteLine(string.Format("HashQueue, {0}", sw.Elapsed));
    }

    { //Queue
        var q = new Queue<int>(count);

        for (int i = 0; i < count; i++) //load queue (not timed)
            q.Enqueue(i);

        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 0; i < count; i++)
        {
            bool contains = q.Contains(i);
        }
        sw.Stop();
        Console.WriteLine(string.Format("Queue,     {0}", sw.Elapsed));
    }

    Console.ReadLine();
}

SortedList будет выполнять поиск быстрее (но медленнее). вставить элементы)

Почему словарь неуместен?

Чтобы увидеть, есть ли конкретное значение в списке, вам нужно пройтись по всему списку. Со словарем (или другим контейнером на основе хеша) гораздо быстрее сузить количество объектов, с которыми нужно сравнивать. Ключ (в вашем случае число) хэшируется, и это дает словарю дробное подмножество объектов для сравнения.

Я использую это в Compact Framework, где нет поддержки HashSet, я выбрал словарь, где обе строки являются значением, которое я ищу.

Это означает, что я получаю функциональность list‹> с производительностью словаря. Это немного хакерски, но это работает.