[gelöst] 2 listen vergleichen ...

[debianator]

Hallo Leute,

ich habe hier 2 Listen.

Liste A habe ich selbst erstellt.

Liste B beziehe ich von Quellen im Internet, die diese Liste immer aktuell halten.

Einmal im Monat lade ich die aktuelle Liste B aus dem Internet und füge sie zusammen mit Liste A in eine .txt.

Dann führe ich folgendes Commando aus und als Ergebniss habe ich die ultimative Liste, die ich dann anwende:

Code: Alles auswählen

sort -f ./my_gurus.txt.bak | uniq > ./my_gurus.txt

Das Problem ist nun das Liste A mittlerweile ziemlich alte, nicht mehr gültige und somit unnötige Einträge enthält, die zu unnötigen Verzögerungen während der Anwendung führen können.

Ich konnte es zwar wenn ich sort -f weglasse mit uniq -u schonmal auf nur einmal vorkommende Zeilen eingegrenzt aber es sind immernoch zu viele Einträge um alle zu prüfen.

Also müsste ich irgendwie aus Liste A nur exakt die Zeilen auszugeben, die in Liste B nicht vorkommen, damit ich nur diese näher überprüfen kann.

Aber wie macht man sowas?

[ip]

hi,

guck mal unter

Code: Alles auswählen

diff

[debianator]

Diff kenne ich schon aber da komme ich auch auf mehrere Tausende Zeilen in der Ausgabe.

Das kann ich unmöglich alles nachprüfen.

Ich müsste es irgendwie schaffen das Liste A nur exakt die Zeilen ausgeben werden, die in Liste B nicht vorkommen.

Dann werden das nur ein paar Hundert Zeilen sein.

Hat niemand eine Idee?

[lemak]

Ich müsste es irgendwie schaffen das Liste A nur exakt die Zeilen ausgeben werden, die in Liste B nicht vorkommen.

Ich antworte mal wie in Jeopardy

Code: Alles auswählen

$ whatis comm
comm (1)             - Zwei sortierte Dateien Zeile für Zeile vergleichen

up

[Meillo]

Ich müsste es irgendwie schaffen das Liste A nur exakt die Zeilen ausgeben werden, die in Liste B nicht vorkommen.

Ich antworte mal wie in Jeopardy

Code: Alles auswählen

$ whatis comm
comm (1)             - Zwei sortierte Dateien Zeile für Zeile vergleichen

Ha! Das genau waere auch meine Antwort ... aeh Frage ... gewesen.

Comm(1) ist das passende Tool, wenn es auch fast vergessen ist.

[rendegast]

Code: Alles auswählen

grep [-v] -f listeB listeA

sollte das tun,
ABER
der Vorgang ist selbst bei ein paar (dutzend) Einträgen extrem rechenaufwändig,
Bsp. wsusoffline rödelt immer auf diesen Stellen herum:

Code: Alles auswählen

$ egrep "grep.*[-]f" wsusoffline70/sh/DownloadUpdates.sh
           grep -i -v -f ../exclude/ExcludeList-SPs.txt $static1 > ../temp/StaticUrls-${sys_old}-${lang}.txt
                grep -i -v -f ../exclude/ExcludeList-SPs.txt $static2 > ../temp/StaticUrls-${sys_old}-${lang}.txt
           grep -i -v -f ../exclude/ExcludeList-SPs.txt $static1 > ../temp/StaticUrls-${sys_old}-glb.txt
                grep -i -v -f ../exclude/ExcludeList-SPs.txt $static2 > ../temp/StaticUrls-${sys_old}-glb.txt
         grep -i -v -f ../exclude/ExcludeList-SPs.txt $static1 > ../temp/StaticUrls-${sys}-${lang}.txt
                grep -i -v -f ../exclude/ExcludeList-SPs.txt $static2 > ../temp/StaticUrls-${sys}-${lang}.txt
grep -F -f ../temp/SupersedingRevisionIds.txt ../temp/ValidUpdateRevisionIds.txt >> ../temp/ValidSupersedingRevisionIds.txt
grep -F -f ../temp/ValidSupersedingRevisionIds.txt ../temp/SupersededUpdateRelations.txt > ../temp/ValidSupersededUpdateRelations.txt
grep -F -f ../temp/ValidSupersededRevisionIds.txt ../temp/BundledUpdateRelationsAndFileIds.txt > ../temp/SupersededRevisionAndFileIds.txt
grep -F -f ../temp/SupersededFileIdsUnique.txt ../temp/UpdateCabExeIdsAndLocations.txt >> ../temp/SupersededCabExeIdsAndLocations.txt
        grep -i -v -f ../temp/Expiredid-${sys}.txt ../temp/Urls-${sys}-${lang}.txt > ../temp/tmpUrls-${sys}-${lang}.txt
        grep -i -f ../temp/Validid-${sys}.txt ../temp/Urls-${sys}-${lang}.txt >> ../temp/tmpUrls-${sys}-${lang}.txt
        grep -i -v -f ../temp/tmpExcludeList-${sys}.txt ../temp/tmpUrls-${sys}-${lang}.txt > ../temp/ValidUrls-${sys}-${lang}.txt
                grep -i -f ../temp/Validid-${sys}.txt ../temp/Urls-${sys}-glb.txt > ../temp/tmpValidUrls-${sys}-glb.txt
                grep -i -v -f ../temp/Expiredid-${sys}.txt ../temp/Urls-${sys}-glb.txt >> ../temp/tmpValidUrls-${sys}-glb.txt
        grep -i -v -f ../temp/tmpExcludeList-${sys}.txt ../temp/tmpValidUrls-${sys}-glb.txt > ../temp/ValidUrls-${sys}-glb.txt
                grep -i -f ../temp/Validid-${sys}.txt ../temp/Urls-${sys}-glb.txt > ../temp/tmpValidUrls-${sys}-glb.txt
                grep -i -v -f ../temp/Expiredid-${sys}.txt ../temp/Urls-${sys}-glb.txt >> ../temp/tmpValidUrls-${sys}-glb.txt
        grep -i -v -f ../temp/tmpExcludeList-${sys}.txt ../temp/tmpValidUrls-${sys}-glb.txt > ../temp/ValidUrls-${sys}-glb.txt
        grep -i -v -f ../temp/tmpExcludeList-win-x86.txt ../temp/Urls-win-x86-${lang}.txt > ../temp/ValidUrls-win-x86-${lang}.txt
  grep -F --file=../temp/OfficeFileIds.txt ../temp/UpdateCabExeIdsAndLocations.txt > ../temp/OfficeUpdateCabExeIdsAndLocations.txt
    grep -F -i -v -f ../temp/ExcludeList-${sys}.txt ../temp/DynamicDownloadLinks-${sys}-${lang}.txt > ../temp/ValidDynamicLinks-${sys}-${lang}.txt

[uname]

egrep "grep.*[-]f" wsusoffline70/sh/DownloadUpdates.sh

Was willst du denn damit überhaupt erreichen? Die grep-Suche sollte doch nur einzelne Dateien durchsuchen.

Ich habe mal vor einiger Zeit ein Perl-Script geschrieben. Das Programm liest jede Zeile beider Dateien ein und baut daraus Hash-Variablen. Am Ende werden die Unterschiede beider Dateien oder auch nur eine Datei zur anderen ausgegeben. Die Software ist nicht gerade speichersparend geschrieben, so dass es bei einigen Millionen Zeilen zu Speicherproblemen kommen kann.

http://nopaste.debianforum.de/36226

Code: Alles auswählen

chmod 755 diff.pl

Code: Alles auswählen

./diff.pl datei1 datei2  (Ausgabe aller Unterschiede mit Namen zur Kennzeichnung)

Code: Alles auswählen

./diff.pl datei1 datei2 datei1 (Ausgabe Unterschiede nur von datei1 nicht von datei2)
./diff.pl datei1 datei2 datei2 (Ausgabe Unterschiede nur von datei2 nicht von datei1)

Anmerkung:
Der Software ist es egal ob eine Zeile mehrfach vorkommt. Kommt eine Zeile in einer Datei einmal und in der anderen zweimal vor so gibt es keine Abweichung. Auch wird die Zeilenreihenfolge nicht beachtet.

[Meillo]

Code: Alles auswählen

grep [-v] -f listeB listeA

sollte das tun,
ABER
der Vorgang ist selbst bei ein paar (dutzend) Einträgen extrem rechenaufwändig, [...]

Ich habe mal vor einiger Zeit ein Perl-Script geschrieben. Das Programm liest jede Zeile beider Dateien ein und baut daraus Hash-Variablen. Am Ende werden die Unterschiede beider Dateien oder auch nur eine Datei zur anderen ausgegeben. Die Software ist nicht gerade speichersparend geschrieben, so dass es bei einigen Millionen Zeilen zu Speicherproblemen kommen kann.

Ich frage mich, weshalb noch aufwendige und gleichzeitig eingeschraenkte Loesungsvorschlaege gemacht werden, wo das Problem mit dem einfachen Tool comm(1) (das in POSIX und demnach ueberall verfuegbar ist) schon laengst geloest ist. Zumindest sehe ich keine bedeutende Verbesserung gegenueber dem Ansatz mit comm.

Anmerkung:
Der Software ist es egal ob eine Zeile mehrfach vorkommt. Kommt eine Zeile in einer Datei einmal und in der anderen zweimal vor so gibt es keine Abweichung. Auch wird die Zeilenreihenfolge nicht beachtet.

Gut, fuer comm will man meistens `sort -u' auf die Eingangsdateien anwenden. Aber soweit war der Fragende ja schon.

[rendegast]

Ich frage mich, weshalb noch

Weitere Möglichkeiten.

egrep "grep.*[-]f" wsusoffline70/sh/DownloadUpdates.sh
Was willst du denn damit überhaupt erreichen?

Nur ein Beispiel des grep-Konstrukts in einer Anwendung.
Für das eigentliche Threadproblem war 'grep [-v] -f listeB listeA'.

Die "Performace" des Konstrukts:

Code: Alles auswählen

$ time ls -1 /var/lib/dpkg/info/
...

real    0m0.109s
user    0m0.012s
sys     0m0.020s
$ time ls -1 /var/lib/dpkg/info/ | grep -v -f /etc/fstab 

real    0m2.400s
user    0m2.396s
sys     0m0.016s
$ time ls -1 /var/lib/dpkg/info/ | grep -o -f /etc/fstab 

real    0m8.912s
user    0m8.909s
sys     0m0.020s

zeigt, daß am Tool grep noch Verbesserungsbedarf besteht
(Vielleicht zumindest ein Hinweis in der Manpage über den in diesem Fall schlechten Algorithmus?).
Oder in gewissen Fällen die Daten einer Vorbereitung bedürfen.

[pferdefreund]

Beide Listen als Tabellen in ne mysql oder postgresql-DB laden und mit select ... where not exists... auswerten.
Wird wohl am schnellsten gehen, insbesondere, wenn es möglich sein sollten, nen Index zu verwenden. Aber selbst ohne ist
hier ne relationale DB -zumindest für mich - die einfachste Lösung.

[Meillo]

Ich frage mich, weshalb noch

Weitere Möglichkeiten.

Leider fehlt ihnen IMO entweder Eleganz oder Mehrwert.

Die "Performace" des Konstrukts:

Code: Alles auswählen

$ time ls -1 /var/lib/dpkg/info/ | grep -v -f /etc/fstab 

real    0m2.400s
user    0m2.396s
sys     0m0.016s
$ time ls -1 /var/lib/dpkg/info/ | grep -o -f /etc/fstab 

real    0m8.912s
user    0m8.909s
sys     0m0.020s

zeigt, daß am Tool grep noch Verbesserungsbedarf besteht

Ich verstehe nicht, weshalb du `grep -o' gegen `grep -v' vergleichst. Zudem enthaelt die fstab ja gar keine sinnvollen Patterns und wenn dann waeren es feste Strings und keine Patterns -> fgrep.

(Vielleicht zumindest ein Hinweis in der Manpage über den in diesem Fall schlechten Algorithmus?).

Ich glaube bevor man hier urteilen kann, sollte man erst in der Sprachentheorie fit sein und dann die konkreten Implementierungen nach ihnen Automatentypen unterscheiden (NFA, DFA, gemischt). Fuer den zweiten Teil kann ich Friedls ``Mastering Regular Expressions'' empfehlen. Fuer die Theorie gibt's zum Beispiel ``Einfuehrung in die Automatentheorie, Formale Sprachen und Komplexitaetstheorie'' von Hopcroft und Ullman. Danach koennen wir uns ueber den Hinweis in der Manpage unterhalten.


Ich sehe schon, wir schweifen ab und eigentlich sollte ich besser was Sinnvolles arbeiten ....

[Meillo]

Beide Listen als Tabellen in ne mysql oder postgresql-DB laden und mit select ... where not exists... auswerten.
Wird wohl am schnellsten gehen, insbesondere, wenn es möglich sein sollten, nen Index zu verwenden.

Will das jemand gegen den comm-Ansatz messen?

Code: Alles auswählen

sort -u list-a >list-a.sorted
sort -u list-b >list-b.sorted
comm -1 list-?.sorted

Ich glaube der Vergleich und die Abfrage werden in der Datenbank richtig schnell sein. Aber wie schnell ist das Einfuegen und das Erzeugen des Indexes? (Zudem das Anlegen der Tabelle.)

Ich bin ehrlich an Zahlen interessiert.

[rendegast]

@Meillo

Ich verstehe nicht, weshalb du `grep -o' gegen `grep -v' vergleichst.

Ich habe einfach ~ 4300 Zeilen (ls dpkg/info/) gegen ~ 200 Zeilen Patternfile (fstab) verglichen.
Der Vergleich sollte keine Ausgabe erzeugen, darum ging es nicht.
Nur darum, daß grep hier bis zu 9 Sekunden herumrechnet (2.9GHz).

Zudem enthaelt die fstab ja gar keine sinnvollen Patterns und wenn dann waeren es feste Strings und keine Patterns -> fgrep.

Das ist natürlich großartig und löst das Problem. Nicht dran gedacht.
In einigen Fällen verwendet wsusoffline ja 'grep -F -f ...' (fgrep),
aber in anderen Fällen nicht, und die sind rechenintensiv.

Damit ist

Code: Alles auswählen

fgrep [-v] -f listeB listeA

doch das eleganteste (wenn es die Daten erlauben)?

[Meillo]

Ich verstehe nicht, weshalb du `grep -o' gegen `grep -v' vergleichst.

Ich habe einfach ~ 4300 Zeilen (ls dpkg/info/) gegen ~ 200 Zeilen Patternfile (fstab) verglichen.
Der Vergleich sollte keine Ausgabe erzeugen, darum ging es nicht.
Nur darum, daß grep hier bis zu 9 Sekunden herumrechnet (2.9GHz).

Ist ja auch klar, denn grep muss unglaublich viel Arbeit tun. Wenn ein Algorithmus eine quadratische Laufzeit hat, dann ist sie eben quadratisch.

In deinem Beispiel sind's 4300*200 Vergleiche, falls kein Suchstring vorkommt. Sonst sind's immer noch durchschnittlich 4300*100 Vergleiche.

Bei zwei Listen mit jeweils n=4300 unsortierten Zeilen. Kommen wir mit `fgrep -f' auf eine Laufzeit von rund: n*(n/2) = 4300*2150 = 9.245.000 Operationen. Mit 2x sort und comm sind es rund: 2 * (n*log(n)) + n = 2 * (4300*3.6) + 4300 = 35.547 Operationen. Man kann das zwar nicht so einfach rechnen, aber ich glaube man bekommt eine grobe Vorstellung um welche Groessenordnungen es geht. Fachleute auf diesem Gebiet moegen mich verbessern und belehren.

Code: Alles auswählen

fgrep [-v] -f listeB listeA

doch das eleganteste (wenn es die Daten erlauben)?

Was ist mit Teilmatches? In Liste B gibt es eine Zeile die *in* einer Zeile in Liste A auftaucht? Man muesste alles an Zeilenanfang und -ende ankern.

Fuer den User mag diese Anweisung einfach zu tippen sein, aber die von fgrep getane Arbeit ist IMO nicht elegant.

Trotzdem danke fuer die Idee, auf die ich bisher noch nicht gekommen bin. Ich werde sie in mein Repertoire aufnehmen.

[debianator]

Achja genau, Teilmatches hatte ich auch noch aber die diff.pl ist wie massgeschneidert, vielen Dank dafür.