2 Listen miteinander vergleichen und unterschiedliche Indizes ausgeben

Hallo!

Ich möchte gerne 2 Listen (von gleicher Größe und gleichem Typ) miteinander vergleichen und möchte als ergebniss eine List<Int> mit den indexes wo die unterschiede sind.

z.B.:

List A = 1,2,3,4,5,6,7
List B = 1,2,4,4,5,6,8

List C = compare(A,B) // List C = 2,6

Gibts da ne bessere Möglichkeit als Liste durchlauffen und paarweise zu vergleichen?

Die listen könnten schon mal 1000+ Elemente enthalten und das kommt mir nicht optimal vor da 1000 Elemente zu vergleichen.

Danke
lg Flo

HashSet mit dem Inhalt von Liste 1 anlegen.
Liste 2 durchlaufen und jedes Element der Liste 1 mit Hilfe von Add hinzufügen.
Schauen, ob Add true oder false zurück gibt. Falls das Resultat unklar ist: MSDN Dokumentation von HashSet durchlesen.

Danke für den Tipp.

Aber was mach ich wenn die Listen gleiche elemente enthalten können?
z.B bei einer Bool liste bekomme ich ja dan nur ein hashset der länge 2(sofern es true und false values gibt)

Ich bin mir nicht sicher in wiefern die Hashset Methode einen vorteil gegenüber ein for schleife mit lista_ != listb_ vergleich hat

1000 einträge sind nicht wirklich viel, verwende einfach eine schleife
premature optimization is the root of all evil

Du willst also nicht nur Gleichheit, sondern auch die Position prüfen (hatte ich zuerst überlesen)? Dann funktioniert das mit HashSet natürlich nicht...
Dann besser Console32's Vorschlag - und ja, 1000 ist nicht viel.
Wenn das dann in die Millionen geht könnte man über TPL nachdenken...

Vielleicht wäre das hier auch was für dich:
Enumerable.Except<TSource>

Hi Da_Flo,

hier noch eine (P)LINQ-Variante:

a.AsParallel().Zip(b.AsParallel(), (x,y) => (x != y)) // each entry is true if elements were distinct
    .Select((x,index) => x ? index : -1) // each entry is the index if elements were distinct, otherwise -1
    .Where(x => (x>=0)) // only indices of distinct elements
    .ToList();

Das ganze läuft von sich aus parallel und skaliert.
Allerdings ist dies bei <1000 Elemente wegen des ganzen Synchronisations- und Aufteilungs-Overheads sicherlich noch langsamer.

beste Grüße
zommi

zoomi, das Problem hier wäre aber parallele Schleife in einer parallelen Schleife.
Potential Pitfalls with PLINQ

Besser wäre..

var list1 = new List<Int32>( );
var list2 = new List<Int32>( );
var unequalIndexes = new ConcurrentBag<Int32>( );

Parallel.For( 0, ( list1.Count - 1 ), ( i ) =>
    {
        if ( list1.ElementAt( i ) != list2.ElementAt( i ) )
        {
            unequalIndexes.Add( i );
        }
    } );

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.