In C # wenn ich eine Liste vom Typ bool habe. Wie kann am schnellsten festgestellt werden, ob die Liste einen wahren Wert enthält? Ich muss nicht wissen, wie viele oder wo der wahre Wert ist. Ich muss nur wissen, ob einer existiert. Ich werde viele extrem große Listen suchen.
Verwenden Sie entweder list.Contains (true) oder list.Any (true). Für eine normale Liste haben beide die Komplexität O (n). Da Any () eine Erweiterungsmethode ist, die Delegaten aufrufen muss, ist Contains () möglicherweise noch etwas schneller. Aber ich würde beides einfach mit einer großen Sammlung testen.
Benutze einfach bool trueInList = list.Contains(true); . Dies führt die Liste so lange durch, bis ein true vorhanden ist.
Warum brauchen Sie etwas schneller mit so einem einfachen Anwendungsfall?
Diese Antwort bietet einen anderen Blickwinkel: Warum speichern Sie die Bools in einer Liste? Speichern Sie sie als zwei Ints: int falseCount; int trueCount; .
Enthält Tests ist so einfach wie: trueCount > 0
Angenommen, Sie benötigen die Liste, verwenden Sie List.Contains , da sie das zugrunde liegende Array direkt durchsucht.
Es wäre sogar noch schneller, das zugrundeliegende Array mithilfe von Reflektion zu extrahieren und es in einer fest codierten Vergleichsschleife zu suchen. Sie können dort das Literal true verwenden, um jedes Element zu vergleichen. Sie können sogar die Schleife auflösen oder unsichere Codetricks ausführen.
Dies wird der schnellste Weg sein:
%Vor%Achten Sie auf Antworten mit Linq. Sie werden langsamer sein, wie dieses Testprogramm zeigt (in der Tat ist der Linq mehr als 12 mal langsamer!
Dies zeigt auch, dass (zumindest auf meinem System) die handcodierte Schleife etwa 3,5 mal schneller ist als List.Contains() .
Ergebnisse auf meinem PC (Windows 8 x64, Programm nach x86 kompiliert)
%Vor%Ich habe das auf verschiedenen Systemen getestet, darunter einen 5 Jahre alten Laptop mit XP und einen neuen PC mit Windows 8, mit ähnlichen Ergebnissen.
(Vergiss nicht, deine Timings von einem RELEASE Build zu machen.)
%Vor% Also, warum in aller Welt wäre List.Contains() langsamer? Nun, lassen Sie uns Reflektor verwenden, um seine Implementierung zu sehen:
Aha! Alles ist offenbart! Es ruft comparer.Equals() für jedes Element auf. Kein Wunder, dass es langsamer ist!
Zwei weitere Dinge, die ich erwähnen möchte:
BitArray schreiben, wo Sie die Bools als Bits in 32-Bit-Unsigned-Ints speichern. Dann könntest du wirklich durch sie hindurchgehen, indem du 32 Bits gleichzeitig mit einem einfachen != 0 auf jeder Uinta prüfst.