Merge zweier Listen (Algorithmus)



  • Hi,

    Ich habe eine Liste mit Elementen. Die Liste ist nicht sortiert, der Benutzer kann Elemente in der Liste verschieben. Jedes Element hat einen time stamp, wird es verschoben, wird der time stamp aktualisiert.

    Die Liste kann an verschiednen Orten verändert werden und muss dann wieder gemerged werden. Ich suche nun einen Algorithmus, der dies bewerkstelligt und zwar so, dass bei einem Konflikt (Element von beiden verändert wurde) diejenige Änderung mit dem grösseren time stamp recht behält.

    Ich habe als Beispiel eine Liste:

    Alfred
    Marco
    Moritz
    Sebastian
    Georg
    Hans

    Benutzer #1 schiebt nun Georg nach ganz oben und fügt "Manuel" ein. Das "+" soll andeuten, dass diese Elemente nun einen grösseren time stamp haben als die anderen:

    Georg +
    Alfred
    Marco
    Manuel +
    Moritz
    Sebastian
    Hans

    Benutzer #2 ändert an der ursprünglichen Liste folgendes: "Hans" und"Alfred" vertauscht und "Thomas" hinzugefügt. "++" noch grösserer time stamp

    Hans ++
    Marco
    Moritz
    Thomas ++
    Sebastian
    Georg
    Alfred ++

    Meiner Meinung nach sollte nach dem Merge folgendes herauskommen:

    Hans
    Georg
    Marco
    Manuel
    Moritz
    Thomas
    Sebastian
    Alfred

    Ich denke das Problem ist nicht so einzigartig, kennt jemand einen Algorithmus oder Ansatz wie man das lösen könnte?

    Danke!

    PS: Das Löschen von Elementen aus der ursprünglichen Liste habe ich absichtlich weggelassen, da dies sowieso extra behandelt werden muss



  • map<string,bool> habSchon;
    while(!a.isEmpty() && !b.isEmpty()){
      if(a.peek().time<b.peek().time)
        if(!habSchon[a.peek().name]){
           habSchon[a.peek().name]=true;
           result.push(a.peek());
        }
        a.pop();
      }
      elseif(a.peek().time>b.peek().time)
        if(!habSchon[b.peek().name]){
           habSchon[b.peek().name]=true;
           result.push(b.peek());
        }
        b.pop();
      }
      else
        performPanic();
    }
    while(!a.isEmpty()){
      if(!habSchon[a.peek().name]){
        habSchon[a.peek().name]=true;
        result.push(a.peek());
      }
    }
    while(!a.isEmpty()){
      if(!habSchon[a.peek().name]){
        habSchon[a.peek().name]=true;
        result.push(a.peek());
      }
    }
    


  • Hi,

    Danke für den Vorschlag! Ich habe den performPanic noch ersetzt (tritt auf wenn beide Listen immer noch die ursprüngliche sind) und füge ein Element nur ein, wenn es zusätzlich nicht in der anderen Liste vorkommt und dort neuer ist.

    Das Ganze funktioniert grundsätzlich, aber es wird nicht richtig zusammengefügt, selbst bei Fällen wo eigentlich gar kein Konflikt auftritt stimmt die Reihenfolge nicht. Zum Beispiel aus

    a
    b
    c
    d
    e
    f

    wobei #1 daraus

    a
    b
    c
    e
    d (nach unten verschoben)
    f

    und #2

    f
    b
    c
    d
    e
    a (mit f vertauscht, änderung neuer als änderungen in #1)

    macht

    entsteht nicht

    f
    b
    c
    e
    d
    a

    sondern

    f
    b
    c
    e
    a (a sollte zuunterst sein)
    d

    Grundsätzlich sollte die Reihenfolge der einzelnen Listen möglichst beibehalten werden und nicht blindlings mittels time stamp gemerged werden.



  • Ups.

    Vielleicht so speichern, was passierte.

    Vorher:
    a
    b
    c
    d
    e
    f

    Kunde1:
    a
    b
    c
    e
    d (nach unten verschoben)
    f

    Kunde2:
    f
    b
    c
    d
    e
    a (mit f vertauscht, änderung neuer als änderungen in #1)

    Speichern als
    Vorher:
    a
    b
    c
    d
    e
    f
    Bewegungen nach Timespamp sortiert:
    d hinter e +
    f vor b ++
    a hinter e ++

    Und beim Mischen die Bewegungen ausführen.
    a
    b
    c
    d
    e
    f

    d hinter e +

    a
    b
    c
    e
    d
    f

    f vor b ++

    a
    f
    b
    c
    e
    d

    a hinter e ++

    f
    b
    c
    e
    a
    d

    Man beachte, daß im letzten Schritt auch

    f
    b
    c
    e
    d
    a

    erlaubt wäre. Vielleicht ist allgemein der kürzeste Weg der beste, weil es sozusagen die Minimal-Aussage des Kunden ist und dem anderen potenziell am wenigsten Widerspricht.



  • Hallo nochmals,

    also erstens hast du recht!

    Die Reihenfolge

    f
    b
    c
    e
    a
    d

    stimmt schon, weil Kunde2 aussagte, dass a unter e soll (oder ans Ende, je nachdem ob man sich am oberen oder am unteren Element orientiert).

    Ich werde den neuen Ansatz mal probieren und berichte dann, ob es geklappt hat 🙂



  • So, ich denke ich habe nun eine Version die hinhaut (auch wenn sie ziemlich kompliziert ist) 🙂

    vereinfacht gesagt funktioniert es nun so:

    Listen A und B werden gemerged:
    ein Typ "ElementInfo" enthält den Zeiger auf einen Listeneintrag, sowie das vorherige (prior) und das nächste (next) Element (sofern vorhanden)

    1. erstelle eine Liste von ElementInfos (change_list)
    2. iteriere über B und füge alle Elemente welche sich nicht in A befinden in die change_list
    3. ist die change_list gleich gross wie B, so müssen alle Elemente aus B bei A angehängt werden (vorne oder hinten, das ist mir egal).. fertig
    4. iteriere über A und füge alle Elemente welche sich auch in B befinden, dort aber neuer sind zur change_list, diesesmal werden die gefundenen Elemente aber zusätzlich aus A gelöscht
    5. A enthält nun nur noch die Elemente, welche neu in A sind, neuer sind als in B oder gleich sind wie in B, die change_list enthält alle Elemente, welche A noch fehlen
    6. nimm das erste Element aus der change_list und prüge, ob ihr nächstes oder vorheriges Element in A zu finden ist, falls ja, füge es in A ein und entferne das Element aus der change_list, falls nicht, schiebe das Element ans Ende der change_list
    7. Punkt 6 wird so lange wiederholt, bis die change_list leer ist


  • osiris81 schrieb:

    So, ich denke ich habe nun eine Version die hinhaut (auch wenn sie ziemlich kompliziert ist) 🙂

    Jupp, ist kompliziert. 🤡
    Vor allem das "falls nicht" in Punkt 6 macht mir Angst.

    Was ist der wichtigste Punkt, der bei meinem Ansatz noch gestört hatte?



  • Hi,

    Ich denke es ist die gleiche Idee die du schon angedeutet hast, mit dem unterschied, dass ich anhand der Listen herausfinde, welche "Änderungen" es gegeben hat, ansonsten mache ich genau das gleiche 🙂

    Punkt 6 macht nur Angst sollte sich im Ganzen ein Programmierfehler eingeschlichen haben 🙂 Eine Endlos-Schlaufe kann sich nur dann ergeben, falls kein Element in der change_list einen Link (prior, next) auf ein Element in A hat.

    Grundsätzlich mache ich nur 3 Sachen:

    1. alle Elemente welche in B neu sind in einer Liste merken (mit "Links")
    2. alle Elente die in B neuer als in A sind in der gleichen Liste merken
    3. Die Liste ist nun genau was du vorgeschlagen hast (die Bewegungsliste) und muss nun nur noch in A eingefügt werden



Log in to reply