ubuntuusers.de

Abend,

ich suche eine Möglichkeit eine ca. 100.000 Einträge-Datei1 (nach Eintragschema pro Zeile "wort1 wort2 wort3 wort4") mit einer zweiten ca. 75.000 Einträge-Datei zu durchsuchen...und das innerhalb einer Minute...Ist das überhaupt möglich???

Zusammenfassung: Vergleiche Datei 1 mit Datei 2 und zähle wie oft ein Eintrag vorkommt und schreibe es in eine/mehrere Dateien

mit

sed -d '/wort1 wort2 wort3 wort4/p' Datei | wc -l

habe ich es schon probiert - dauert aber zu lange

mit

split -d -l 1000 Datei

um die Dateien kleiner zu machen und sie dann über mehrere Befehle (Befehl & Befehl) gleichzeitig laufen zu lassen ist auch nicht schneller

halloICKEbins schrieb:

Zusammenfassung: Vergleiche Datei 1 mit Datei 2 und zähle wie oft ein Eintrag vorkommt und schreibe es in eine/mehrere Dateien

Hab ich das richtig verstanden: Du hast also eine Datei ($suchdatei), und willst für jede Zeile in dieser Datei eine andere Datei ($datendatei) durchsuchen und die Ergebnisse zählen?

Ich würde das so machen:

1

cat $suchdatei | tr '\n' '\0' | xargs -0 -n 1 -P 4 -I {} sh -c 'grep "{}" $datendatei | wc -l | sed "s/^/{} /"'

Erklärung:

• cat suchdatei sollte klar sein

• Mit tr ersetzt du den Zeilenumbruch durch ein Null-Zeilen damit xargs den Input zeilenweise (statt wort-weise) interpretieren kann

• xargs nimmt den Input und führt damit einen Befehl aus

  • -0 bewirkt, dass der Input null-terminiert interpretiert wird (und eben nicht wort-weise)

  • -n 1 legt fest, dass nur ein Input-Parameter an den nachfolgenden Befehl übergeben wird (in diesem Fall heißt es also, dass nur eine Suchzeile übergeben wird)

  • -P 4 ist für die Parallelisierung da: Es werden 4 Prozesse gleichzeitig gestartet

  • -I {} definiert eine Zeichenfolge, die durch den Input (also deine Suchzeile) ersetzt wird

  • sh -c: Das ist das Kommando, welches ausgeführt wird. Da wir eigentlich mehrere Befehle benötigen, müssen wir diese in eine Shell-Instanz auslagern. Innerhalb dieser Shell wird dann folgendes ausgeführt:

    • grep "{}" $datendatei durchsucht die Datendatei nach der Suchzeile

    • wc -l zählt die Ergebnisse

    • sed ...: Damit wird einfach der Suchbegriff nochmal vorne rangestellt, da du sonst ja nicht weißt, auf welche Suchzeile sich die Anzahl bezieht (es werden ja mehrere Prozesse gleichzeitig gestartet, welche unterschiedlich lang dauern können, und damit bleibt die Reihenfolge nicht erhalten)

Ob das ganze jetzt wirklich schneller ist, kann ich nicht sagen. Wenn das keine kritischen Daten sind kannst du die Dateien ja mal zur Verfügung stellen.

halloICKEbins schrieb:

ich suche eine Möglichkeit eine ca. 100.000 Einträge-Datei1 (nach Eintragschema pro Zeile "wort1 wort2 wort3 wort4") mit einer zweiten ca. 75.000 Einträge-Datei zu durchsuchen...und das innerhalb einer Minute...Ist das überhaupt möglich???

Das hängt im Wesentlichen von deinem Rechner ab... mit einer dicken CPU, viel RAM, schnellem I/O und einem effizient implementierten Programm ist fast nichts unmöglich 😀

Zusammenfassung: Vergleiche Datei 1 mit Datei 2 und zähle wie oft ein Eintrag vorkommt und schreibe es in eine/mehrere Dateien

Nur um das zu präzisieren: Du hast eine Datei, die du zeilenweise durchsuchen willst und die Suchbegriffe stehen jeweils in einer eigenen Zeile einer zweiten Datei. Dich interessiert nur, wie oft der Suchbegriff vorkommt.

grep kann mit dem Argument -c selber Treffer zählen (das spart einem die wc -l Aufrufe) und paste scheint noch etwas schneller als sed zu sein, wenn es darum geht die Suchbegriffe und die Häufigkeit aneinander zu kleben Edit: paste macht keinen Sinn, wenn man mit xargs parallelisiert:

$ time paste suchdaten.txt <(cat suchdaten.txt | tr '\n' '\0' | xargs -0 -n 1 -P 4 -I {} sh -c 'grep -c "{}" big_data.txt | sed "s/^/{} /"' ) 

Ich bin mir nicht sicher, ob ich richtig verstehe, aber das klingt nach einer Aufgabe für fgrep mit seinem fürchterlich schnellen Algorithmus.

Mooi schrieb:

Ich bin mir nicht sicher, ob ich richtig verstehe, aber das klingt nach einer Aufgabe für fgrep mit seinem fürchterlich schnellen Algorithmus.

Man kann die Anzahl der Zeilen mit Treffern sehr einfach und schnell ermitteln:

1

fgrep -cf "$suchdatei" "$datendatei"

Dabei wird aber eine Zeile, die mehrere Suchwörter enthält, nur einmal gezählt. Wenn man alle Wörter zählen will, kann man das so machen:

1

fgrep -of "$suchdatei" "$datendatei" | wc -l

Wenn die Summen pro Suchwort ausgegeben werden sollen, wird es etwas komplizierter.

misterunknown schrieb:

Ich würde das so machen:

1	cat $suchdatei | tr '\n' '\0' | xargs -0 -n 1 -P 4 -I {} sh -c 'grep "{}" $datendatei | wc -l | sed "s/^/{} /"'

Das ist viel zu umständlich: der cat und tr sind überflüssig. Stattdessen:

1

xargs -a "$suchdatei" -d \\n -n 1 -I {} sh -c 'grep "{}" $datendatei | wc -l | sed "s/^/{} /"'

Und dann, um noch ein paar Shell-Prozesse zu sparen

1

xargs -a "$suchdatei" sh -c 'for w; do echo -n "$w: "; fgrep -ce "$w" "$datendatei"; done' --

Ich nehme an, dass mehrere Wörter pro Zeile einzeln gelesen werden sollen. Unschön ist hier immer noch, dass die $datendatei mehrfach gelesen wird. Das wird aber etwas umständlicher und dafür fehlt mir gerade die Zeit.

halloICKEbins schrieb:

Zusammenfassung: Vergleiche Datei 1 mit Datei 2 und zähle wie oft ein Eintrag vorkommt und schreibe es in eine/mehrere Dateien

Ist das denn ein einfacher zeilenweiser Vergleich oder willst du auch nach Substrings in den Zeilen suchen können?

Sind die Dateien sortiert?

Kannst Du sie umsortieren?

Sortierte Dateien lassen sich nämlich sehr effizient mit einem Spreizschritt (kein Fachwort dafür) durchsuchen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

d1:
1
3
7
9

d2
2
3
4
7
8

• Du nimmst die kleinste Zeile aus jeder Datei.

  • Loop solange noch Zeilen da sind

  • Sind sie gleich: Ding-Dong und nächste Zeile aus beiden Dateien

  • Sind sie ungleich: Nimm die nächste Zeile aus der Datei mit der kleineren Zeile.

1
2
3
4
5
6

1 2 
3 2
3 3 ding dong
7 4
7 7 ding dong
9 8 

Wenn man das Zeug nicht sinnlos mehrfach liest, ist so eine Liste von 100000 Einträgen im Grunde nicht wirklich viel.
Und etwas schnelleres als fgrep wirst Du zum vergleichen auch nicht finden.

Dazu gerade mal - so als "Proof-of-Concept" - getestet: ^{(Dabei bestehen die "Wörter" hier mal einfach aus Zufallszahlen < 32768)}

track@track:~$ time for (( i=1; i<=75000; i++)); do echo $RANDOM; done  > zufall.liste

real	0m8.973s
user	0m5.052s
sys	0m1.664s
track@track:~$ time for (( i=1; i<=100000; i++)); do echo $RANDOM; done  > zufall.daten

real	0m11.995s
user	0m6.760s
sys	0m2.236s
track@track:~$ time fgrep -of zufall.liste  zufall.daten > /dev/null

real	0m0.472s
user	0m0.384s
sys	0m0.028s
track@track:~$ head zufall.liste
11831
16882
4734
14280
15016
7059
29145
25069
5640
31351 

Das ist jetzt nur der nackte Vergleich, ohne jede statistische Auswertung. (die käme dahinter)
Aber selbst mit Deiner originalen Datengröße (ok, die Wörter sind vielleicht zu kurz ...) läuft das in unter 1 Sekunde.

Das heißt, dass Du in dieser Richtung Deine 1 Minute bequem einhalten kannst.
- Du musst jetzt nur noch klären, wie Du die Suchkriterien genau ansetzt. (z.B. im Fall von doppelten Wörtern in der Suchliste)

LG,

track

p.s.: - Vermutlich wird man sogar eher mit fgrep -wof suchen (→ siehe man grep), damit nur komplette Treffer zählen, und keine Teilwörter.

pps.: ... und eine ausgezählte Liste könnte ± so aussehen:

track@track:~$ time fgrep -wof zufall.liste  zufall.daten | sort | uniq -c | head
      1 1
      3 10
      5 100
      5 1000
      4 10000
      2 10001
      7 10002
      4 10003
      1 10004
      3 10006

real	0m2.010s
user	0m1.916s
sys	0m0.040s 

... und auch das liegt immer noch weit unter 1 Minute. 😉

Wenn man für ganze Zeilen

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#!/usr/bin/env python
from collections import Counter

search_file = "search_by_lines.txt"
data_file = "data.txt"

with open(search_file) as search_terms, open(data_file) as data:
    data_counter = Counter(data)
    for search_term in search_terms:
        print(search_term.rstrip(), data_counter[tuple(search_term.split())])

bzw. für die in einer Zeile möglichen aufeinander folgenden Wortkombinationen Hashes bauen darf

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#!/usr/bin/env python3
from collections import Counter, deque

search_file = "search_by_words.txt"
data_file = "data.txt"

words_per_line = 4

with open(search_file) as search_terms, open(data_file) as data:
    data_elements = deque()
    for l in data:
        elements = l.split()
        for i in range(words_per_line):
            for n in range(i + 1, words_per_line + 1):
                data_elements.append(tuple(elements[i:n]))

    data_counter = Counter(data_elements)
    for search_term in search_terms:
        print(search_term.rstrip(), data_counter[tuple(search_term.split())])

geht das in Python3 auch recht flott (letzteres liegt mit Testdaten mit 100k Zeilen mit 4 Zufallszahlen pro Zeile und Suchdaten mit 75k Zeilen bei etwas über einer Sekunde (wenn man das Ergebnis in eine Datei schreiben lässt, mit der Ausgabe auf stdout sind es etwas mehr als 2 Sekunden) in einer VM auf einem Core i5 2500) - die Sortierung ist dabei egal und man muss nur einmal über jede Datei laufen.

collections.Counter nimmt einen Iterator, bildet für die von ihm gelieferten Elemente Hashwerte und zählt wie oft sie auftreten. Mit den Suchbegriffen kann man dann die Häufigkeit für die Werte abfragen, die einen interessieren.

seahawk1986 schrieb:

Wenn man für ganze Zeilen

geht das in Python3 auch recht flott (letzteres liegt mit Testdaten mit 100k Zeilen mit 4 Zufallszahlen pro Zeile und Suchdaten mit 75k Zeilen bei etwas über einer Sekunde (wenn man das Ergebnis in eine Datei schreiben lässt, mit der Ausgabe auf stdout sind es etwas mehr als 2 Sekunden) in einer VM auf einem Core i5 2500) - die Sortierung ist dabei egal und man muss nur einmal über jede Datei laufen.

Das ist lobenswert.

collections.Counter nimmt einen Iterator, bildet für die von ihm gelieferten Elemente Hashwerte und zählt wie oft sie auftreten. Mit den Suchbegriffen kann man dann die Häufigkeit für die Werte abfragen, die einen interessieren.

Wieder was über Python gelernt. Vielen Dank! 👍

In Ruby würde ich Wörter so zählen:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#!/usr/bin/ruby

def each_word(io, &b)
  io.each_line do |line|
    line.scan(/\w+/, &b)
  end
end

counters = {}

File.open(ARGV.shift || abort("ERROR: Need a list of search terms.")) do |io|
  each_word(io) {|word| counters[word] = 0}
end

each_word(ARGF) do |word|
  c = counters[word] and counters[word] = c + 1
end

totals = 0

counters.each do |word, count|
  printf "%10d %s\n", count, word
  totals += count
end

printf "\n%10d TOTALS\n", totals

Der Ansatz ist ähnlich wie der von seahawk1986 - allerdings mit dem Unterschied, dass die Liste mit Suchbegriffen benutzt wird, um selektiv zu zählen. Wörter, die nicht in der Suchmenge sind, werden nicht gezählt (die Bedingung in Zeile 16). Das kann einen Unterschied machen, wenn die Eingabe sehr viele Wörter enthält, die man gar nicht zählen will.

@seahawk1986

Abend,

habe mich mal ein wenig mit Python beschäftigt...sehr sehr schnell beim Durchsuchen aber irgendwie habe ich noch Probleme mit meinem Script

search_file = "file2"
data_file = "file1"
count = 0

with open(search_file) as search_terms, open(data_file) as data_terms:
    for line1 in search_terms:
        for line2 in data_terms:
            if line1 == line2:
                count += 1
        print (line1.rstrip(), count)
        count = 0

Inhalt von file 1

1
2
3
4
5
6
7

string1
string2
string2
string1
string3
string2
string2

Inhalt von file 2

1
2
3

string1
string2
string3

1
2
3
4
5
6
7
8
9

Ich würde jetzt erwarten, dass er mir das Nachfolgende ausgibt:
string1 2
string2 4
string3 1

Ich bekomme aber die nachfolgende Ausgabe:
string1 2
string2 0
string3 0

Nachtrag:

search_file = "file2"
data_file = "file1"
count = 0

with open(search_file) as search_terms, open(data_file) as data_terms:
    for line1 in search_terms:
        for line2 in data_terms:
            print (line2.rstrip())

Jetzt würde ich erwarte, dass er mir 3x file1 hintereinander ausgibt, also

string1
string2
string2
string1
string3
string2
string2
string1
string2
string2
string1
string3
string2
string2
string1
string2
string2
string1
string3
string2
string2

er gibt es aber nur einmal aus:

string1
string2
string2
string1
string3
string2
string2

Wieso???

Weil du mit dem Konstrukt jeweils zeilenweise über Dateien iterierst und der Iterator keine Daten mehr liefert, sobald er am Ende der Datei angelangt ist. Wenn du den Cursor in der Datei wieder an den Anfang bewegst (das geht mit seek()), kannst du erneut über die Datei iterieren:

1
2
3
4
5
6
7
8
9

search_file = "file2"
data_file = "file1"
count = 0

with open(search_file) as search_terms, open(data_file) as data_terms:
    for line1 in search_terms:
        for line2 in data_terms:
            print (line2.rstrip())
        data_terms.seek(0)

Aber wenn du mehrfach Dateien einliest und eine Menge Stringvergleiche durchführst, verspielst du wieder den Geschwindigkeitsvorteil, den dir der collections.Counter verschafft.

Aso ... Problem an deiner Methode ist, dass ich es irgendwie nicht zum laufen bekomme...

#!/usr/bin/env python
from collections import Counter

search_file = "file2"
data_file = "file1"

import sys
f = open("output.txt","w")
sys.stdout = f

with open(search_file) as search_terms, open(data_file) as data:
    data_counter = Counter(data)
    for search_term in search_terms:
        print(search_term.rstrip(), data_counter[tuple(search_term.split())])

Ergebnis des Scripts ist folgendes:

1
2
3

string1 0
string2 0
string3 0