List <T> .Contains () est très lent?

Quelqu'un pourrait-il m'expliquer pourquoi la List.Contains()fonction générique est si lente?

J'ai un List<long>avec environ un million de nombres, et le code qui vérifie constamment s'il y a un nombre spécifique dans ces nombres.

J'ai essayé de faire la même chose en utilisant Dictionary<long, byte>et la Dictionary.ContainsKey()fonction, et c'était environ 10 à 20 fois plus rapide qu'avec la liste.

Bien sûr, je ne veux pas vraiment utiliser Dictionary dans ce but, car il n'était pas destiné à être utilisé de cette façon.

Donc, la vraie question ici est, y a-t-il une alternative au List<T>.Contains(), mais pas aussi farfelue que Dictionary<K,V>.ContainsKey()?

Si vous ne faites que vérifier l'existence, HashSet<T>dans .NET 3.5 est votre meilleure option - des performances de type dictionnaire, mais pas de paire clé / valeur - juste les valeurs:

    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 est une opération O (n).

Dictionary.ContainsKey est une opération O (1), car elle utilise le hashcode des objets comme clé, ce qui vous donne une capacité de recherche plus rapide.

Je ne pense pas que ce soit une bonne idée d 'avoir une liste contenant un million d' entrées. Je ne pense pas que la classe List ait été conçue à cet effet. :)

N'est-il pas possible de sauvegarder ces entités millon dans un SGBDR par exemple, et d'effectuer des requêtes sur cette base de données?

Si ce n'est pas possible, j'utiliserais de toute façon un dictionnaire.

Je pense avoir la réponse! Oui, il est vrai que Contains () sur une liste (tableau) est O (n), mais si le tableau est court et que vous utilisez des types valeur, cela devrait quand même être assez rapide. Mais en utilisant le CLR Profiler [téléchargement gratuit de Microsoft], j'ai découvert que Contains () boxe les valeurs afin de les comparer, ce qui nécessite une allocation de tas, ce qui est TRÈS cher (lent). [Remarque: il s'agit de .Net 2.0; autres versions .Net non testées.]

Voici l'histoire complète et la solution. Nous avons une énumération appelée "VI" et avons créé une classe appelée "ValueIdList" qui est un type abstrait pour une liste (tableau) d'objets VI. L'implémentation d'origine était dans les anciens jours de .Net 1.1, et elle utilisait une ArrayList encapsulée. Nous avons découvert récemment dans http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx qu'une liste générique (List <VI>) fonctionne bien mieux que ArrayList sur les types valeur (comme notre enum VI) car les valeurs n'ont pas à être encadrées. C'est vrai et ça a marché ... presque.

Le CLR Profiler a révélé une surprise. Voici une partie du graphique d'allocation:

• ValueIdList :: Contient un booléen (VI) 5,5 Mo (34,81%)
• Generic.List :: Contient un booléen (<UNKNOWN>) 5,5 Mo (34,81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool (<UNKNOWN> <UNKNOWN>) 5,5 Mo (34,88%)
• Valeurs: VI 7,7 Mo (49,03%)

Comme vous pouvez le voir, Contains () appelle de manière surprenante Generic.ObjectEqualityComparer.Equals (), qui nécessite apparemment l'encadrement d'une valeur de VI, ce qui nécessite une allocation de tas coûteuse. Il est étrange que Microsoft supprime la boxe de la liste, seulement pour l'exiger à nouveau pour une opération simple comme celle-ci.

Notre solution était de réécrire l'implémentation Contains (), ce qui dans notre cas était facile à faire puisque nous encapsulions déjà l'objet liste générique (_items). Voici le code 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 comparaison des valeurs de VI se fait maintenant dans notre propre version d'IndexOf () qui ne nécessite aucune boxe, et c'est très rapide. Notre programme particulier a accéléré de 20% après cette simple réécriture. O (n) ... pas de problème! Évitez simplement le gaspillage de la mémoire!

Le dictionnaire n'est pas si mal, car les clés d'un dictionnaire sont conçues pour être trouvées rapidement. Pour trouver un numéro dans une liste, il doit parcourir toute la liste.

Bien sûr, le dictionnaire ne fonctionne que si vos numéros sont uniques et non classés.

Je pense qu'il y a aussi une HashSet<T>classe dans .NET 3.5, elle n'autorise également que des éléments uniques.

Une SortedList sera plus rapide à rechercher (mais plus lente à insérer des éléments)

Ce n'est pas exactement une réponse à votre question, mais j'ai une classe qui augmente les performances de Contains () sur une collection. J'ai sous-classé une file d'attente et ajouté un dictionnaire qui mappe les codes de hachage aux listes d'objets. La Dictionary.Contains()fonction est O (1) tandis que List.Contains(), Queue.Contains()et Stack.Contains()sont O (n).

Le type de valeur du dictionnaire est une file d'attente contenant des objets avec le même hashcode. L'appelant peut fournir un objet de classe personnalisé qui implémente IEqualityComparer. Vous pouvez utiliser ce modèle pour les piles ou les listes. Le code n'aurait besoin que de quelques modifications.

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

Mes tests simples montrent que mes HashQueue.Contains()courses sont beaucoup plus rapides que Queue.Contains(). L'exécution du code de test avec un nombre défini sur 10 000 prend 0,00045 secondes pour la version HashQueue et 0,37 seconde pour la version Queue. Avec un nombre de 100 000, la version HashQueue prend 0,0031 seconde alors que la file d'attente prend 36,38 secondes!

Voici mon code de test:

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

Pourquoi un dictionnaire est-il inapproprié?

Pour voir si une valeur particulière figure dans la liste, vous devez parcourir toute la liste. Avec un dictionnaire (ou un autre conteneur basé sur le hachage), il est beaucoup plus rapide de réduire le nombre d'objets à comparer. La clé (dans votre cas, le nombre) est hachée et cela donne au dictionnaire le sous-ensemble fractionnaire d'objets à comparer.

J'utilise ceci dans le cadre compact où il n'y a pas de support pour HashSet, j'ai opté pour un dictionnaire où les deux chaînes sont la valeur que je recherche.

Cela signifie que j'obtiens la fonctionnalité de liste <> avec les performances du dictionnaire. C'est un peu hacky, mais ça marche.