Hallo zusammen,
ich möchte mich Console32 anschließen: premature optimization is the root of all evil.
Ich habe alle drei Varianten auf einem Quadcore unter .NET 4.0 gemessen. Im Kern besteht jeder Test aus zwei Listen mit je einer 1Mio Einträgen, wobei sich sich die Listenelemente an jedem zweiten Index unterscheiden. Jeden Test habe ich 10mal laufen lassen und die Gesamtzeit ermittelte. So einen Testdurchlauf habe ich je 5mal wiederholt.
- Variante 1: die naive Lösung mit for-Schleife und if-Vergleich für jeden Index.
- Variante 2: die (P)LINQ-Lösung von zommi
- Variante 3: die Parallel.For-Lösung von Abt (wobei aus dem ConcurrentBag am Ende noch eine (sortierte) Liste gemacht wird, so wie sie von den anderen Varianten produziert wird)
Hier die Ergebnisse (in Sekunden):
[pre]
Debug Release
0.3122152 0.1464129
0.3125960 0.1471423
0.3119771 0.1474386
0.3145677 0.1465855
0.3118011 0.1490578
0.5548933 0.5646838
0.4729633 0.5187067
0.4888288 0.4869280
0.4751555 0.5011644
0.4962970 0.5495512
1.4667704 1.4000914
1.6532845 1.7779067
1.5387897 1.5262697
1.6663349 1.6185221
1.7648896 1.2412357
[/pre]
Die "Optimierungen" gehen - zumindest in dem gewählten Szenario(*) - also nach hinten los.
Hier noch mein Code:
using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Threading.Tasks;
static class App
{
public static void Main (string [] astrArg)
{
Console.WriteLine ("Begin Main");
var list1 = new List<Int32>( );
var list2 = new List<Int32>( );
for (int i = 0; i < 1000000; ++i) {
list1.Add (i);
list2.Add (i % 2 == 0 ? -1 : i);
}
for (int variant = 1; variant ≤ 3; ++variant) {
Console.WriteLine ();
for (int tries = 0; tries < 5; ++tries) {
var sw = new Stopwatch ();
sw.Start ();
for (int times = 0; times < 10; ++times) {
var unequalIndexes = new List<Int32>( );
switch (variant) {
case 1: {
for (int i = 0; i < list1.Count; ++i) {
if ( list1 [i] != list2 [i] ) {
unequalIndexes.Add( i );
}
}
break;
}
case 2: {
unequalIndexes = list1.AsParallel().Zip(list2.AsParallel(), (x,y) => (x != y))
.Select((x,index) => x ? index : -1)
.Where(x => (x≥0))
.ToList();
break;
}
case 3: {
var unequalIndexesTmp = new ConcurrentBag<Int32>( );
Parallel.For( 0, ( list1.Count - 1 ), ( i ) =>
{
if ( list1.ElementAt( i ) != list2.ElementAt( i ) )
{
unequalIndexesTmp.Add( i );
}
} );
unequalIndexes = unequalIndexesTmp.ToList();
unequalIndexes.Sort ();
break;
}
default: {
Console.WriteLine ("error");
break;
}
}
}
sw.Stop ();
Console.WriteLine (sw.Elapsed);
}
}
#if false
foreach (var i in unequalIndexes) {
Console.WriteLine (i);
}
#endif
}
}
herbivore
(*) Wenn sich relativ wenige Elemente unterscheiden, können parallelen Varianten einen (kleinen) Vorteil herausholen. Das ist auch verständlich, denn die Vergleiche sind problemlos parallelisierbar, aber die Zugriffe auf die Ergebnisliste müssen synchronisiert werden. Je mehr Vergleiche und je weniger Zugriffe auf die Ergebnisliste, desto besser schneiden die parallelen Varianten ab. Aber normalerweise kann man sich nicht aussuchen, wieviele Unterschiede es gibt. Das bedeutet andersherum, dass wenn es noch mehr Unterschiede gibt, als bei jedem zweiten Index, dann schneiden die parallelen Varianten noch schlechter ab.
