Das kam in einer realen Situation auf, und ich dachte, ich würde es teilen, da es zu einigen interessanten Lösungen führen könnte. Im Wesentlichen muss der Algorithmus zwei Listen unterscheiden, aber lassen Sie mich Ihnen eine genauere Definition des Problems geben.
Angenommen, Sie haben zwei Listen, L und R , von denen jede Elemente aus einem zugrunde liegenden Alphabet S enthält. Außerdem haben diese Listen die Eigenschaft, dass die gemeinsamen Elemente, die sie haben, in der richtigen Reihenfolge erscheinen: das heißt, wenn L[i] = R[i*] und L[j] = R[j*] und i & lt; j dann i * & lt; %Code%*. Die Listen müssen überhaupt keine gemeinsamen Elemente haben, und eines oder beide können leer sein. [ Erläuterung: Sie dürfen keine Wiederholungen von Elementen annehmen. ]
Das Problem besteht darin, eine Art "diff" der Listen zu erzeugen, die als neue Liste der bestellten Paare angesehen werden kann j wobei (x,y) von x und L von y ist, mit folgenden Eigenschaften:
R in beiden Listen erscheint, erscheint x im Ergebnis. (x,x) in x , aber nicht in L angezeigt wird, erscheint R im Ergebnis. (x,NULL) in y , aber nicht in R angezeigt wird, erscheint L im Ergebnis. und schließlich
Hat jemand irgendwelche guten Algorithmen, um das zu lösen? Was ist die Komplexität?
Es gibt eine Möglichkeit, dies in O (n) zu tun, wenn Sie eine Kopie einer der Listen in einer anderen Datenstruktur erstellen möchten. Dies ist ein klassisches Zeit / Raum-Kompromiss.
Erstellen Sie eine Hash-Map der Liste R, wobei der Schlüssel das Element und der Wert der ursprüngliche Index in das Array ist; In C ++ könnten Sie unordered_map von tr1 oder boost verwenden.
Behalten Sie einen Index für den nicht verarbeiteten Teil der Liste R, initialisiert für das erste Element.
Überprüfen Sie für jedes Element in Liste L die Hash-Zuordnung für eine Übereinstimmung in Liste R. Wenn Sie keine finden, Ausgabe (L-Wert, NULL). Wenn es eine Übereinstimmung gibt, holen Sie sich den entsprechenden Index aus der Hash-Map. Für jedes nicht verarbeitete Element in Liste R bis zum übereinstimmenden Index, Ausgabe (NULL, R-Wert). Für die Übereinstimmung, Ausgabe (Wert, Wert).
Wenn Sie das Ende der Liste L erreicht haben, gehen Sie durch die restlichen Elemente der Liste R und geben Sie (NULL, R-Wert) aus.
Bearbeiten: Hier ist die Lösung in Python. Für diejenigen, die sagen, diese Lösung hängt von der Existenz einer guten Hashing-Funktion ab - natürlich tut es dies. Das ursprüngliche Poster könnte die Frage, ob es sich um ein Problem handelt, um weitere Einschränkungen erweitern, aber ich werde bis dahin eine optimistische Haltung einnehmen.
%Vor%Der schlechteste Fall, wie er definiert wurde und nur Gleichheit verwendet, muss O (n * m) sein. Betrachten Sie die folgenden zwei Listen:
A [] = {a, b, c, d, e, f, g}
B [] = {h, i, j, k, l, m, n}
Angenommen, es gibt genau eine Übereinstimmung zwischen diesen beiden "geordneten" Listen. Es wird O (n * m) Vergleiche benötigen, da kein Vergleich existiert, der später andere Vergleiche überflüssig macht.
Also wird jeder Algorithmus, den Sie sich vorstellen, O (n * m) oder schlechter sein.
Diffing geordnete Listen können in linearer Zeit durchgeführt werden, indem Sie beide Listen durchqueren und den Abgleich durchführen. Ich werde versuchen, einige psuedo Java-Code in einem Update zu veröffentlichen.
Da wir den Ordnungsalgorithmus nicht kennen und keine Ordnung auf der Basis von Operatoren mit weniger als oder größer als bestimmen können, müssen wir die Listen ungeordnet betrachten. Da die Ergebnisse formatiert werden müssen, müssen Sie beide Listen scannen (zumindest bis Sie eine Übereinstimmung gefunden haben und dann können Sie ein Lesezeichen setzen und von dort aus erneut starten). Es wird immer noch O (n ^ 2) -Leistung sein, oder genauer gesagt O (nm).
Dies ist genau wie Sequence Alignment, Sie können den Needleman-Wunsch -Algorithmus verwenden, um es zu lösen. Der Link enthält den Code in Python. Stellen Sie nur sicher, dass Sie die Bewertung so festlegen, dass eine Nichtübereinstimmung negativ ist und eine Übereinstimmung positiv ist und eine Ausrichtung mit einem Leerzeichen beim Maximieren 0 ist. Der Algorithmus läuft in O (n * m) Zeit und Raum, aber die Raumkomplexität davon kann verbessert werden.
Bewertungsfunktion
%Vor%Code
%Vor%Sample IO
%Vor%Keine wirklich greifbare Antwort, nur vage Intuition. Weil Sie den Ordnungsalgorithmus nicht kennen, nur dass die Daten in jeder Liste geordnet sind, klingt er vage wie die Algorithmen, die zum "Diff" von Dateien verwendet werden (z. B. in Beyond Compare) und Zeilenabfolgen zusammenpassen. Oder auch ähnlich wie Regexp-Algorithmen.
Es kann auch mehrere Lösungen geben. (Egal, wenn es keine wiederholten Elemente gibt, die streng geordnet sind. Ich habe zu viel über Dateivergleiche nachgedacht)
Dies ist ein ziemlich einfaches Problem, da Sie bereits eine geordnete Liste haben.
%Vor%Hinweis ... dieser Code wird NICHT kompiliert. Es ist nur als Leitfaden gedacht.
BEARBEITEN Basierend auf den OP-Kommentaren
Wenn der Sortieralgorithmus nicht verfügbar ist, müssen die Listen als ungeordnet betrachtet werden. Wenn die Listen ungeordnet sind, hat der Algorithmus eine Zeitkomplexität von O (n ^ 2), insbesondere O (nm), wobei n und m die Anzahl der Elemente in jeder Liste sind.
BEARBEITEN Algorithmus, um dies zu lösen
L (a, b, c, d, e) R (b, q, c, d, g, e)
%Vor%Die Ergebnismenge ist
L (a, b, c, d, e) R (b, q, c, d, g, e)
Ergebnis ((a, null), (b, b), (null, q), (c, c), (d, d), (null, g), (e, e))
Ich glaube nicht, dass Sie genug Informationen haben. Alles, was Sie behauptet haben, ist, dass übereinstimmende Elemente in der gleichen Reihenfolge übereinstimmen, aber das erste übereinstimmende Paar zu finden, ist eine O (nm) -Operation, es sei denn, Sie haben eine andere Ordnung, die Sie bestimmen können.
SELECT distinct l.element, r.element
FROM Linke Liste l
OUTER JOIN RightList r
ON l.element = .element
ORDER BY l.id, r.id
Nimmt an, dass die ID jedes Elements seine Reihenfolge ist. Und natürlich, dass Ihre Listen in einer relationalen Datenbank enthalten sind:)
Tags und Links algorithm language-agnostic diff list