wake-up-neo.net

Die effizienteste Methode, um herauszufinden, ob ein Wert in einer C # -Liste vorhanden ist

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 liegt. Ich muss nur wissen, ob einer existiert. Ich werde viele extrem große Listen durchsuchen.

12
Aaron Benzel

Verwenden Sie entweder list.Contains (true) oder list.Any (true) . Für eine normale Liste haben beide die Komplexität O (n). Da Any () jedoch eine Erweiterungsmethode ist, die Delegaten aufrufen muss, ist Contains () möglicherweise noch etwas schneller. Um sicher zu sein, würde ich beides einfach mit einer großen Sammlung testen.

7
treze

Verwenden Sie einfach bool trueInList = list.Contains(true);. Die Liste wird so lange durchlaufen, bis eine true vorhanden ist.

Warum brauchen Sie etwas schneller mit einem so einfachen Anwendungsfall?

20
Rango

Sie könnten Any () verwenden.

list.Any(b => b);
5
user707727

Versuche dies:

var result = myBoolList.Any(i => i==true);

Dies wird der schnellste Weg sein:

static bool AnySet(List<bool> data)
{
    for (int i = 0; i < data.Count; ++i)
        if (data[i])
            return true;

    return false;
}

Hüte dich vor Antworten mit Linq. Sie werden langsamer sein, wie dieses Testprogramm zeigt (tatsächlich ist der Linq mehr als 12-mal langsamer!)

Dies zeigt auch, dass (zumindest in 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)

Times in seconds

01.0994496 data.Any() list
01.1147795 data.Any() enumerable
00.1215951 hand-rolled loop
00.4240996 list.Contains()

Ich habe dies auf mehreren Systemen getestet, darunter einem 5 Jahre alten Laptop mit XP und einem neuen PC mit Windows 8, mit ähnlichen Ergebnissen.

(Vergiss nicht, deine Timings von einem RELEASE-Build zu machen.)

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication1
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            int size = 10000000;
            int count = 10;
            List<bool> data = new List<bool>(size);

            for (int i = 0; i < size; ++i)
                data.Add(false);

            var sw = Stopwatch.StartNew();

            for (int trial = 0; trial < 5; ++trial)
            {
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    AnySet1(data);

                Console.WriteLine(sw.Elapsed + " data.Any() list");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    AnySet2(data);

                Console.WriteLine(sw.Elapsed + " data.Any() enumerable");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    AnySet3(data);

                Console.WriteLine(sw.Elapsed + " hand-rolled loop");
                sw.Restart();

                for (int i = 0; i < count; ++i)
                    AnySet4(data);

                Console.WriteLine(sw.Elapsed + " list.Contains()");

                Console.WriteLine();
            }
        }

        static bool AnySet1(List<bool> data)
        {
            return data.Any(b => b);
        }

        static bool AnySet2(IEnumerable<bool> data)
        {
            return data.Any(b => b);
        }

        static bool AnySet3(List<bool> data)
        {
            for (int i = 0; i < data.Count; ++i)
                if (data[i])
                    return true;

            return false;
        }

        static bool AnySet4(List<bool> data)
        {
            return data.Contains(true);
        }
    }
}

Warum sollte List.Contains() langsamer sein? Nun, verwenden wir den Reflektor, um die Implementierung zu betrachten:

bool Contains(T item)
{
    if (item == null)
    {
        for (int j = 0x0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    EqualityComparer<T> comparer = EqualityComparer<T>.Default;
    for (int i = 0x0; i < this._size; i++)
    {
        if (comparer.Equals(this._items[i], item))
        {
            return true;
        }
    }
    return false;
}

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:

  • Wenn Sie wirklich maximale Geschwindigkeit wünschen, sollten Sie ein einfaches Array anstelle einer Liste verwenden.
  • Für die maximal mögliche Geschwindigkeit können Sie eine eigene Version einer BitArray schreiben, in der Sie die Bools als Bits in 32-Bit-Bits ohne Vorzeichen speichern. Dann könnten Sie wirklich durchgehen und jeweils 32 Bits mit einem einfachen != 0 bei jedem Uint überprüfen.
2
Matthew Watson

Sie verwenden die Any(...)

list.Any(c => c == true);

oder nur

list.Any(c => c);
1
Jens Kloster

Diese Antwort bietet einen anderen Blickwinkel: Warum werden die Bools in einer Liste gespeichert? Speichern Sie sie als zwei Ints: int falseCount; int trueCount;.

Enthält das Testen so einfach wie: trueCount > 0

Angenommen, Sie benötigen die Liste, verwenden Sie List.Contains, da das darunterliegende Array direkt durchsucht wird.

Noch schneller wäre es, das zugrunde liegende Array mit Reflektion zu extrahieren und in einer hart codierten Vergleichsschleife zu suchen. Sie können dort das Literal true verwenden, um jedes Element zu vergleichen. Sie können sogar die Schleife abrollen oder unsichere Code-Tricks ausführen.

1
usr
bool val = false;
Foreach(bool val in listofvalue)
{
   val |= val;
}

if(val)
print "List contain true value"

else

print "List contain false value"
0
vikky

Sie können die BinarySearch-Methode der Liste verwenden.

if(list.BinarySearch(true) > 0){...}
0
Saeed