C #, liste <T> .Contains () - trop lent?

Question

Quelqu'un pourrait-il m'expliquer pourquoi les génériques de la liste de la fonction contains() est-elle si lente?
J'ai une Liste avec environ un million de nombres, et le code qui est constamment vérifier si il y a un nombre spécifique au sein de ces numéros.
J'ai essayé de faire la même chose en utilisant le Dictionnaire et la ContainsKey() de la fonction, et il était d'environ 10 à 20 fois plus rapide qu'avec la Liste.
Bien sûr, je n'ai pas vraiment envie d'utiliser le Dictionnaire pour la fin, car il n'était pas destiné à être utilisé de cette façon.
Donc, la vraie question ici est, est-il une alternative à la Liste.Contient du (de la), mais pas aussi déjanté que Dictionnaire.ContainsKey() ?
Merci à l'avance!

Answer 1

Si vous ne faites que vérifier l'existence, HashSet<T> dans .NET 3.5 est votre meilleure option - performances similaires à celles d'un dictionnaire, mais pas de paire clé / valeur - uniquement 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
 

Answer 2

Liste.Contient est un O(n) opérations.

De dictionnaire.ContainsKey est un O(1), car il utilise le hashcode de la des objets comme des clés, ce qui vous donne une plus rapide de la capacité de recherche.

Je ne pense pas que c'est une bonne idée d'avoir une Liste qui contient un million d'entrées. Je ne pense pas que la Liste de la classe a été conçu à cet effet. :)

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

Si il n'est pas possible, alors je voudrais utiliser un Dictionnaire de toute façon.

Answer 3

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

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

Je pense qu’il existe également une classe HashSet<T> dans .NET 3.5, elle ne permet également que des éléments uniques.

Answer 4

Ce n'est pas exactement la réponse à votre question, mais j'ai une classe qui augmente les performances de Contains() sur une collection. Je sous-classé une File d'attente et l'ajout d'un Dictionnaire de cartes hashcodes à des listes d'objets. L' Dictionary.Contains() fonction est en O(1) considérant que l' List.Contains(), Queue.Contains(), et Stack.Contains() O(n).

Le type de donnée du dictionnaire est une file d'attente contenant des objets avec le même hashcode. L'appelant peut fournir une classe personnalisée objet qui implémente IEqualityComparer. Vous pouvez utiliser ce modèle pour les Piles ou les Listes. Le code aurait besoin 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
    }
}

Mon test simple montre que mes HashQueue.Contains() tourne beaucoup plus vite que Queue.Contains(). Exécution du test de code avec un nombre fixé à 10 000 prend 0.00045 secondes pour le HashQueue version et 0,37 secondes pour la File d'attente de la version. Avec un nombre de 100 000, la HashQueue version prend 0.0031 secondes tandis 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();
}

Answer 5

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