Big Daten sortieren und suchen

Question

Ich habe zwei Dateien von Daten, 100 Zeichen Linien jedem. Datei A: 10 ⁸ Linien, Datei B: 10 ⁶ Linien. Und ich brauche alle die Saiten von Datei B zu finden, die nicht in der Datei A. Was ist Zuerst dachte ich beiden Dateien zu mysql Fütterung, aber es sieht aus wie es nicht immer wird fertig einen eindeutigen Schlüssel auf 10 zu schaffen ⁸ Aufzeichnungen.

Ich bin für Ihre Anregungen auf diese warten.

Answer 1

Sie können diesen Vorgang ausführen, ohne eine Datenbank. Der Schlüssel ist, um die Größe von A zu reduzieren, da ein viel größer als B. Hier ist, wie dies zu tun:

berechnen 64-Bit-Hash-Werte eine anständige Hash-Funktion für die Zeichenfolge in der B-Datei. Bewahren Sie diese im Speicher (in einer Hash-Tabelle), die Sie tun können, weil B klein ist. Dann Hash alle Saiten in Ihrer A-Datei, Zeile für Zeile, und sehen, ob jeder einen Hash für Ihre B-Datei übereinstimmt. Alle Zeilen mit Matching-Hashes (einer von B) sollten in einer Datei C

gespeichert werden

Wenn dieser Prozess abgeschlossen ist Datei C die kleine Teilmenge von A von potentiell passenden Strings haben (auf B). Jetzt haben Sie eine viel kleinere Datei C, dass Sie mit den Linien der B vergleichen müssen. Dadurch verringert sich das Problem zu einem Problem, wo man tatsächlich alle Zeilen von C in den Speicher (als Hash-Tabelle) laden und jede Zeile von B zu vergleichen, um zu sehen, ob es in C ist.

Answer 2

Sie können leicht verbessern @ michael-goldshteyn Antwort ( https://stackoverflow.com/a/3926745/179529). Da Sie alle Fäden in B finden müssen, die nicht in A sind, können Sie ein beliebiges Element aus der Hash-Tabelle der Elemente von B entfernen, wenn Sie vergleichen und ein Spiel für sie mit den Elementen in A. Die Elemente dieser Wille finden bleiben in der Hash-Tabelle sind die Elemente, die nicht in der Datei A. gefunden

Answer 3

Für die Größen, die Sie erwähnen, sollten Sie sofort im Speicher der Lage sein, alle B zu halten, so dass Sie eine vereinfachte Version von Goldshteyn Antwort tun könnte; so etwas wie dies in Python:

#!/usr/bin/python3

import sys

if __name__=='__main__':
  b = open(sys.argv[2],'r')
  bs = set()
  for l in b:
    bs.add(l.strip())
  b.close()
  a = open(sys.argv[1],'r')
  for l in a:
    l = l.strip()
    if l in bs:
      bs.remove(l)
  for x in bs:
    print(x)

Ich habe das 10 ^ auf zwei Dateien von 5 und 10 ^ 7 in Größe getestet mit ~ 8 Zeichen pro Zeile auf einem Atom-Prozessor. Die Ausgabe von / usr / bin / time:

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244