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
HansBenutzer #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
HansBenutzer #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
AlfredIch 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
fwobei #1 daraus
a
b
c
e
d (nach unten verschoben)
fund #2
f
b
c
d
e
a (mit f vertauscht, änderung neuer als änderungen in #1)macht
entsteht nicht
f
b
c
e
d
asondern
f
b
c
e
a (a sollte zuunterst sein)
dGrundsä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
fKunde1:
a
b
c
e
d (nach unten verschoben)
fKunde2:
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
fd hinter e +
a
b
c
e
d
ff vor b ++
a
f
b
c
e
da hinter e ++
f
b
c
e
a
dMan beachte, daß im letzten Schritt auch
f
b
c
e
d
aerlaubt 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
dstimmt 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)- erstelle eine Liste von ElementInfos (change_list)
- iteriere über B und füge alle Elemente welche sich nicht in A befinden in die change_list
- 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
- 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
- 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
- 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
- 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:
- alle Elemente welche in B neu sind in einer Liste merken (mit "Links")
- alle Elente die in B neuer als in A sind in der gleichen Liste merken
- Die Liste ist nun genau was du vorgeschlagen hast (die Bewegungsliste) und muss nun nur noch in A eingefügt werden
-