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

89

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()?

DSent
quelle
2
Welches Problem mit Dictionary? Es ist für den Fall wie Ihres vorgesehen.
Kamarey
4
@Kamarey: HashSet ist möglicherweise eine bessere Option.
Brian Rasmussen
HashSet ist das, wonach ich gesucht habe.
DSent

Antworten:

156

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
Marc Gravell
quelle
30

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.

Frederik Gheysels
quelle
13
Ich glaube nicht, dass eine Liste mit einer Million Elementen etwas Unangemessenes enthält. Es ist nur so, dass Sie wahrscheinlich keine linearen Suchvorgänge mehr durchführen möchten.
Will Dean
Einverstanden, es ist nichts falsch an einer Liste oder einem Array mit so vielen Einträgen. Scannen Sie einfach nicht nach Werten.
Michael Krauklis
8

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!

Kevin North
quelle
Vielen Dank für den Tipp, ich wurde selbst von einer schlechten Boxleistung erwischt. Eine benutzerdefinierte ContainsImplementierung ist für meinen Anwendungsfall viel schneller.
Lea Hayes
5

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.

Stefan Steinegger
quelle
Ein Wörterbuch <Typ, Ganzzahl> kann auch nicht eindeutige Objekte effektiv speichern. Verwenden Sie die Ganzzahl, um die Anzahl der Duplikate zu zählen. Zum Beispiel würden Sie die Liste {a, b, a} als {a = 2, b = 1} speichern. Es verliert natürlich die Ordnung.
MSalters
2

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

Mitch Wheat
quelle
2

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();
}
user2023861
quelle
Ich habe gerade den dritten Testfall für HashSet <T> hinzugefügt, der noch bessere Ergebnisse zu erzielen scheint als Ihre Lösung: HashQueue, 00:00:00.0004029 Queue, 00:00:00.3901439 HashSet, 00:00:00.0001716
Psulek
1

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.

Andrew
quelle
0

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.

Mark McGookin
quelle
1
Wenn Sie ein Wörterbuch anstelle eines HashSet verwenden, können Sie den Wert auch auf "" setzen und nicht auf dieselbe Zeichenfolge wie der Schlüssel. Auf diese Weise benötigen Sie weniger Speicher. Alternativ können Sie auch Dictionary <string, bool> verwenden und alle auf true (oder false) setzen. Ich weiß nicht, welche weniger Speicher, eine leere Zeichenfolge oder einen Bool benötigen würden. Meine Vermutung wäre bool.
TTT
Im Wörterbuch machen eine stringReferenz und ein boolWert einen Unterschied von 3 oder 7 Bytes für 32- bzw. 64-Bit-Systeme. Beachten Sie jedoch, dass die Größe jedes Eintrags auf ein Vielfaches von 4 bzw. 8 aufgerundet wird. Die Wahl zwischen stringund macht boolsomit möglicherweise überhaupt keinen Unterschied in der Größe. Die leere Zeichenfolge ""ist im Speicher immer bereits als statische Eigenschaft vorhanden string.Empty, sodass es keinen Unterschied macht, ob Sie sie im Wörterbuch verwenden oder nicht. (Und es wird sowieso woanders verwendet.)
Wormbo