List <T> .Contains () é muito lento?

Alguém poderia me explicar por que a List.Contains()função dos genéricos é tão lenta?

Eu tenho um List<long>com cerca de um milhão de números e o código que verifica constantemente se há um número específico dentro desses números.

Tentei fazer a mesma coisa usando Dictionary<long, byte>e a Dictionary.ContainsKey()função, e foi cerca de 10-20 vezes mais rápido do que com o List.

Claro, eu realmente não quero usar o Dicionário para esse propósito, porque ele não foi feito para ser usado dessa forma.

Portanto, a verdadeira questão aqui é: há alguma alternativa para o List<T>.Contains(), mas não tão maluco quanto Dictionary<K,V>.ContainsKey()?

Se você está apenas verificando a existência, HashSet<T>no .NET 3.5 é sua melhor opção - desempenho semelhante a um dicionário, mas nenhum par chave / valor - apenas os valores:

    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 é uma operação O (n).

Dictionary.ContainsKey é uma operação O (1), pois usa o código hash dos objetos como uma chave, o que lhe dá uma capacidade de pesquisa mais rápida.

Não acho que seja uma boa ideia ter uma lista que contenha um milhão de entradas. Não acho que a classe List tenha sido projetada para esse propósito. :)

Não é possível salvar essas entidades millon em um RDBMS, por exemplo, e realizar consultas nesse banco de dados?

Se não for possível, eu usaria um Dicionário de qualquer maneira.

Acho que tenho a resposta! Sim, é verdade que Contains () em uma lista (array) é O (n), mas se o array for curto e você estiver usando tipos de valor, ainda assim deverá ser bastante rápido. Mas usando o CLR Profiler [download gratuito da Microsoft], descobri que Contains () está encaixotando valores para compará-los, o que requer alocação de heap, o que é MUITO caro (lento). [Nota: Este é .Net 2.0; outras versões .Net não testadas.]

Aqui está a história completa e a solução. Temos uma enumeração chamada "VI" e criamos uma classe chamada "ValueIdList", que é um tipo abstrato para uma lista (array) de objetos VI. A implementação original estava nos antigos dias .Net 1.1 e usava uma ArrayList encapsulada. Descobrimos recentemente em http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx que uma lista genérica (List <VI>) tem um desempenho muito melhor do que ArrayList em tipos de valor (como nosso enum VI) porque os valores não precisam ser encaixotados. É verdade e funcionou ... quase.

O CLR Profiler revelou uma surpresa. Aqui está uma parte do gráfico de alocação:

• ValueIdList :: Contém bool (VI) 5,5 MB (34,81%)
• Generic.List :: Contém bool (<UNKNOWN>) 5,5 MB (34,81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool (<UNKNOWN> <UNKNOWN>) 5,5 MB (34,88%)
• Values.VI 7,7 MB (49,03%)

Como você pode ver, Contains () chama surpreendentemente Generic.ObjectEqualityComparer.Equals (), que aparentemente requer o encaixotamento de um valor VI, o que requer uma alocação de heap cara. É estranho que a Microsoft tenha eliminado o boxing da lista, apenas para exigi-lo novamente para uma operação simples como essa.

Nossa solução foi reescrever a implementação de Contains (), o que em nosso caso foi fácil de fazer, pois já estávamos encapsulando o objeto de lista genérica (_items). Aqui está o código simples:

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;
}

A comparação dos valores de VI agora está sendo feita em nossa própria versão de IndexOf (), que não requer boxing e é muito rápida. Nosso programa específico aumentou 20% após essa simples reescrita. O (n) ... sem problemas! Apenas evite o desperdício de memória!

O dicionário não é tão ruim, porque as chaves em um dicionário são projetadas para serem encontradas rapidamente. Para localizar um número em uma lista, ele precisa iterar por toda a lista.

É claro que o dicionário só funciona se seus números forem exclusivos e não ordenados.

Acho que também existe uma HashSet<T>classe no .NET 3.5, que também permite apenas elementos únicos.

Uma SortedList será mais rápida para pesquisar (mas mais lenta para inserir itens)

Esta não é exatamente uma resposta à sua pergunta, mas tenho uma classe que aumenta o desempenho de Contains () em uma coleção. Criei uma subclasse de Fila e adicionei um Dicionário que mapeia códigos hash para listas de objetos. A Dictionary.Contains()função é O (1) enquanto List.Contains(),Queue.Contains() , e Stack.Contains()são O (n).

O tipo de valor do dicionário é uma fila contendo objetos com o mesmo código hash. O chamador pode fornecer um objeto de classe personalizado que implementa IEqualityComparer. Você pode usar esse padrão para pilhas ou listas. O código precisaria de apenas algumas alterações.

/// <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
    }
}

Meu teste simples mostra que minha HashQueue.Contains()execução é muito mais rápida do queQueue.Contains() . A execução do código de teste com contagem definida para 10.000 leva 0,00045 segundos para a versão HashQueue e 0,37 segundos para a versão Fila. Com uma contagem de 100.000, a versão HashQueue leva 0,0031 segundos, enquanto a Fila leva 36,38 segundos!

Este é meu código de teste:

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();
}

Por que um dicionário é impróprio?

Para ver se um determinado valor está na lista, você precisa percorrer a lista inteira. Com um dicionário (ou outro contêiner baseado em hash) é muito mais rápido restringir o número de objetos com os quais você precisa comparar. A chave (no seu caso, o número) é hash e isso dá ao dicionário o subconjunto fracionário de objetos para comparação.

Estou usando isso no Compact Framework, onde não há suporte para HashSet, optei por um Dicionário onde ambas as strings são o valor que estou procurando.

Significa que obtenho a funcionalidade list <> com desempenho de dicionário. É um pouco hacky, mas funciona.