So ermitteln Sie Unterschiede in zwei Datenlisten

StackOverflow https://stackoverflow.com/questions/127151

Frage

Dies ist eine Übung für die CS-Leute, um mit der Theorie zu glänzen.

Stellen Sie sich vor, Sie haben 2 Container mit Elementen.Ordner, URLs, Dateien, Strings, es spielt wirklich keine Rolle.

Was ist ein Algorithmus zur Berechnung der Hinzufügung und der Entfernung?

Beachten:Wenn es viele Möglichkeiten gibt, dieses Problem zu lösen, posten Sie bitte eine pro Antwort, damit diese analysiert und positiv bewertet werden kann.

Bearbeiten:Alle Antworten lösen die Sache mit 4 Containern.Ist es möglich, nur die ersten 2 zu verwenden?

War es hilfreich?

Lösung

Angenommen, Sie zwei Listen von Unikaten haben und die Reihenfolge keine Rolle spielt, können Sie von ihnen sowohl als Sätze denken können, anstatt Listen

Wenn Sie ein Venn-Diagramm denken, mit der Liste A, wie ein Kreis und Liste B als andere, dann ist die Schnittstelle zwischen diesen beiden ist die konstante Pool.

Entfernen Sie alle Elemente in diesem Schnittpunkt von A und B, und und etwas links in A gelöscht wurde, während alles in B gelassen wurde hinzugefügt.

So durchlaufen A für jedes Element in B. suchen Wenn Sie es finden, entfernen Sie es von beiden A und B

Dann ist A eine Liste der Dinge, die gelöscht wurden, und B ist eine Liste der Dinge, die hinzugefügt wurden,

Ich denke, ...

[Bearbeiten] Ok, mit der neuen "nur 2 Containern" Einschränkung, das gleiche noch gilt: 

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

Dann sind Sie nicht eine neue Liste der Konstruktion oder Ihre alten zu zerstören ... aber es wird länger dauern als mit dem vorherigen Beispiel, könnten Sie einfach Schleife über die kürzere Liste und die Elemente aus, je länger entfernen. Hier müssen Sie beiden Listen tun

Ein Ich würde meine erste Lösung argumentieren nicht 4 Behälter verwendet haben, es zerstört nur zwei; -)

Andere Tipps

Ich habe das nicht in einer Weile getan, aber ich glaube, dass der Algorithmus so geht ... 

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

In Bezug auf der rechten Liste Beziehung zu Liste links, löscht enthält Elemente entfernt und fügt enthält jetzt neue Elemente.

Was Joe sagte. Und, wenn die Listen zu groß sind, in dem Speicher zu passen, verwenden Sie eine externe Datei Sortierprogramm oder eine Merge Art.

Fehlende Information:Wie definieren Sie hinzugefügt/entfernt?Z.B.Wenn die Listen (A und B) das gleiche Verzeichnis auf Server A und Server B anzeigen, ist das synchron.Wenn ich jetzt 10 Tage warte, die Listen erneut erstelle und vergleiche, wie kann ich dann feststellen, ob etwas entfernt wurde?Ich kann nicht.Ich kann nur sagen, dass es Dateien auf Server A gibt, die nicht auf Server B gefunden werden und/oder umgekehrt.Dies kann daran liegen, dass eine Datei zu Server A hinzugefügt wurde (die Datei wird also nicht auf B gefunden) oder dass eine Datei auf Server B gelöscht wurde (die Datei wird also nicht auf B gefunden). mehr) ist etwas, das ich nicht allein anhand einer Liste von Dateinamen bestimmen kann.

Für die von mir vorgeschlagene Lösung gehe ich einfach davon aus, dass Sie eine Liste mit dem Namen OLD und eine Liste mit dem Namen NEW haben.Alles, was auf OLD, aber nicht auf NEW gefunden wurde, wurde entfernt.Alles, was auf NEU, aber nicht auf ALT gefunden wurde, wurde hinzugefügt (z. B.der Inhalt desselben Verzeichnisses auf demselben Server, jedoch wurden Listen zu unterschiedlichen Zeitpunkten erstellt).

Außerdem gehe ich davon aus, dass es keine Duplikate gibt.Das bedeutet, dass jedes Element auf beiden Listen einzigartig ist im Sinne von:Wenn ich diesen Artikel mit einem anderen Artikel auf der Liste vergleiche (unabhängig davon, wie dieser Vergleich funktioniert), kann ich immer sagen, dass der Artikel einer von beiden ist kleiner oder größer als der, mit dem ich es vergleiche, aber nie gleich.Z.B.Wenn ich mit Zeichenfolgen arbeite, kann ich sie lexikografisch vergleichen und dieselbe Zeichenfolge kommt nie zweimal in der Liste vor.

In diesem Fall ist die einfachste (allerdings nicht unbedingt beste) Lösung:

  1. Sortieren Sie die ALTEN Listen.Z.B.Wenn die Liste aus Zeichenfolgen besteht, sortieren Sie diese alphabetisch.Das Sortieren ist notwendig, weil es bedeutet, dass ich mithilfe der binären Suche schnell ein Objekt in der Liste finden kann, sofern es dort vorhanden ist (oder schnell feststellen kann, dass es überhaupt nicht in der Liste vorhanden ist).Wenn die Liste unsortiert ist, hat das Finden des Objekts eine Komplexität von O(n) (ich muss mir jedes einzelne Element in der Liste ansehen).Wenn die Liste sortiert ist, beträgt die Komplexität nur O(log n), da ich nach jedem Versuch, ein Element in der Liste zu finden, immer 50 % der Elemente in der Liste ausschließen kann, die nicht übereinstimmen.Selbst wenn die Liste 100 Elemente enthält, erfordert das Finden eines Elements (oder das Erkennen, dass das Element nicht auf der Liste steht) höchstens 7 Tests (oder sind es 8?Jedenfalls weit weniger als 100). Die NEUE Liste muss nicht sortiert werden.

  2. Jetzt führen wir die Listeneliminierung durch.Versuchen Sie für jedes Element in der NEUEN Liste, dieses Element in der ALTEN Liste zu finden (mithilfe der binären Suche).Wenn das Element gefunden wird, entfernen Sie dieses Element aus der ALTEN Liste und Auch Entfernen Sie es aus der NEUEN Liste.Dies bedeutet auch, dass die Listen kleiner werden, je weiter die Eliminierung voranschreitet, und die Suchvorgänge somit immer schneller werden.Da das Entfernen eines Elements aus einer Liste keinen Einfluss auf die korrekte Sortierreihenfolge der Listen hat, besteht während der Eliminierungsphase keine Notwendigkeit, die ALTE Liste erneut zu verwenden.

  3. Am Ende der Eliminierung könnten beide Listen leer sein, in diesem Fall wären sie gleich.Wenn sie nicht leer sind, sind alle Elemente, die sich noch auf der ALTEN Liste befinden, Elemente, die in der NEUEN Liste fehlen (andernfalls hätten wir sie entfernt), daher sind dies die Elemente entfernt.Alle Elemente, die sich noch auf der NEUEN Liste befinden, sind Elemente, die nicht auf der ALTEN Liste waren (wiederum hatten wir sie anderweitig entfernt), daher sind dies die hinzugefügte Artikel.

Sind die Objekte in der Liste „einzigartig“? In diesem Fall würde ich zum ersten Mal bauen zwei Karten (Hashmaps) und dann die Listen scannen und jedes Objekt in den Karten Nachschlag. 

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

Sorry für die schreckliche Metasprache Misch Ruby und Java :-P

Am Ende removedElements werden die Elemente enthalten, um list1 gehören, aber nicht beschränkt auf List2 und addedElements werden die Elemente, die zu list2 enthalten.

Die Kosten der gesamten Operation ist O (4 * N), da die Suche in der Karte / Wörterbuch konstant betrachtet werden. Auf der anderen Seite linear / binäre jeweils Elemente in den Listen suchen, wird diese O (N ^ 2) machen.

Bearbeiten : auf einem zweiten Gedanken die letzte Überprüfung in die zweite Schleife bewegen Sie eine der Schleifen entfernen ... aber das ist hässlich ...:) 

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top