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

Question

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

Ich habe eine List<long> mit etwa einer Million Zahlen und dem Code, der ständig prüft, ob es eine bestimmte Zahl innerhalb dieser Zahlen gibt.

Ich habe versucht, das Gleiche zu tun mit Dictionary<long, byte> und die Dictionary.ContainsKey() Funktion und war etwa 10-20 Mal schneller als mit der Liste.

Natürlich möchte ich das Wörterbuch nicht wirklich für diesen Zweck verwenden, denn dafür ist es nicht gedacht.

Die eigentliche Frage ist also, ob es eine Alternative zur List<T>.Contains() aber nicht so abgefahren wie Dictionary<K,V>.ContainsKey() ?

Answer 1

A SortierteListe ist schneller bei der Suche (aber langsamer beim Einfügen von Elementen)

Answer 2

Warum ist ein Wörterbuch unangebracht?

Um festzustellen, ob ein bestimmter Wert in der Liste enthalten ist, müssen Sie die gesamte Liste durchgehen. Mit einem Wörterbuch (oder einem anderen Hash-basierten Container) können Sie die Anzahl der Objekte, die Sie vergleichen müssen, viel schneller eingrenzen. Der Schlüssel (in Ihrem Fall die Zahl) wird mit einem Hashwert versehen, der dem Wörterbuch die Teilmenge der zu vergleichenden Objekte liefert.

Answer 3

Ich bin mit diesem in der Compact Framework, wo es keine Unterstützung für HashSet, ich habe für ein Wörterbuch, wo beide Zeichenfolgen sind der Wert, den ich suche entschieden.

Das bedeutet, dass ich eine Liste<>-Funktionalität mit Wörterbuchleistung erhalte. Es ist ein bisschen hakelig, aber es funktioniert.