Zwei Listen auf Unterschiede vergleichen?

[Gast freescale]

Hallo,

ich stehe vor folgendem Problem...

Ich habe zwei Listen (java.util.List), firstList & secondList, mit beispielsweise folgenden Werten:

firstList -> a; b; d; e; g;

secondList -> b; c; d; e; h; i;

...und nun möchte ich diese untereinander vergleichen bezgl. neuer und entfernter Werte, um - bei obigen Beispielswerten zu bleiben - letztlich eine Ausgabe wie dieser zu bekommen:

- secondList verglichen mit firstList -

a: Weggefallen

b: keine Veränderungen

c: Neu

d: keine Veränderungen

e: keine Veränderungen

g: Weggefallen

h: Neu

i: Neu

Irgendwie habe ich es bisher noch nicht geschafft, dieses halbwegs zuverlässig zu implementieren.

Dass beide Listen sortiert sind, kann ich vorraussetzen.

Vielleicht hat ja jemand von euch eine Idee oder einen guten Tipp.

Liebe Grüße,

Denis

[USF]

Man koennte alle Werte der Liste 1 durchgehen und schauen, ob es sie auch in Liste 2 gibt, wenn ja, dann keine Veraenderung, wenn nicht, dann Weggefallen.

Danach koennte man den Umkehrvergleich machen, also Liste 2 ist gegeben und Liste 1 wird zugeordnet. Wenn vorhanden dann keine Veraenderung, wenn nicht, dann neu.

[Rondario]

Quick and dirty Idee:

Falls du eine der beiden Listen als Ausgangsliste nehmen willst, kannst du einfach mit zwei Iteratoren die Listen durchwandern und nach matchings prüfen. Bsp:

Iterator IA für Liste A

Iterator IB für Liste B

Anfangen tust du bei beiden Listen am Anfang, und wanderst mit dem iterator IA immer weiter wenn etwas weggefallen ist, mit IB immer weiter wenn etwas hinzugekommen ist, und bei einem Match wanderst du mit beiden weiter.

Seien a und b jeweils elemente für die die Ordnung a < b gilt.

Da beide Listen sortiert sind, gilt:

1) IA -> a, IB -> a => a in beiden Listen, IB weitersetzen

2) IA -> a, IB -> b => zweite Liste enthält kein a, da sonst schon irgenwann Fall eins gegriffen hätte => a weggefallen, IA weitersetzen

3) IA -> b, IB -> a => erste Liste enthält kein a, da a < b und es somit schon vorher gefunden worden wäre, womit IB weitergesetzt worden wäre und nicht mehr auf a zeigen würde. => a hinzugekommen.

Am Beispiel:

firstList -> a; b; d; e; g;

secondList -> b; c; d; e; h; i;

1) IA -> a, IB -> b => a<b =>a weggefallen (IA++)

2) IA -> b, IB -> b => b=b => b gleich (IA++, IB++)

3) IA -> d, IB -> c => d>c => c hinzugekommen (IB++)

4) IA -> d, IB -> d => d=d => d gleich (IA++, IB++)

5) IA -> e, IB -> e => e=e => e gleich (IA++, IB++)

6) IA -> g, IB -> h => g<h => g weggefallen (IA++) (bereits am Ende)

7) IA ende => alles hinter IB ist hinzugekommen.

Klappt natürlich nur wenn einer der beiden Liste ausgezeichnet im Sinne von "Liste mit der verglichen wird" ist. Ähnlichkeit zweier Listen sollte unter anderem mit Sequence alignment gehen.

Das ganze sollte dir modulo Denkfehler in linearer Zeit zur länge der kürzeren Liste deine Informationen beschaffen

[Gast freescale]

Hey...

super! Danke für die Antworten!

Das probier ich gleich mal aus.

Die Listen sind eigentlich relativ klein (50 bis 60 Werte), ... daher sollte die Größe eigentlich kein Problem sein.

Liebe Grüße,

Denis

[Rondario]

Kleiner Fehler im Pseudocode, muss natürlich wie folgt lauten:

Da beide Listen sortiert sind, gilt:

1) IA -> a, IB -> a => a in beiden Listen, IB und IA weitersetzen

2) IA -> a, IB -> b => zweite Liste enthält kein a, da sonst schon irgenwann Fall eins gegriffen hätte => a weggefallen, IA weitersetzen

3) IA -> b, IB -> a => erste Liste enthält kein a, da a < b und es somit schon vorher gefunden worden wäre, womit IB weitergesetzt worden wäre und nicht mehr auf a zeigen würde. => a hinzugekommen, IB weitersetzen.

Außerdem ist natürlich noch der Fall "IB am Ende der Liste angekommen" analog zum Fall IA am Ende der Liste angekommen zu behandeln. (alle Elemente aus Liste A "hinter" IA fallen weg)

[Gast freescale]

Für alle die es interessiert, hier mein Code. :-)

Danke nochmal!!

package com.[...].tools;


import java.util.ArrayList;

import java.util.List;


public class ListCompare

{

  public static void main(String[] args)

  {

    List oldList; // param

    List newList; // param




    oldList = new ArrayList(); // Alte Daten

    oldList.add("a");

    oldList.add("b");

    oldList.add("d");

    oldList.add("e");

    oldList.add("g");


    newList = new ArrayList(); // Neue Daten

    newList.add("b");

    newList.add("c");

    newList.add("d");

    newList.add("e");

    newList.add("h");

    newList.add("i");



    /* ab hier in eigene Methode */

    List resultList = new ArrayList();


    String oldValue;

    String newValue;


    int oldIndex = 0;

    int newIndex = 0;

    int compareResult;


    while(true)

    {

      oldValue = "";

      newValue = "";


      if(oldIndex < oldList.size())

        oldValue = oldList.get(oldIndex).toString();


      if(newIndex < newList.size())

        newValue = newList.get(newIndex).toString();


      if((oldValue != "") && (newValue != ""))

        compareResult = oldValue.compareTo(newValue);

      else if((oldValue == "") && (newValue == ""))

        break;

      else if(oldValue != "")

        compareResult = -1;

      else

        compareResult = 1;


      if(compareResult < 0)

      {

        resultList.add(oldValue.concat(": Weggefallen"));

        oldIndex++;

      }

      else if(compareResult > 0)

      {

        resultList.add(newValue.concat(": Neu"));

        newIndex++;

      }

      else

      {

        resultList.add(oldValue.concat(": keine Veränderungen"));

        oldIndex++;

        newIndex++;

      }

    }


    oldIndex = 0;

    while(oldIndex < resultList.size())

    {

      System.out.println(resultList.get(oldIndex++).toString());

    }

  }

}[/PHP]

[kingofbrain]

Servus,

Deine Lösung habe ich zwar nicht ausprobiert, aber ich finde sie nicht sonderlich elegant. Das fängt schon mit der while(true)-Schleife und dem break an. Das ist in den allermeisten Fällen unnötig. Ich habe mal schnell was geschrieben, was das Ganze in meinen Augen nachvollziehbarer löst. Dabei gehe ich davon aus, das es drei interessante Listen gibt. Die mit den unveränderten Daten, die mit den Neuen, und die mit den Gelöschten. Wenn ich aus den beiden Ursprungslisten die Werte, die in beiden vorkommen, rausnehme und in einer extra Liste ablege, habe ich bereits alle Listen. Man müsste den Code natürlich noch vernünftig aufteilen, das ist jetzt einfach nur schnell hingeklatscht, zeigt aber, was ich meine.

import java.util.ArrayList;

import java.util.List;


public class ListCompare

{

  public static void main(String[] args)

  {

    List oldList = new ArrayList(); // Alte Daten

    oldList.add("a");

    oldList.add("b");

    oldList.add("d");

    oldList.add("e");

    oldList.add("g");


    List newList = new ArrayList(); // Neue Daten

    newList.add("b");

    newList.add("c");

    newList.add("d");

    newList.add("e");

    newList.add("h");

    newList.add("i");


    List equal = new ArrayList();


    // Values in both lists

    for(int i = 0; i < oldList.size(); i++) {

        if(newList.contains(oldList.get(i))) {

            equal.add(oldList.get(i));

        }

    }


    // remove values that occur in both lists

    for(int i = 0; i < equal.size(); i++) {

        oldList.remove(equal.get(i));

        newList.remove(equal.get(i));

    }


    System.out.println("Values that haven't been changed: ");


    for(int i = 0; i < equal.size(); i++) {

        System.out.println(equal.get(i));

    }


    System.out.println("Values that have been added: ");


    for(int i = 0; i < newList.size(); i++) {

        System.out.println(newList.get(i));

    }


    System.out.println("Values that have been deleted: ");


    for(int i = 0; i < oldList.size(); i++) {

        System.out.println(oldList.get(i));

    }

  }

} 

Peter

[Gast freescale]

das ist jetzt einfach nur schnell hingeklatscht

Meiner doch auch. :-)

Ich kann ja mal den Code posten wenn er fertig ist. Trotzdem danke, mal schauen, vielelicht finde ich auch oben noch interessante Anregungen.

lg,

Denis