laszlokorte

Guten Tag zusammen,

ich habe mal wieder ein kleines aber vielleicht interessantes Problem.
Eigentlich ist es sprachenunabhängig, aber umgesetzt werden soll es in Javascript, daher poste ich es hier.

Ich habe folgende Datenstruktur:
Also ein Array an Objekten. Jedes dieser Objekte hat eine ID-Property, die als einzigartig zu betrachten ist.

Ich möchte nun zwei dieser Strukturen vergleichen und dabei eben nur nur in Bezug auf den Index des Arrays, sondern mit Bezugnahme auf die id des Objekts.

Wenn ich also in der oben genannten Struktur das 5. Objekte an den Anfang schiebe und das Resultat dann mit der Ausgangsstruktur vergleiche, möchte ich die Information haben, dass sich die Objekte mit den IDs 1-4 nicht geändert haben, aber das objekt mit der ID 5 von der 5. an die erste Stelle geschoben wurde.
Neben dem verschieben von Objekten im Array, soll natürlich auch das Hinzufügen und entfernen von Objekten erkannt werden.

Das Ergebnis des Vergleiches hätte ich gerne in einem solchen Format:
(Angenommen zusätzlich zu dem verschobenen Objekt[id:5] wird Objekt[ID:3] noch gelöscht und am ende noch ein Objekt hinzugefügt, was dann die ID6 bekommt)

Die changed_props-Property ist für das aktuelle Problem erstmal egal, später sollen aber für moved und none-changed noch die evtl veränderten (weiteren) Properties der Objekte gelistet werden.

Ich stelle mir vor, dass es für so ein Problem schon irgendwo einen Algorithms gibt, habe aber noch nichts gefunden. Vielleicht hat von euch ja jemand einen Tipp.

Einerseits ist das ganze ja durch das movement-tracking etwas komplexer als ein einfacher Text-Line-Diff, andererseits dürften die vorhandenen eindeutigen IDs das ganze evtl. ja auch vereinfachen.

Mister Ad

ChrisB

Das wäre aber doch gar nicht mehr der Fall - weil Objekt 1 jetzt nicht mehr an Position 1, sondern an Position 2 steht.

__________________
RGB is totally confusing - I mean, at least #C0FFEE should be brown, right?

laszlokorte

Das stimmt natürlich. Es ist aber ein Teil des Problems, das richtig zu erkennen, denn wenn ich oben ein Objekt einfüge, ist es uninteressant für den Betrachter des Diffs, dass sich der Rest nach unten bewegt. Ansonsten würde ja bei fast egal welcher Änderung an der Struktur die gesamte Struktur als "geändert" markiert werden, sodass niemand mehr erkennt, was sich nun wirklich geändert hat.

Das Tracking des Moved-To und Moved-From soll nur für die Objekte stattfinden, die sich "tatsächlich" bewegt haben. Natürlich ist mir klar, dass Bewegung relativ ist und sich je nach Sichtweise immer genau das andere Objekt bewegt oder hier eben "alles" bewegt.

Wenn man das ganze aber als DAU betrachtet, ist in dem obigen Beispiel die einfachste Schlussfolgerung, dass sich Objekt5 nach oben bewegt hat.
Wie man das jetzt im Programm erkennt ist die Frage. Da ich noch nie einen Diff-Programmiert hab, bin ich auf diesem Gebiet noch mehr in der Denkweise des Benutzers als in der Logik der Datenstrukturen. Ich habe eine Vorstellung davon, wo ich hin will, aber bin gar nicht 100% sicher, ob oder wie das möglich ist.

Wenn man einen Text-Diff macht, wird ja auch erkannt, dass 5 Zeilen am Anfang der Datei eingefügt wurden und entsprechend davon abgeleitet, dass sich die anderen Zeilen obwohl sie nicht mehr an der gleichen Position sind, nicht geändert haben.

nikosch

Nicht immer. Das kommt stark auf den eingefügten Text an. Enthält der Fragmente aus dem bisherigen, sieht ein Diff auch schnell mal ganz anders aus. Fazit: Entweder musst Du viel Gehirmschmalz investieren, oder das Problrm ist ne Nummer zu groß für Dich. In jedem Fall wüßte ich nicht, was dieses Board jetzt für Dich tun soll.

http://neil.fraser.name/writing/diff/ Viel Spaß.

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

Chriz

Hab nur den ersten Block deines Postings gelesen, aber wenn du eine PHP-Funktion suchst, wahrscheinlich array_diff_assoc, kannst du immer mal bei phpjs.org vorbeischauen:
http://phpjs.org/functions/array_diff_assoc:310

PS: Kann mir jemand die Syntax dort erklaeren .. arr1keys: for (k1 in arr1)???

__________________
"Nuschel ich?" - "Was?"

laszlokorte

Ich hab nun aber pro "zeile" eine eindeutige id, die nicht doppelt vor kommt.

Dein Link sieht schon mal recht interessant aus. Ich hab nicht wirklich erwartet, dass hier jemand sofort mit einer einfachen Lösung ankommt.
Aber es könnte ja sein, dass diese Art von Diff einen besonderen Namen hat, nach dem man besser googlen kann oder es vielleicht einen Algorithmus, der genau so etwas tut schon in pseudo-code gibt.

Anfangs kam mir das Problem gar nicht so komplex vor, nach etwas experimentieren habe ich gemerkt, dass es nicht ganz so einfach ist wie ich dachte. Wenn das Ganze in ein paar hundert Zeilen Code gut und performant zu machen ist, wäre das ja schonmal gut. Wenn's auch mit weniger geht noch besser. Wenn es eher eine Sache ist, über die man ein ganzes Buch schreiben könnte, dann muss ich das Problem wohl vereinfachen und mich mit weniger komfort begnügen.

Bisher habe ich mir grob so etwas gedacht:

- Über die neue Struktur iterieren
- alle objekt-ids, die auch in der alten vorkommen in einem array sammeln.

- über die alte Struktur iterieren
- alle objekt-ids, die auch in der neuen Version vorkommen, in einem zweiten array sammeln

- jetzt habe ich die alle Objekte, die nicht gelöscht und nicht hinzugefügt wurden (also alle gemeinsamen), einmal in der Reihenfolge, wie sie früher waren und einmal in der neuen Reihenfolge

- ein drittes - leeres - Array namens "result" erzeugen
- Einmal von 0 bis n hoch zählen, wobei n die länge der längeren der beiden Strukturen ist, den Zähler nenne ich mal i
-- Dabei erst die alte Struktur betrachten:
--- Wenn das i'te Objekt der alten Struktur in der neuen nicht vorkommen, dieses als "deleted" ins result pushen
--- Ansonsten als "not modified" oder "moved_from" pushen. Diese Entscheidung anhand der beiden zu anfangs erzeugen Arrays mit der alten und neuen Reihenfolge der ObjektIds treffen. Wie genau weiss ich eben noch nicht
-- Als nächstes die neue Struktur betrachten.
--- Wenn das i'te Objekt der neuen Struktur in der alten nicht vorkam, dieses als "added" ins result pushen
--- Ansonsten als "moved_to" pushen, wenn dieses Objekt nicht schon als "not modified" gepusht wurde oder wenn sich die Reihenfolge - anhand der zwei arrays ermittelt - nicht geändert hat

Bei der Erkennung, ob sich die Reihenfolge nun geändert hat oder nicht, hakt es eben noch.

/edit: @chriz: Die Syntax hat mich grad auch erst verwundert. Dort wird der äußeren for-schleife ein Label gegeben, damit das continue in der inneren schleife auf die äussere angewendet werden kann. Alternativ könnte man auch mit continue 1; oder continue 2; angeben, in der wievielten schleife von innen gezählt man in die nächste iteration springen will. Ist aber glaube ich nicht ganz das was ich brauche, trotzdem danke.

nikosch

arr1keys: ist die Sprungmarke (vgl. continue weiter unten) *)
for (k1 in arr1) iteriert über arr1 und liefert die Schlüssel (ähnlich foreach, aber eben nur für Objektschlüssel).

[edit]
*) nennt sich wohl „label“: http://www.mediaevent.de/javascript/...Schleifen.html

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

laszlokorte

Ich habe grad noch mal nachgedacht. Ich denke man könnte das Problem so weiter reduzieren dass man sagt:

Ich habe zwei Arrays mit gleicher Länge, gleichem Inhalt, aber in verschiedener Reihenfolge und suche die kleinste Menge an Elementen, die ich bewegen müsste um das eine Array in das andere umzuwandeln.

nikosch

Ja, das ist schon klar. Das Problem ist halt, dass die Lösung nur trivial ist, wenn Du mit atomaren Vorgängen arbeitest*). Also eine Änderung pro Diff. Wie ich das verstehe, willst Du aber zwei Strukturen in den Prozess reinwerfen und die optimale Überführung errechnen lassen. Das scheint mir recht aussichtslos.

PS: Was ich auf jeden Fall machen würde: Nicht zwischen Löschen und Verschieben unterscheiden. Verschieben als Löschen und Einfügen zu begreifen, macht die Sache auf jeden Fall einfacher. Im Endeffekt kannst Du dazwischen eh nicht unterscheiden.

*)

f([a,b,c,d], [d,c,b,a]) # => ???

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

laszlokorte

Ok, ich verstehe was du meinst, aber bei deinem Beispiel wäre eine der Lösung, dass man mindestens 3 Elemente wegen muss. Das könnt man einfach dort lassen wo es ist, weil sich dafür ja automatisch eine neue Position ergibt. Ich wäre da also mit einem Ergebnis von [a,b,c] total zu frieden und ob es nun [a,b,c] oder [a,b,d] wäre mir letztendlich noch egal.

Bei längeren Arrays (~700 Elemente) sollte das Ergebnis natürlich genauer sein.

Um dem ganzen mal etwas mehr Bezug zur Realität zu verleihen:

Ich habe eine Baum-Struktur (Kategorien und Unterkategorien mit beliebiger Tiefe und auf unterste Ebene Items, also wie so eine Forumkategorien/Threads-Struktur). Die Daten liegen aber nicht wirklich in einer rekursiven Baumstruktur vor, sondern als einfache Liste von Objekten:
Diese Threads und Kategorien können nun hin und her geschoben werden. Kategorie 3 könnte in Kategorie1 oder in Kategorie1.2 verschoben werden, oder Thread 2 könnte nach oben geschoben werden, sodass er vor Thread 1 steht.

Ich will jetzt also sehen können:
- Welcher Thread und welche Kategorie wurde seit dem 1.9.2011 erstellt?
- Welche Threads wurden seit dem gelöscht?
- Welche Threads wurden verschoben? Von wo? Wohin?

Der Diff wäre nicht sehr brauchbar, wenn er mir die ganzen Kategorien und Threads als gelöscht und neu erstellt anzeigen würde, nur weil ich Thread3 an den Anfang von Kategorie1.1 verschiebe.