J'ai une liste de 500000 généré de façon aléatoire, Tuple<long,long,string> objets sur lesquels je suis en effectuant une simple "entre" recherche:
var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
Lorsque je génère mon ensemble aléatoire et exécuter ma recherche de 100 généré de façon aléatoire les valeurs de x, les recherches se terminer dans environ quatre secondes. Connaître les grandes merveilles que le tri n'est à la recherche, cependant, j'ai décidé de trier mes données en Item1, puis, en Item2, et, enfin, en Item3 - avant de lancer mon 100 recherches. J'attend la version triée à effectuer un peu plus rapide en raison de la direction de la prévision: ma pensée a été qu'une fois qu'on arrive au point où l' Item1 == x, toutes les autres vérifications d' t.Item1 <= x de prédire la branche correctement comme "ne pas prendre", l'accélération de la queue de la partie de la recherche. À ma grande surprise, les perquisitions qui ont eu deux fois plus longtemps sur un tableau trié!
J'ai essayé de commutation autour de l'ordre dans lequel j'ai couru mes expériences, et utilisé différents de la graine pour le générateur de nombre aléatoire, mais l'effet a été le même: recherche dans un tableau non trié couru près de deux fois plus rapide que les recherches dans le même tableau, mais triés!
Quelqu'un aurait-il une bonne explication de cet étrange effet? Le code source de mes tests en suit, je suis à l'aide .NET 4.0.
private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
var data = new byte[8];
r.NextBytes(data);
return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
var res = x.Item1.CompareTo(y.Item1);
if (res != 0) return res;
res = x.Item2.CompareTo(y.Item2);
return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
}
}
static void Test(bool doSort) {
var data = new List<Tuple<long,long,string>>(TotalCount);
var random = new Random(1000000007);
var sw = new Stopwatch();
sw.Start();
for (var i = 0 ; i != TotalCount ; i++) {
var a = NextLong(random);
var b = NextLong(random);
if (a > b) {
var tmp = a;
a = b;
b = tmp;
}
var s = string.Format("{0}-{1}", a, b);
data.Add(Tuple.Create(a, b, s));
}
sw.Stop();
if (doSort) {
data.Sort(new TupleComparer());
}
Console.WriteLine("Populated in {0}", sw.Elapsed);
sw.Reset();
var total = 0L;
sw.Start();
for (var i = 0 ; i != TotalQueries ; i++) {
var x = NextLong(random);
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
total += cnt;
}
sw.Stop();
Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
Test(false);
Test(true);
Test(false);
Test(true);
}
Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)
