Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

2 Listen miteinander vergleichen und unterschiedliche Indizes ausgeben
Da_Flo
myCSharp.de - Member



Dabei seit:
Beiträge: 269
Herkunft: Österreich

Themenstarter:

2 Listen miteinander vergleichen und unterschiedliche Indizes ausgeben

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.832

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Da_Flo
myCSharp.de - Member



Dabei seit:
Beiträge: 269
Herkunft: Österreich

Themenstarter:

beantworten | zitieren | melden

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)
private Nachricht | Beiträge des Benutzers
Console32
myCSharp.de - Member



Dabei seit:
Beiträge: 258

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.832

beantworten | zitieren | melden

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...
private Nachricht | Beiträge des Benutzers
felix
myCSharp.de - Member



Dabei seit:
Beiträge: 174

beantworten | zitieren | melden

Vielleicht wäre das hier auch was für dich:
Enumerable.Except<TSource>
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1.361
Herkunft: Berlin

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von zommi am .
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.832

beantworten | zitieren | melden

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 );
        }
    } );
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers