Liste <T> .Contains () ist sehr langsam?

Kann mir jemand erklären, warum die Generika- List.Contains()Funktion so langsam ist?

Ich habe eine List<long>mit ungefähr einer Million Nummern und den Code, der ständig überprüft, ob diese Nummern eine bestimmte Nummer enthalten.

Ich habe versucht, dasselbe mit Dictionary<long, byte>und der Dictionary.ContainsKey()Funktion zu tun , und es war ungefähr 10-20 Mal schneller als mit der Liste.

Natürlich möchte ich Dictionary nicht wirklich für diesen Zweck verwenden, da es nicht so verwendet werden sollte.

Die eigentliche Frage hier ist also, gibt es eine Alternative zu der List<T>.Contains(), aber nicht so verrückten wie Dictionary<K,V>.ContainsKey()?

Wenn Sie nur nach Existenz suchen, ist HashSet<T>in .NET 3.5 die beste Option - wörterbuchähnliche Leistung, aber kein Schlüssel / Wert-Paar - nur die Werte:

    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 ist eine O (n) -Operation.

Dictionary.ContainsKey ist eine O (1) -Operation, da der Hashcode der Objekte als Schlüssel verwendet wird, wodurch Sie schneller suchen können.

Ich denke nicht, dass es eine gute Idee ist, eine Liste zu haben, die eine Million Einträge enthält. Ich glaube nicht, dass die List-Klasse für diesen Zweck entwickelt wurde. :) :)

Ist es nicht möglich, diese Millon-Entitäten beispielsweise in einem RDBMS zu speichern und Abfragen in dieser Datenbank durchzuführen?

Wenn es nicht möglich ist, würde ich trotzdem ein Wörterbuch verwenden.

Ich glaube ich habe die Antwort! Ja, es stimmt, dass Contains () in einer Liste (Array) O (n) ist. Wenn das Array jedoch kurz ist und Sie Werttypen verwenden, sollte es dennoch recht schnell sein. Mit dem CLR-Profiler [kostenloser Download von Microsoft] stellte ich jedoch fest, dass Contains () Boxwerte enthält, um sie zu vergleichen. Dies erfordert eine Heap-Zuweisung, die SEHR teuer (langsam) ist. [Hinweis: Dies ist .Net 2.0; andere .Net-Versionen nicht getestet.]

Hier ist die ganze Geschichte und Lösung. Wir haben eine Aufzählung namens "VI" und eine Klasse namens "ValueIdList" erstellt, die ein abstrakter Typ für eine Liste (ein Array) von VI-Objekten ist. Die ursprüngliche Implementierung war in den alten .Net 1.1-Tagen und es wurde eine gekapselte ArrayList verwendet. Wir haben kürzlich in http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx festgestellt, dass eine generische Liste (List <VI>) bei Werttypen (wie unserer) eine viel bessere Leistung als ArrayList aufweist Aufzählung VI), da die Werte nicht eingerahmt werden müssen. Es ist wahr und es hat funktioniert ... fast.

Der CLR-Profiler zeigte eine Überraschung. Hier ist ein Teil des Zuordnungsdiagramms:

• ValueIdList :: Enthält Bool (VI) 5,5 MB (34,81%)
• Generic.List :: Enthält Bool (<UNKNOWN>) 5,5 MB (34,81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool (<UNKNOWN> <UNKNOWN>) 5,5 MB (34,88%)
• Werte.VI 7,7 MB (49,03%)

Wie Sie sehen können, ruft Contains () überraschenderweise Generic.ObjectEqualityComparer.Equals () auf, was anscheinend das Boxen eines VI-Werts erfordert, was eine teure Heap-Zuweisung erfordert. Es ist seltsam, dass Microsoft das Boxen auf der Liste eliminieren würde, nur um es für eine einfache Operation wie diese erneut zu benötigen.

Unsere Lösung bestand darin, die Implementierung von Contains () neu zu schreiben, was in unserem Fall einfach war, da wir das generische Listenobjekt (_items) bereits gekapselt hatten. Hier ist der einfache Code:

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

Der Vergleich der VI-Werte wird jetzt in unserer eigenen Version von IndexOf () durchgeführt, die kein Boxen erfordert und sehr schnell ist. Unser spezielles Programm hat sich nach diesem einfachen Umschreiben um 20% beschleunigt. O (n) ... kein Problem! Vermeiden Sie einfach die verschwendete Speichernutzung!

Das Wörterbuch ist nicht so schlecht, weil die Schlüssel in einem Wörterbuch so konzipiert sind, dass sie schnell gefunden werden können. Um eine Nummer in einer Liste zu finden, muss die gesamte Liste durchlaufen werden.

Natürlich funktioniert das Wörterbuch nur, wenn Ihre Nummern eindeutig und nicht geordnet sind.

Ich denke, es gibt auch eine HashSet<T>Klasse in .NET 3.5, die auch nur eindeutige Elemente zulässt.

Eine SortedList ist schneller zu suchen (aber langsamer zum Einfügen von Elementen)

Dies ist nicht gerade eine Antwort auf Ihre Frage, aber ich habe eine Klasse, die die Leistung von Contains () für eine Sammlung erhöht. Ich habe eine Warteschlange untergeordnet und ein Wörterbuch hinzugefügt, das Hashcodes Listen von Objekten zuordnet. Die Dictionary.Contains()Funktion O (1) , während List.Contains(), Queue.Contains()und Stack.Contains()ist O (n).

Der Werttyp des Wörterbuchs ist eine Warteschlange, die Objekte mit demselben Hashcode enthält. Der Aufrufer kann ein benutzerdefiniertes Klassenobjekt bereitstellen, das IEqualityComparer implementiert. Sie können dieses Muster für Stapel oder Listen verwenden. Der Code würde nur ein paar Änderungen benötigen.

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

Meine einfachen Tests zeigen, dass meine HashQueue.Contains()viel schneller läuft als Queue.Contains(). Das Ausführen des Testcodes mit einer Anzahl von 10.000 dauert 0,00045 Sekunden für die HashQueue-Version und 0,37 Sekunden für die Queue-Version. Bei einer Anzahl von 100.000 dauert die HashQueue-Version 0,0031 Sekunden, während die Warteschlange 36,38 Sekunden benötigt!

Hier ist mein Testcode:

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

Warum ist ein Wörterbuch unangemessen?

Um festzustellen, ob ein bestimmter Wert in der Liste enthalten ist, müssen Sie die gesamte Liste durchlaufen. Mit einem Wörterbuch (oder einem anderen Hash-basierten Container) können Sie die Anzahl der Objekte, mit denen Sie vergleichen müssen, viel schneller eingrenzen. Der Schlüssel (in Ihrem Fall die Zahl) ist gehasht und gibt dem Wörterbuch die Teilmenge der Objekte, mit denen verglichen werden soll.

Ich verwende dies im Compact Framework, wo HashSet nicht unterstützt wird. Ich habe mich für ein Wörterbuch entschieden, bei dem beide Zeichenfolgen der gesuchte Wert sind.

Dies bedeutet, dass ich Listenfunktionalität mit Wörterbuchleistung erhalte. Es ist ein bisschen hacky, aber es funktioniert.