Der beste Weg, um "Gruppieren nach" von Bash zu simulieren?

231

Angenommen, Sie haben eine Datei mit IP-Adressen, eine Adresse in jeder Zeile:

10.0.10.1
10.0.10.1
10.0.10.3
10.0.10.2
10.0.10.1

Sie benötigen ein Shell-Skript, das für jede IP-Adresse zählt, wie oft sie in der Datei angezeigt wird. Für die vorherige Eingabe benötigen Sie die folgende Ausgabe:

10.0.10.1 3
10.0.10.2 1
10.0.10.3 1

Eine Möglichkeit, dies zu tun, ist:

cat ip_addresses |uniq |while read ip
do
    echo -n $ip" "
    grep -c $ip ip_addresses
done

Es ist jedoch weit davon entfernt, effizient zu sein.

Wie würden Sie dieses Problem mit bash effizienter lösen?

(Eine Sache zum Hinzufügen: Ich weiß, dass es von Perl oder Awk gelöst werden kann. Ich bin an einer besseren Lösung in Bash interessiert, nicht in diesen Sprachen.)

ZUSÄTZLICHE INFORMATION:

Angenommen, die Quelldatei ist 5 GB groß und der Computer, auf dem der Algorithmus ausgeführt wird, verfügt über 4 GB. Sortieren ist also keine effiziente Lösung, und die Datei wird auch nicht mehr als einmal gelesen.

Ich mochte die Hashtable-ähnliche Lösung - kann jemand Verbesserungen an dieser Lösung vornehmen?

ZUSÄTZLICHE INFO # 2:

Einige Leute fragten, warum ich mir die Mühe machen würde, es in Bash zu machen, wenn es in Perl viel einfacher ist. Der Grund ist, dass auf der Maschine, die ich machen musste, diese Perl für mich nicht verfügbar war. Es war eine speziell angefertigte Linux-Maschine ohne die meisten Tools, die ich gewohnt bin. Und ich denke, es war ein interessantes Problem.

Also bitte, beschuldigen Sie die Frage nicht, ignorieren Sie sie einfach, wenn Sie sie nicht mögen. :-)

Zizzencs
quelle
Ich denke, Bash ist das falsche Werkzeug für den Job. Perl wird wahrscheinlich eine bessere Lösung sein.
Francois Wolmarans
Werfen Sie einen Blick auf IPV4 Subnetzliste Cleaner (in CIDR-Notation)
F. Hauri

Antworten:

412
sort ip_addresses | uniq -c

Dadurch wird zuerst die Anzahl gedruckt, aber ansonsten sollte es genau das sein, was Sie wollen.

Joachim Sauer
quelle
71
Diese können Sie dann an "sort -nr" weiterleiten, um sie in absteigender Reihenfolge von der höchsten zur niedrigsten Anzahl zu sortieren. dhsort ip_addresses | uniq -c | sort -nr
Brad Parks
15
Und sort ip_addresses | uniq -c | sort -nr | awk '{ print $2, $1 }'um die IP-Adresse in der ersten Spalte zu erhalten und in der zweiten zu zählen.
Raghu Dodda
noch eine Optimierung für Sortierteil:sort -nr -k1,1
Andrzej Martyna
49

Die schnelle und schmutzige Methode ist wie folgt:

cat ip_addresses | sort -n | uniq -c

Wenn Sie die Werte in bash verwenden müssen, können Sie den gesamten Befehl einer bash-Variablen zuweisen und dann die Ergebnisse durchlaufen.

PS

Wenn der Befehl sort weggelassen wird, erhalten Sie nicht die richtigen Ergebnisse, da uniq nur aufeinanderfolgende identische Zeilen betrachtet.

Francois Wolmarans
quelle
In
Bezug auf die
Quadratische Bedeutung O (n ^ 2) ?? Das würde sicherlich vom Sortieralgorithmus abhängen, es ist unwahrscheinlich, dass eine solche falsche Sortierung verwendet wird.
Paxdiablo
Nun, im besten Fall wäre es O (n log (n)), was schlimmer ist als zwei Durchgänge (was Sie mit einer trivialen Hash-basierten Implementierung erhalten). Ich hätte "superlinear" statt quadratisch sagen sollen.
Vinko Vrsalovic
Und es ist immer noch in der gleichen Grenze wie das, was das OP zur Verbesserung der Effizienz verlangte ...
Vinko Vrsalovic
11
uuoc, nutzlose Verwendung von cat
22

Verwenden Sie das folgende Beispiel, um mehrere Felder basierend auf einer Gruppe vorhandener Felder zusammenzufassen: (Ersetzen Sie die $ 1, $ 2, $ 3, $ 4 gemäß Ihren Anforderungen.)

cat file

US|A|1000|2000
US|B|1000|2000
US|C|1000|2000
UK|1|1000|2000
UK|1|1000|2000
UK|1|1000|2000

awk 'BEGIN { FS=OFS=SUBSEP="|"}{arr[$1,$2]+=$3+$4 }END {for (i in arr) print i,arr[i]}' file

US|A|3000
US|B|3000
US|C|3000
UK|1|9000
Anonym
quelle
2
+1, weil es zeigt, was zu tun ist, wenn nicht nur die Zählung benötigt wird
user829755
1
+1, weil sortund uniqam einfachsten zu zählen sind, aber nicht helfen, wenn Sie Feldwerte berechnen / summieren müssen. Die Array-Syntax von awk ist sehr leistungsfähig und der Schlüssel zur Gruppierung. Vielen Dank!
Odony
1
Beachten Sie außerdem, dass die printFunktion von awk 64-Bit-Ganzzahlen auf 32 Bit zu verkleinern scheint. Für int-Werte über 2 ^ 31 möchten Sie möglicherweise printfdas %.0fFormat anstelle von printdort verwenden
Odony
1
Menschen für "Gruppe von" mit String - Verkettung suchen statt Nummer Zusatz ersetzen würden arr[$1,$2]+=$3+$4mit zB arr[$1,$2]=(arr[$1,$2] $3 "," $4). I needed this to provide a grouped-by-package list of files (two columns only) and used: arr [$ 1] = (arr [$ 1] $ 2) `mit Erfolg.
Stéphane Gourichon
20

Die kanonische Lösung ist die von einem anderen Befragten erwähnte:

sort | uniq -c

Es ist kürzer und prägnanter als das, was in Perl oder awk geschrieben werden kann.

Sie schreiben, dass Sie sort nicht verwenden möchten, da die Daten größer sind als der Hauptspeicher des Computers. Unterschätzen Sie nicht die Implementierungsqualität des Unix-Sortierbefehls. Sort wurde verwendet, um sehr große Datenmengen (denken Sie an die ursprünglichen Rechnungsdaten von AT & T) auf Computern mit 128 KB (das sind 131.072 Byte) Speicher (PDP-11) zu verarbeiten. Wenn beim Sortieren mehr Daten als ein voreingestellter Grenzwert festgestellt werden (häufig nahe an der Größe des Hauptspeichers des Geräts abgestimmt), werden die im Hauptspeicher gelesenen Daten sortiert und in eine temporäre Datei geschrieben. Anschließend wird die Aktion mit den nächsten Datenblöcken wiederholt. Schließlich führt es eine Zusammenführungssortierung für diese Zwischendateien durch. Auf diese Weise kann die Sortierung Daten verarbeiten, die um ein Vielfaches größer sind als der Hauptspeicher des Geräts.

Diomidis Spinellis
quelle
Nun, es ist immer noch schlimmer als eine Hash-Zählung, nein? Wissen Sie, welchen Sortieralgorithmus die Sortierung verwendet, wenn die Daten in den Speicher passen? Variiert es im Fall der numerischen Daten (Option -n)?
Vinko Vrsalovic
Dies hängt davon ab, wie sort (1) implementiert ist. Sowohl die GNU-Sortierung (in Linux-Distributionen verwendet) als auch die BSD-Sortierung sind sehr umfangreich, um den am besten geeigneten Algorithmus zu verwenden.
Diomidis Spinellis
9
cat ip_addresses | sort | uniq -c | sort -nr | awk '{print $2 " " $1}'

Dieser Befehl würde Ihnen die gewünschte Ausgabe geben

zjor
quelle
4

Es scheint, dass Sie entweder eine große Menge Code verwenden müssen, um Hashes in Bash zu simulieren, um ein lineares Verhalten zu erhalten, oder sich an die quadratischen superlinearen Versionen halten müssen.

Unter diesen Versionen ist die Lösung von saua die beste (und einfachste):

sort -n ip_addresses.txt | uniq -c

Ich habe http://unix.derkeiler.com/Newsgroups/comp.unix.shell/2005-11/0118.html gefunden . Aber es ist höllisch hässlich ...

Vinko Vrsalovic
quelle
Genau. Dies ist die bisher beste Lösung und ähnliche Lösungen sind in Perl und Awk möglich. Kann jemand eine sauberere Implementierung in Bash bereitstellen?
Zizzencs
Nicht, dass ich davon Wüste. Sie können bessere Implementierungen in Sprachen erhalten, die Hashes unterstützen, wobei Sie dies für mein $ ip (@ips) {$ hash {$ ip} = $ hash {$ ip} + 1 tun. } und drucken Sie dann einfach die Schlüssel und Werte.
Vinko Vrsalovic
4

Lösung (gruppieren nach wie MySQL)

grep -ioh "facebook\|xing\|linkedin\|googleplus" access-log.txt | sort | uniq -c | sort -n

Ergebnis

3249  googleplus
4211 linkedin
5212 xing
7928 facebook
kairouan2020
quelle
3

Sie können wahrscheinlich das Dateisystem selbst als Hash-Tabelle verwenden. Pseudocode wie folgt:

for every entry in the ip address file; do
  let addr denote the ip address;

  if file "addr" does not exist; then
    create file "addr";
    write a number "0" in the file;
  else 
    read the number from "addr";
    increase the number by 1 and write it back;
  fi
done

Am Ende müssen Sie nur alle Dateien durchlaufen und die Dateinamen und -nummern darin drucken. Anstatt eine Zählung beizubehalten, können Sie alternativ jedes Mal ein Leerzeichen oder eine neue Zeile an die Datei anhängen und am Ende nur die Dateigröße in Byte anzeigen.

PolyThinker
quelle
3

Ich denke, ein awk assoziatives Array ist auch in diesem Fall praktisch

$ awk '{count[$1]++}END{for(j in count) print j,count[j]}' ips.txt

Eine Gruppe per Post hier

SriniV
quelle
Yepp, großartige awk-Lösung, aber awk war auf der Maschine, auf der ich das gemacht habe, einfach nicht verfügbar.
Zizzencs
1

Die meisten anderen Lösungen zählen Duplikate. Wenn Sie Schlüsselwertpaare wirklich gruppieren müssen, versuchen Sie Folgendes:

Hier sind meine Beispieldaten:

find . | xargs md5sum
fe4ab8e15432161f452e345ff30c68b0 a.txt
30c68b02161e15435ff52e34f4fe4ab8 b.txt
30c68b02161e15435ff52e34f4fe4ab8 c.txt
fe4ab8e15432161f452e345ff30c68b0 d.txt
fe4ab8e15432161f452e345ff30c68b0 e.txt

Dadurch werden die Schlüsselwertpaare gedruckt, die in der md5-Prüfsumme gruppiert sind.

cat table.txt | awk '{print $1}' | sort | uniq  | xargs -i grep {} table.txt
30c68b02161e15435ff52e34f4fe4ab8 b.txt
30c68b02161e15435ff52e34f4fe4ab8 c.txt
fe4ab8e15432161f452e345ff30c68b0 a.txt
fe4ab8e15432161f452e345ff30c68b0 d.txt
fe4ab8e15432161f452e345ff30c68b0 e.txt
Aron Curzon
quelle
1

Rein (keine Gabel!)

Es gibt einen Weg, a Funktion . Dieser Weg ist sehr schnell, da es keine Gabel gibt! ...

... während viele IP-Adressen klein bleiben !

countIp () { 
    local -a _ips=(); local _a
    while IFS=. read -a _a ;do
        ((_ips[_a<<24|${_a[1]}<<16|${_a[2]}<<8|${_a[3]}]++))
    done
    for _a in ${!_ips[@]} ;do
        printf "%.16s %4d\n" \
          $(($_a>>24)).$(($_a>>16&255)).$(($_a>>8&255)).$(($_a&255)) ${_ips[_a]}
    done
}

Hinweis: IP-Adressen werden in vorzeichenlose 32-Bit-Ganzzahlwerte konvertiert, die als Index für das Array verwendet werden . Dies verwendet einfache Bash-Arrays , keine assoziativen Arrays (was teurer ist)!

time countIp < ip_addresses 
10.0.10.1    3
10.0.10.2    1
10.0.10.3    1
real    0m0.001s
user    0m0.004s
sys     0m0.000s

time sort ip_addresses | uniq -c
      3 10.0.10.1
      1 10.0.10.2
      1 10.0.10.3
real    0m0.010s
user    0m0.000s
sys     0m0.000s

Auf meinem Host ist dies viel schneller als die Verwendung von Gabeln, bis zu ca. 1'000 Adressen, aber es dauert ungefähr 1 Sekunde, wenn ich versuche, 10'000 Adressen zu sortieren und zu zählen .

F. Hauri
quelle
0

Ich hätte es so gemacht:

perl -e 'while (<>) {chop; $h{$_}++;} for $k (keys %h) {print "$k $h{$k}\n";}' ip_addresses

aber uniq könnte für Sie arbeiten.

Nicerobot
quelle
Wie ich im ursprünglichen Beitrag sagte, ist Perl keine Option. Ich weiß, dass es in Perl einfach ist, kein Problem damit :-)
Zizzencs
0

Ich verstehe, dass Sie in Bash nach etwas suchen, aber falls jemand anderes in Python nach etwas sucht, sollten Sie Folgendes in Betracht ziehen:

mySet = set()
for line in open("ip_address_file.txt"):
     line = line.rstrip()
     mySet.add(line)

Da die Werte im Set standardmäßig eindeutig sind und Python in diesem Bereich ziemlich gut ist, können Sie hier möglicherweise etwas gewinnen. Ich habe den Code nicht getestet, daher ist er möglicherweise fehlerhaft, aber dies bringt Sie möglicherweise dorthin. Und wenn Sie Vorkommen zählen möchten, ist die Verwendung eines Diktats anstelle eines Satzes einfach zu implementieren.

Edit: Ich bin ein mieser Leser, also habe ich falsch geantwortet. Hier ist ein Ausschnitt mit einem Diktat, das Vorkommen zählt.

mydict = {}
for line in open("ip_address_file.txt"):
    line = line.rstrip()
    if line in mydict:
        mydict[line] += 1
    else:
        mydict[line] = 1

Das Wörterbuch mydict enthält jetzt eine Liste eindeutiger IP-Adressen als Schlüssel und die Häufigkeit, mit der sie als Werte aufgetreten sind.

wzzrd
quelle
das zählt nichts. Sie brauchen ein Diktat, das die Punktzahl hält.
Doh. Schlechtes Lesen der Frage, sorry. Ich hatte ursprünglich etwas damit zu tun, ein Diktat zu verwenden, um zu speichern, wie oft jede IP-Adresse vorkam, aber ich habe es entfernt, weil ich die Frage nicht sehr gut gelesen habe. * versucht richtig
aufzuwachen
2
Es gibt eine, itertools.groupby()die sorted()genau das tut, was OP verlangt.
JFS
Es ist eine großartige Lösung in Python, die dafür nicht verfügbar war :-)
Zizzencs
-8

Die Sortierung kann weggelassen werden, wenn die Reihenfolge nicht von Bedeutung ist

uniq -c <source_file>

oder

echo "$list" | uniq -c

wenn die Quellliste eine Variable ist

Plötzliche Def
quelle
1
Zur weiteren Verdeutlichung auf der Uniq-Manpage: Hinweis: 'Uniq' erkennt wiederholte Zeilen nur, wenn sie benachbart sind. Möglicherweise möchten Sie zuerst die Eingabe sortieren oder 'sort -u' ohne 'uniq' verwenden.
Konverter42