В C#, Список.Содержит() - слишком медленно?

список.Содержит операцию O(n).

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

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

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

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

Я думаю, что у меня есть ответ! Да, это правда, что Contains () в списке (массиве) - O(n), но если массив короткий и вы используете типы значений, он все равно должен быть довольно быстрым. Но с помощью профилировщика CLR [скачать бесплатно от 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) работает намного лучше, чем ArrayList на типах значений (например, наше перечисление VI), потому что значения не должны быть упакованы. Это правда и это работал... почти.

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

• ValueIdList:: содержит bool (VI) 5.5 MB (34.81%)
• универсальный.Список:: содержит bool () 5.5 MB (34.81%)
• универсальный.ObjectEqualityComparer:: Equals bool () 5.5 MB (34.88%)
• Values.VI 7,7 МБ (49,03%)

Как вы можете видеть, содержит () удивительно вызовы Родовой.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% после этого простого перезаписи. O (n)... без проблем! Просто избегайте впустую использования памяти!

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

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

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

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

это не совсем ответ на ваш вопрос, но у меня есть класс, который увеличивает производительность содержит() на коллекции. Я подкласс очереди и добавил словарь, который отображает хэш-коды в списки объектов. Элемент 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 секунды для версии очереди. При количестве 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();
}

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

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

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

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