List<> vergleichen

Professional

Wednesday, January 20th 2010, 1:54pm

List<> vergleichen

hallo zusammen,

ich bin auf der suche nach einer schnellen lösung wie zwei listen miteinander verglichen werden können. ich möchte nicht auf .Equals vergleichen da dies ja "nur" die referenzen vergleicht, sondern ich möchte die inhalte der listen vergleichen.
dabei möchte ich aber auf diese methode wenn es geht verzichten:

C# Quellcode

List<string> list1 = new List<string>();
List<string> list2 = new List<string>();
 
list1.add("ka");
list2.add("ka");
 
for(int i = 0; i < list1.count; i++)
{
      if(list1[i] == list2[i])
      {
             MessageBox.Show("gleich");
      }
      else
      {
             MessageBox.Show("ungleich");
      }
}

da dies wohl nicht so super flott ist wenn die beiden listen mal richtig dick werden...
hat jemand ne gute idee?

thx, truespin

F0kus

Professional

Posts: 581

Wednesday, January 20th 2010, 2:06pm

Hey truespin!

Sag mal, bist du dir sicher was .equals() angeht? Das wäre eig. wenig sinnvoll.
In Java ist es genau umgekehrt:

"==" prüft auf die Identität (selbe Referenz)
.equals() prüft auf gleichen Inhalt (gleichheit).

truespin

Professional

Posts: 378

Wednesday, January 20th 2010, 2:24pm

hallo,

aus der .net hilfe:
"Die Standardimplementierung von Equals unterstützt Verweisgleichheit für Referenztypen und bitweise Gleichheit für Werttypen. Verweisgleichheit ist gegeben, wenn die zu vergleichenden Objektverweise auf dasselbe Objekt verweisen. Bitweise Gleichheit ist gegeben, wenn die binären Darstellungen der zu vergleichenden Objekte identisch sind. "

außerdem hab ich es schon versucht

thx, truespin

F0kus

Professional

Posts: 581

Wednesday, January 20th 2010, 2:31pm

Urg okay =) Dann ist es im .Net umgekehrt.

Hmmm um etwas performance zu sparen, könntest du die Transitivität ausnutzen.

Z.b.
Wenn list[0] == list[1] und list[1] == list[2] folgt daraus dass list[0] == list[2] ist.
Da sparste dir einige vergleiche.

Ansonsten wirst du wohl nicht drum herum kommen die Liste zu durchlaufen :-/

truespin

Professional

Posts: 378

Wednesday, January 20th 2010, 2:44pm

danke für deinen tipp, aber wie willst du das mit... sagen wir mal 300 einträgen machen?

thx, truespin

Rondrer

Professional

Posts: 306

Wednesday, January 20th 2010, 4:06pm

Also ich glaube nicht, dass es einen effizienteren Algorithmus als den von dir schon geposteten gibt: (oder sogar geben kann)

Quoted from "truespin"

C# Quellcode

for(int i = 0; i < list1.count; i++)
{
      if(list1[i] == list2[i])
      {
             MessageBox.Show("gleich");
      }
      else
      {
             MessageBox.Show("ungleich");
      }
}

Um den Inhalt zweier Listen auf Gleichheit zu prüfen muss ich ja zumindest jedes Element jeder liste einmal mit irgendetwas (spielt hier erstmal keine Rolle mit was) vergleichen, sonst kann man darüber ja keinerlei Aussage treffen. Und deine Methode hat eben genau diese minimale Anzahl an Vergleichen schon erreicht. Ich sehe da kein Einsparpotential.
Auch solche transitiven Zusammenhänge sparen dabei keine Vergleiche, erhöhen die Zahl derer eher noch.

F0kus

Professional

Posts: 581

Thursday, January 21st 2010, 12:29am

Urg sorry hatte mir den code nciht so richtig angeschaut.
Hab gedacht du willst beispielsweise ein Element der einen Liste mit der kompletten anderen Liste vergleichen. Und dann das gleiche mit dem zweiten Element und so weiter...

Sorry.... :-/

Ach so und einsparen kannst du da nicht so wirklich machen... zumindest fällt mir nix ein.

truespin

Professional

Posts: 378

Thursday, January 21st 2010, 7:56am

guten morgen,

ja das dachte ich mir. es war mir klar das ich im worst case die gesamte liste durchlaufen muss um einen unterschied fest zu stellen. ich hatte nur die hoffnung das es noch eine andere möglichkeit gibt... was aber eigentlich nicht möglich ist.

danke für eure ideen!

thx, truespin

vince

Master

Posts: 1,104

Thursday, January 21st 2010, 1:37pm

Hey,

ich weiss nicht was das für Listen sind und ich kenn die Inhalte nicht, aber wenn man einen binären Suchbaum hat, dann bräuchte man nicht zwangsweise alle Elemente prüfen sondern nur die unteresten Knoten miteinandner vergleichen.

Mir fällt jetzt grad nichts weiter groß zu dem Thema ein, aber ich denke, das man mit einer Baumstruktur die Laufzeitklasse mit Sicherheit verbessern kann.