schneiden und irgendwelche oder enthält und irgendwelche. Welches ist effizienter, um mindestens ein gemeinsames Element zu finden?

Question

Wenn ich zwei Liste habe, und ich möchte wissen, ob es mindestens ein gemeinsames Element ist, habe ich diese zwei Möglichkeiten:

lst1.Intersect(lst2).Any(); 

Lst1.Any(x => lst2.Contains(x)); 

Die beiden Optionen geben Sie mir das Ergebnis, das ich erwarte, aber ich nicht wissen, was die beste Option ist. Was ist effizienter? Und warum?

Danke.

EDIT: als ich diesen Beitrag erstellt, abgesehen von der Lösung, suchte ich den Grund. Ich weiß, dass ich Tests durchführen kann, aber ich würde den Grund des Ergebnisses nicht wissen. Einer ist schneller als der andere? Ist immer eine Lösung die beste?

Aus diesem Grund habe ich die Antwort von Matthew akzeptiert, nicht nur für den Testcode, sondern er erklärt auch, wenn einer besser ist als andere und warum. Ich schätze auch die Beiträge von Nicholas und Oren sehr.

Danke.

Answer 1

Orens Antwort weist einen Fehler bei der Verwendung der Stoppuhr auf. Es wird am Ende der Schleife nicht zurückgesetzt, nachdem die Zeit Any() gemessen wurde.

Hinweis, wie es zu Beginn der Schleife geht zurück mit der Stoppuhr nie Reset() so zu sein, dass die Zeit, den intersect hinzugefügt wird umfasst die von Any() Zeit genommen.

Folgendes ist eine korrigierte Version.

Ein Release-Build außerhalb jeden Debugger gibt dieses Ergebnis auf meinem PC laufen:

Intersect: 1ms 
Any:  6743ms 

Hinweis, wie ich für diesen Test zwei nicht überlappende Stringlisten zu machen. Beachten Sie auch, dass dies ein Worst-Case-Test ist.

Wo viele Schnittpunkte (oder Schnittpunkte, die in der Nähe des Anfanges der Daten auftreten) auftreten, ist Oren ganz richtig zu sagen, dass Any() schneller sein sollte. Wenn die echten Daten normalerweise Kreuzungen enthalten, ist es wahrscheinlich besser, Any() zu verwenden. Andernfalls verwenden Sie Intersect(). Es ist sehr datenabhängig.

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

namespace Demo 
{ 
    class Program 
    { 
     void run() 
     { 
      double intersect = 0; 
      double any = 0; 

      Stopwatch stopWatch = new Stopwatch(); 

      List<string> L1 = Enumerable.Range(0, 10000).Select(x => x.ToString()).ToList(); 
      List<string> L2 = Enumerable.Range(10000, 10000).Select(x => x.ToString()).ToList(); 

      for (int i = 0; i < 10; i++) 
      { 
       stopWatch.Restart(); 
       Intersect(L1, L2); 
       stopWatch.Stop(); 
       intersect += stopWatch.ElapsedMilliseconds; 

       stopWatch.Restart(); 
       Any(L1, L2); 
       stopWatch.Stop(); 
       any += stopWatch.ElapsedMilliseconds; 
      } 

      Console.WriteLine("Intersect: " + intersect + "ms"); 
      Console.WriteLine("Any: " + any + "ms"); 
     } 

     private static bool Any(List<string> lst1, List<string> lst2) 
     { 
      return lst1.Any(lst2.Contains); 
     } 

     private static bool Intersect(List<string> lst1, List<string> lst2) 
     { 
      return lst1.Intersect(lst2).Any(); 
     }    

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 
} 

Zu Vergleichszwecken schrieb ich meine eigenen Test int Sequenzen zu vergleichen:

intersect took 00:00:00.0065928 
any took  00:00:08.6706195 

Der Code:

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

namespace Demo 
{ 
    class Program 
    { 
     void run() 
     { 
      var lst1 = Enumerable.Range(0, 10000); 
      var lst2 = Enumerable.Range(10000, 10000); 

      int count = 10; 

      DemoUtil.Time(() => lst1.Intersect(lst2).Any(), "intersect", count); 
      DemoUtil.Time(() => lst1.Any(lst2.Contains),  "any",  count); 
     } 

     static void Main() 
     { 
      new Program().run(); 
     } 
    } 

    static class DemoUtil 
    { 
     public static void Print(this object self) 
     { 
      Console.WriteLine(self); 
     } 

     public static void Print(this string self) 
     { 
      Console.WriteLine(self); 
     } 

     public static void Print<T>(this IEnumerable<T> self) 
     { 
      foreach (var item in self) 
       Console.WriteLine(item); 
     } 

     public static void Time(Action action, string title, int count) 
     { 
      var sw = Stopwatch.StartNew(); 

      for (int i = 0; i < count; ++i) 
       action(); 

      (title + " took " + sw.Elapsed).Print(); 
     } 
    } 
} 

Wenn ich auch Zeit, dies für überlappende Bereiche durch Änderung der Listen dazu und die count zu 10000:

var lst1 = Enumerable.Range(10000, 10000); 
var lst2 = Enumerable.Range(10000, 10000); 

ich diese Ergebnisse:

intersect took 00:00:03.2607476 
any took 00:00:00.0019170 

In diesem Fall Any() eindeutig viel schneller ist.

Fazit

Die Worst-Case-Leistung ist sehr schlecht für Any() aber acceptible für Intersect(). Die Best-Case-Leistung ist sehr gut für Any() und schlecht für Intersect(). (und am besten Fall für Any() ist wahrscheinlich Worst-Case für Intersect()!)

Der Any() Ansatz ist O (N^2) im schlimmsten Fall und O (1) im besten Fall. Der Intersect() Ansatz ist immer O (N) (da es Hashing verwendet, nicht sortiert wird, sonst wäre es O (N (Log (N)))

Sie auch die Speichernutzung berücksichtigen müssen. Die Intersect() Methode Bedürfnisse eine Kopie von einem der Eingänge zu nehmen, während Any() nicht.

Deshalb ist die beste Entscheidung zu treffen, die Sie wirklich brauchen die Eigenschaften der realen Daten kennen, und Tests tatsächlich durchführen.

Wenn Sie wirklich Ich möchte nicht, dass Any() im schlimmsten Fall zu einem O (N^2) wird, dann solltest du Intersect() verwenden e dass Sie am besten mit Any() arbeiten.

Und natürlich spielt die meiste Zeit keine Rolle!

Wenn Sie diesen Teil des Codes nicht als Engpass erkannt haben, ist dies nur von akademischem Interesse. Sie sollten Ihre Zeit mit dieser Art von Analyse nicht verschwenden, wenn es kein Problem gibt. :)

Answer 2

Siehe Matthäus Antwort für eine vollständige und genaue Aufschlüsselung.

relativ leicht, sich lustig zu machen und versuchen:

 bool found; 

     double intersect = 0; 
     double any = 0; 

     for (int i = 0; i < 100; i++) 
     { 
      List<string> L1 = GenerateNumberStrings(200000); 
      List<string> L2 = GenerateNumberStrings(60000); 
      Stopwatch stopWatch = new Stopwatch(); 

      stopWatch.Start(); 
      found = Intersect(L1, L2); 
      stopWatch.Stop(); 
      intersect += stopWatch.ElapsedMilliseconds; 

      stopWatch.Reset(); 

      stopWatch.Start(); 
      found = Any(L1, L2); 
      stopWatch.Stop(); 
      any += stopWatch.ElapsedMilliseconds; 
     } 

     Console.WriteLine("Intersect: " + intersect + "ms"); 
     Console.WriteLine("Any: " + any + "ms"); 
    } 

    private static bool Any(List<string> lst1, List<string> lst2) 
    { 
     return lst1.Any(x => lst2.Contains(x)); 
    } 

    private static bool Intersect(List<string> lst1, List<string> lst2) 
    { 
     return lst1.Intersect(lst2).Any(); 
    } 

Sie werden feststellen, dass die Any Verfahren deutlich schneller auf lange Sicht ist, wahrscheinlich, weil es nicht die Speicherzuordnungen und Einrichtung erfordert, die erfordert, sich kreuzen (Any stoppt und gibt true zurück, sobald es eine Übereinstimmung findet, während Intersect tatsächlich die Übereinstimmungen in einem neuen List<T> speichern muss).

Answer 3

Es hängt von der Implementierung Ihrer IEnumerables ab.

Ihr erster Versuch (Intersect/Any), findet alle Übereinstimmungen und bestimmt dann, ob der Satz leer ist oder nicht. Aus der Dokumentation sieht das so etwas wie O (n) Betrieb sein:

Wenn das Objekt von dieser Methode zurückgegeben wird aufgezählt, aufzählt Intersect erster, alle unterschiedlichen Elemente dieser Sequenz zu sammeln. Es zählt dann die Sekunde auf und markiert jene Elemente, die in beiden Sequenzen vorkommen.Schließlich werden die markierten Elemente in der Reihenfolge zurückgegeben, in der sie gesammelt wurden.

Ihr zweiter Versuch (Any/Contains) aufzählt, über die erste Erhebung, ein O (n) Betrieb und für jedes Element in der ersten Erhebung, aufzählt über die zweiten, einen weiteren O (n) Operation, um zu sehen, wenn ein übereinstimmendes Element gefunden wird. Dies macht es etwas wie ein O (n) Betrieb, nicht wahr? Was denkst du könnte schneller sein?

Eine Sache zu prüfen, ist aber, dass die Contains() Lookup für bestimmte Sammlung oder einen Satz Typen (zB Wörterbücher, Binärbäumen oder geordnete Sammlungen, die einer binäre Suche oder Hash-Tabelle Lookup erlauben) könnten ein billiger Betrieb sein, wenn die Contains() Implementierung ist schlau genug, die Semantik der Sammlung auszunutzen, auf der sie sich befindet.

Aber Sie müssen mit Ihre Sammlungstypen experimentieren, um herauszufinden, welche besser funktioniert.