Ich versuche, nur die minimale Anzahl von Änderungen anzuwenden, wenn die Daten der Tabelle aktualisiert werden (es ist eine iOS-App und die Tabellenansicht ist natürlich UITableView , aber ich denke nicht, dass es hier relevant ist). Zu diesen Änderungen gehören das Hinzufügen neuer Elemente, das Entfernen alter Elemente sowie das Verschieben einiger vorhandener Elemente an eine andere Position, ohne deren Inhalt zu aktualisieren . Ich weiß, dass es ähnliche Fragen zu SO gibt, aber die meisten von ihnen berücksichtigen nur die Hinzufügungen und Streichungen und bestehende werden entweder ignoriert oder einfach neu geladen.
Meistens beinhalten die Bewegungen nicht mehr als ein paar existierende Elemente und die Tabelle kann bis zu 500 Elemente enthalten.
Elemente in den Arrays sind eindeutig.
Ich kann leicht Elemente hinzufügen, indem ich den Satz von Elementen in einem neuen Array von dem Satz von Elementen im alten Array subtrahiere. Und die umgekehrte Operation führt zu einem Satz gelöschter Elemente.
Das Problem liegt also darin, die minimalen Unterschiede zwischen zwei Arrays mit den gleichen Elementen zu finden.
%Vor%Das Diffundieren dieser Arrays sollte nur zu einer Verschiebung von Index 1 nach 3 führen.
Der Algorithmus weiß nicht, ob es nur einen solchen Zug gibt. Genauso gut kann die Änderung sein:
%Vor%Dies sollte dazu führen, dass der Index 1 zu 4 und 2 zu 3 verschoben wird und nicht 3 und 4 zwei Indizes nach links verschoben werden, da dies dazu führen könnte, dass 300 Elemente verschoben werden, obwohl die Änderung tatsächlich viel einfacher sein sollte. In Bezug auf das Anwenden der visuellen Änderung auf die Ansicht. Das erfordert möglicherweise eine Neuberechnung von Zellenhöhen oder das Ausführen vieler Animationen und anderer damit zusammenhängender Operationen. Ich möchte sie vermeiden. Ein Beispiel: Wenn Sie ein Objekt als Favorit markieren, wird das Verschieben des Elements an die Spitze der Liste oder 300 Elemente etwa 400 Millisekunden dauern. Das ist, weil mit dem Algorithmus, den ich momentan verwende, z. 100 Items werden um einen Index nach oben verschoben, einer um den Index 0, 199 andere bleiben unberührt. Wenn ich es abnehme, wird ein Element um 100 Indizes nach unten verschoben und das ist großartig, aber das ist der perfekte, aber ein sehr seltener Fall.
Ich habe versucht, den Index des Elements im alten Array zu finden und zu prüfen, ob es sich im neuen Array geändert hat. Wenn es eine Änderung gab, habe ich das Element von einem neuen Index zu einem alten verschoben, die entgegengesetzte Änderung aufgezeichnet und die Arrays verglichen, bis es hinsichtlich der Elementordnung gleich ist. Dies führt jedoch manchmal dazu, dass die großen Teile der Elemente verschoben werden, die tatsächlich nicht geändert wurden, abhängig von der Position dieser Elemente.
Irgendwelche Ideen oder Hinweise? Vielleicht ein modifizierter Levenshtein-Distanzalgorithmus? Könnte der Unmodifizierte dafür arbeiten? Wahrscheinlich werde ich es in der einen oder anderen Form implementieren müssen.
Gummiente sprach:
Denken Sie daran, alle unveränderten Sequenzen von Gegenständen zu finden und alle anderen Gegenstände zu bewegen. Könnte es die richtige Richtung sein?
Ich habe eine Idee, ich weiß nicht, ob es funktionieren würde. Nur meine zwei Cent. Wie wäre es, wenn Sie einen Algorithmus implementieren würden, der den längsten gemeinsamen Teilsequenzen Ihrer Array-Elemente ähnelt?
Die Idee wäre, große "Teilstrings" von Daten zu finden, die die ursprüngliche Sequenz beibehalten haben, die größten zuerst. Sobald Sie einen bestimmten Schwellenwert von Elementen in "langen Sequenzen" erreicht haben, wenden Sie einen trivialeren Algorithmus an, um die verbleibenden Probleme zu lösen.
Entschuldigung dafür, dass Sie ziemlich vage sind, es ist nur eine Unterordnung. Hoffe, dass Sie Ihr Problem lösen.