Bei zwei gegebenen Werten muss ich herausfinden, ob es ein gemeinsames Element gibt oder nicht, d. h. ob ihre Schnittmenge null ist oder nicht.
Welche der standardmäßigen C # -Sammlungen werden für diesen Zweck am besten (in Bezug auf die Leistung) geeignet sein? Ich weiß, dass linq eine Intersect Erweiterungsmethode hat, um die Schnittmenge zweier Listen / Arrays herauszufinden, aber mein Fokus liegt auf der Leistung in Big-O notation .
Und wenn ich auch die Schnittmenge zweier Sets herausfinden muss?
Nun, wenn Sie die Methode Intersect von LINQ verwenden, wird ein HashSet der zweiten Sequenz aufgebaut und dann jedes Element der ersten Sequenz dagegen geprüft. Also ist es O (M + N) ... und du kannst foo.Intersect(bar).Any() verwenden, um ein frühes Aus zu bekommen.
Wenn Sie einen (entweder) Wert in einem HashSet<T> speichern, um damit zu beginnen, können Sie natürlich einfach über den anderen iterieren, um in jedem Schritt nach Containment zu suchen. Sie müssten trotzdem das Set erstellen, um damit zu beginnen.
Grundsätzlich haben Sie ein O (M + N) -Problem, was auch immer Sie tun - Sie werden nicht billiger werden als das (es gibt immer die Möglichkeit, dass Sie sich ansehen müssen jedes Element) und wenn Ihre Hash-Codes vernünftig sind, sollten Sie in der Lage sein, diese Komplexität leicht zu erreichen. Natürlich können einige Lösungen bessere konstante Faktoren als andere geben ... aber das ist eher Leistung als Komplexität;)
EDIT: Wie in den Kommentaren erwähnt, gibt es auch ISet<T>.Overlaps - Wenn Sie bereits entweder einen statischen Typ von ISet<T> oder eine konkrete Implementierung festgelegt haben, wird durch Aufrufen von Overlaps deutlicher, was Sie tun. Wenn beide Ihrer Sätze statisch als ISet<T> eingegeben werden, verwenden Sie larger.Overlaps(smaller) (wobei größere und kleinere in Bezug auf die Größe der Menge sind), da ich eine Implementierung von Overlaps erwarten würde. iterieren Sie über das Argument und prüfen Sie jedes Element auf den Inhalt des Satzes, auf dem Sie es aufrufen.
Wie bereits erwähnt, erhalten Sie mit Any() eine gewisse Leistung.
Ich habe es an ziemlich großen Datensätzen getestet und es gab 25% Verbesserungen.
Es ist auch sehr wichtig, larger.Intersect(smaller) anstatt das Gegenteil anzuwenden, in meinem Fall hat es 35% Verbesserungen gegeben.
Auch die Reihenfolge der Liste vor dem Anwenden von Schnittpunkt ergab weitere 7-8%.
Beachten Sie auch, dass Sie je nach Anwendungsfall die Anwendung von Schnittpunkt vollständig vermeiden können.
Wenn beispielsweise für eine Integer-Liste das Maximum und das Minimum nicht innerhalb der gleichen Bounders liegen, müssen Sie keine Schnittmenge anwenden, da dies niemals der Fall ist.
Das gleiche gilt für eine String-Liste mit derselben Idee, die auf den ersten Buchstaben angewendet wird.
Versuchen Sie, je nach Ihrem Fall, so viel wie möglich, eine Regel zu finden, bei der es unmöglich ist, eine Kreuzung zu vermeiden.