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

Может ли кто-нибудь объяснить мне, почему List.Contains()функция дженериков такая медленная?

У меня есть List<long>около миллиона номеров, и код, который постоянно проверяет, есть ли конкретное число в этих числах.

Я пробовал делать то же самое, используя Dictionary<long, byte>и Dictionary.ContainsKey()функцию, и это было примерно в 10-20 раз быстрее, чем со списком.

Конечно, я действительно не хочу использовать Dictionary для этой цели, потому что он не предназначен для этого.

Итак, настоящий вопрос здесь в том, есть ли альтернатива List<T>.Contains(), но не такая уж дурацкая, как Dictionary<K,V>.ContainsKey()?

Если вы просто проверяете существование, 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 days, и в ней использовался инкапсулированный 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 :: Содержит bool (<UNKNOWN>) 5,5 МБ (34,81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool (<UNKNOWN> <UNKNOWN>) 5,5 МБ (34,88%)
• Values.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% после этой простой перезаписи. О (п) ... нет проблем! Просто избегайте бесполезного использования памяти!

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

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

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

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

Это не совсем ответ на ваш вопрос, но у меня есть класс, который увеличивает производительность Contains () для коллекции. Я разделил очередь на подклассы и добавил словарь, который отображает хэш-коды в списки объектов. Dictionary.Contains()Функция О (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(). Выполнение тестового кода со значением count, равным 10 000, занимает 0,00045 секунды для версии HashQueue и 0,37 секунды для версии Queue. При количестве 100000 версия HashQueue занимает 0,0031 секунды, тогда как Queue занимает 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();
}

Почему словарь не подходит?

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

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

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