List <T> .Contains () es muy lento?

¿Alguien podría explicarme por qué la List.Contains()función de los genéricos es tan lenta?

Tengo un número List<long>con aproximadamente un millón de números, y el código que constantemente verifica si hay un número específico dentro de estos números.

Intenté hacer lo mismo usando Dictionary<long, byte>y la Dictionary.ContainsKey()función, y fue entre 10 y 20 veces más rápido que con la Lista.

Por supuesto, realmente no quiero usar Dictionary para ese propósito, porque no estaba destinado a usarse de esa manera.

Entonces, la verdadera pregunta aquí es, ¿hay alguna alternativa al List<T>.Contains(), pero no tan loca como Dictionary<K,V>.ContainsKey()?

Si solo está verificando la existencia, HashSet<T>en .NET 3.5 es su mejor opción: rendimiento similar al de un diccionario, pero sin par clave / valor, solo los 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 es una operación O (n).

Dictionary.ContainsKey es una operación O (1), ya que utiliza el código hash de los objetos como clave, lo que le brinda una capacidad de búsqueda más rápida.

No creo que sea una buena idea tener una lista que contenga un millón de entradas. No creo que la clase List haya sido diseñada para ese propósito. :)

¿No es posible guardar esos millones de entidades en un RDBMS, por ejemplo, y realizar consultas en esa base de datos?

Si no es posible, usaría un diccionario de todos modos.

¡Creo que tengo la respuesta! Sí, es cierto que Contains () en una lista (matriz) es O (n), pero si la matriz es corta y está utilizando tipos de valor, aún debería ser bastante rápido. Pero usando CLR Profiler [descarga gratuita de Microsoft], descubrí que Contains () está encajonando valores para compararlos, lo que requiere una asignación de montón, lo cual es MUY caro (lento). [Nota: esto es .Net 2.0; otras versiones .Net no probadas.]

Aquí está la historia completa y la solución. Tenemos una enumeración llamada "VI" y creamos una clase llamada "ValueIdList" que es un tipo abstracto para una lista (matriz) de objetos VI. La implementación original estaba en los antiguos días .Net 1.1 y usaba una ArrayList encapsulada. Recientemente descubrimos en http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx que una lista genérica (List <VI>) funciona mucho mejor que ArrayList en tipos de valor (como nuestro enum VI) porque los valores no tienen que estar encuadrados. Es cierto y funcionó ... casi.

El CLR Profiler reveló una sorpresa. A continuación, se muestra una parte del gráfico de asignación:

• ValueIdList :: Contiene bool (VI) 5,5 MB (34,81%)
• Lista genérica :: Contiene bool (<DESCONOCIDO>) 5,5 MB (34,81%)
• Generic.ObjectEqualityComparer <T> :: Es igual a bool (<UNKNOWN> <UNKNOWN>) 5.5MB (34.88%)
• Valores.VI 7.7MB (49.03%)

Como puede ver, Contains () llama sorprendentemente a Generic.ObjectEqualityComparer.Equals (), que aparentemente requiere el encajonamiento de un valor VI, lo que requiere una costosa asignación de almacenamiento dinámico. Es extraño que Microsoft elimine el boxeo en la lista, solo para volver a requerirlo para una operación simple como esta.

Nuestra solución fue reescribir la implementación de Contains (), que en nuestro caso fue fácil de hacer ya que ya estábamos encapsulando el objeto de lista genérico (_items). Aquí está el código simple:

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

La comparación de los valores de VI ahora se está haciendo en nuestra propia versión de IndexOf () que no requiere boxing y es muy rápida. Nuestro programa particular se aceleró en un 20% después de esta simple reescritura. O (n) ... ¡no hay problema! ¡Simplemente evite el uso de memoria desperdiciada!

Diccionario no es tan malo, porque las claves en un diccionario están diseñadas para ser encontradas rápidamente. Para encontrar un número en una lista, necesita recorrer toda la lista.

Por supuesto, el diccionario solo funciona si sus números son únicos y no están ordenados.

Creo que también hay una HashSet<T>clase en .NET 3.5, también permite solo elementos únicos.

Una SortedList será más rápida de buscar (pero más lenta para insertar elementos)

Esta no es exactamente una respuesta a su pregunta, pero tengo una clase que aumenta el rendimiento de Contains () en una colección. Subclasé una cola y agregué un diccionario que asigna códigos hash a listas de objetos. La Dictionary.Contains()función es O (1), mientras que List.Contains(), Queue.Contains(), y Stack.Contains()son O (n).

El tipo de valor del diccionario es una cola que contiene objetos con el mismo código hash. El llamador puede proporcionar un objeto de clase personalizado que implemente IEqualityComparer. Puede utilizar este patrón para pilas o listas. El código necesitaría solo unos pocos cambios.

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

Mi prueba simple muestra que mi HashQueue.Contains()funciona mucho más rápido que Queue.Contains(). Ejecutar el código de prueba con un recuento establecido en 10,000 toma 0,00045 segundos para la versión HashQueue y 0.37 segundos para la versión Queue. Con un recuento de 100.000, la versión HashQueue tarda 0,0031 segundos, mientras que la cola tarda 36,38 segundos.

Aquí está mi código de prueba:

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 qué un diccionario es inapropiado?

Para ver si un valor en particular está en la lista, debe recorrer toda la lista. Con un diccionario (u otro contenedor basado en hash) es mucho más rápido reducir la cantidad de objetos con los que necesita comparar. La clave (en su caso, el número) tiene hash y eso le da al diccionario el subconjunto fraccionario de objetos con los que comparar.

Estoy usando esto en Compact Framework donde no hay soporte para HashSet, he optado por un Dictionary donde ambas cadenas son el valor que estoy buscando.

Significa que obtengo la funcionalidad list <> con el rendimiento del diccionario. Es un poco hacky, pero funciona.