Wie finde ich die Unterschiede zwischen zwei fast identischen Dateien sehr schnell?

8

Wenn Sie zwei weitgehend identische Dateien mit mehreren tausend Datensätzen haben, wie schreiben Sie Code, um Unterschiede zwischen ihnen zu finden. Angenommen, Unix / Linux-Befehle dürfen nicht verwendet werden.

Meine Idee:

Da die meisten Einträge gleich sind, können wir die Einträge der zwei Dateien sortieren und dann jeden Eintrag einzeln vergleichen, z. Eintrag i in Datei1 Vergleich mit Eintrag i in Datei2. Es ist O (n lg n), n ist die Größe der Datei.

Gibt es eine O (n) Lösung?

    
Jack 27.10.2011, 04:48
quelle

1 Antwort

3

Hashtabellen sind deine Freunde.

  1. Erhalte einen Datensatz aus Datei 1.
  2. Hash es.
  3. Erhalte die entsprechende Speicheradresse.
  4. Setze es auf 1 .
  5. Wiederholen Sie dies für alle Datensätze in Datei 1.
  6. Wiederholen Sie für alle Datensätze in Datei 2, aber fügen Sie 2 hinzu, anstatt auf 1 zu setzen.

Jetzt wissen Sie, welcher Datensatz in beiden Dateien existiert (Wert 3), welcher nur in der ersten Datei existiert (Wert 1) und welcher nur in der zweiten Datei existiert (Wert 2). Und in linearer Zeit.

Hinweis: Wenn Sie eine eigene Hash-Tabelle implementieren, müssen Sie bei Bedarf die Größe Ihrer Tabelle und Kollisionen erhöhen. Ich bin sicher, wenn Sie das tun könnten, dann würden Sie mit dieser Frage keine harte Zeit haben, also benutzen Sie eine Bibliothek.

    
bdares 27.10.2011, 05:04
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Anzeige der genauen Sql nach der Parametersubstitution C #