La risposta di Oren ha un errore nel modo in cui viene utilizzato il cronometro. Non viene ripristinato alla fine del ciclo dopo che è stato misurato il tempo impiegato da Any().
Nota come va di nuovo al punto di partenza del ciclo con il cronometro non essere mai Reset() in modo che il tempo che viene aggiunto al intersectinclude il tempo impiegato da Any().
Di seguito è una versione corretta.
Una build di rilascio correre fuori di qualsiasi debugger dà questo risultato sul mio PC:
Intersect: 1ms
Any: 6743ms
nota come sto facendo due liste non sovrapposti stringa per questo test. Si noti inoltre che questo è un test nel caso peggiore.
Dove ci sono molte intersezioni (o intersezioni che si verificano in prossimità dell'inizio dei dati) allora Oren è del tutto corretto per dire che Any() dovrebbe essere più veloce.
Se i dati reali contengono in genere intersezioni, è probabile che sia preferibile utilizzare Any(). Altrimenti, utilizzare Intersect(). È molto dipendente dai dati.
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();
}
}
}
A fini comparativi, ho scritto il mio test di confronto tra int sequenze:
intersect took 00:00:00.0065928
any took 00:00:08.6706195
Il codice:
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();
}
}
}
Se ho anche il tempo questo per sovrapposizione gamme cambiando il elenca questo e aumentando il count a 10000:
var lst1 = Enumerable.Range(10000, 10000);
var lst2 = Enumerable.Range(10000, 10000);
ottengo questi risultati:
intersect took 00:00:03.2607476
any took 00:00:00.0019170
In questo caso Any() è chiaramente molto più veloce.
Conclusione
la performance peggiore è molto male per Any() ma dimensioni adeguate per Intersect(). Le prestazioni migliori sono estremamente buone per Any() e non valide per Intersect(). (e caso migliore per Any() è probabilmente peggiore per Intersect()!)
Il Any() approccio è O (n^2) nel caso peggiore e O (1) nel migliore dei casi. L'approccio Intersect() è sempre O (N) (in quanto utilizza l'hashing, non l'ordinamento, altrimenti sarebbe O (N (log (N)))
Si deve anche considerare l'utilizzo della memoria:. Il metodo Intersect() esigenze di prendere una copia di uno degli ingressi, mentre Any() non lo fa.
quindi per prendere la decisione migliore si ha realmente bisogno di conoscere le caratteristiche dei dati reali, e in realtà eseguire test.
Se davvero non voglio che lo Any() diventi un O (N^2) nel peggiore dei casi, quindi dovresti usare Intersect(). Tuttavia, le e che ti sarà meglio usare Any().
E, naturalmente, il più delle volte niente di tutto ciò è importante!
A meno che non abbiate scoperto che questa parte del codice è un collo di bottiglia, questo è di mero interesse accademico. Non dovresti perdere tempo con questo tipo di analisi se non ci sono problemi. :)
Eseguire alcuni test o osservare l'IL generato? – zimdanen
Da http://ericlippert.com/2012/12/17/performance-rant/ _Se hai due cavalli e vuoi sapere quale dei due è più veloce allora ** corri i tuoi cavalli ** ._ –
Se uno sta andando decisamente meglio o peggio dell'altro, quindi la domanda di "Perché?" sarebbe valida. Ma senza sapere nulla dei tuoi dati, è impossibile rispondere. – Bobson