Список<t>.Contains() очень медленный?

Ответ 1

Если вы просто проверяете существование, 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

Ответ 2

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

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

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

Возможно ли сохранить эти миллионные объекты в RDBMS, например, и выполнить запросы в этой базе данных?

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

Ответ 3

Думаю, у меня есть ответ! Да, верно, что 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 в типах значений (например, наше перечисление VI), потому что значения don ' t должен быть помещен в коробку. Это правда, и это сработало... почти.

Профайлер CLR показал удивление. Здесь часть графика распределения:

• ValueIdList:: Содержит bool (VI) 5.5MB (34.81%)
• Generic.List:: Содержит bool (<UNKNOWN> ) 5.5MB (34.81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool (<UNKNOWN> <UNKNOWN> ) 5,5 МБ (34,88%)
• Значения .VI 7.7MB (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% после этой простой перезаписи. O (n)... не проблема! Просто избегайте использования использованной памяти!

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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