Najlepszy sposób na symulację „grupowania według” z bash?

Załóżmy, że masz plik zawierający adresy IP, jeden adres w każdej linii:

10.0.10.1
10.0.10.1
10.0.10.3
10.0.10.2
10.0.10.1

Potrzebujesz skryptu powłoki, który liczy dla każdego adresu IP, ile razy pojawia się w pliku. Do poprzedniego wejścia potrzebne są następujące dane wyjściowe:

10.0.10.1 3
10.0.10.2 1
10.0.10.3 1

Jednym ze sposobów na to jest:

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

Jednak naprawdę nie jest to wydajne.

Jak rozwiązalibyście ten problem bardziej efektywnie za pomocą bash?

(Jedną rzecz do dodania: wiem, że można to rozwiązać z Perla lub awk, interesuje mnie lepsze rozwiązanie w bash, a nie w tych językach).

DODATKOWE INFORMACJE:

Załóżmy, że plik źródłowy ma 5 GB, a komputer z algorytmem ma 4 GB. Sortowanie nie jest więc skutecznym rozwiązaniem, ani odczytywanie pliku więcej niż jeden raz.

Podobało mi się rozwiązanie przypominające hashtable - ktoś może ulepszyć to rozwiązanie?

INFORMACJE DODATKOWE # 2:

Niektórzy ludzie pytali, dlaczego miałbym zawracać sobie tym głowę, kiedy jest to o wiele łatwiejsze, np. W Perlu. Powodem jest to, że na maszynie musiałem zrobić ten perl nie był dla mnie dostępny. Była to specjalnie zbudowana maszyna linuksowa bez większości narzędzi, do których jestem przyzwyczajony. Myślę, że to był interesujący problem.

Więc proszę, nie obwiniaj tego pytania, po prostu zignoruj ​​je, jeśli ci się nie podoba. :-)

sort ip_addresses | uniq -c

Spowoduje to wydrukowanie liczby jako pierwszej, ale poza tym powinna być dokładnie taka, jak chcesz.

Szybka i brudna metoda jest następująca:

cat ip_addresses | sort -n | uniq -c

Jeśli musisz użyć wartości w bash, możesz przypisać całe polecenie do zmiennej bash, a następnie przejrzeć wyniki.

PS

Jeśli polecenie sortowania zostanie pominięte, nie uzyskasz poprawnych wyników, ponieważ uniq patrzy tylko na kolejne identyczne linie.

do sumowania wielu pól na podstawie grupy istniejących pól skorzystaj z poniższego przykładu: (zamień 1 $, 2 $, 3 $, 4 $ zgodnie z własnymi wymaganiami)

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

Rozwiązaniem kanonicznym jest to, o którym wspomniał inny respondent:

sort | uniq -c

Jest krótszy i bardziej zwięzły niż to, co można napisać w Perlu lub awk.

Piszesz, że nie chcesz używać sortowania, ponieważ rozmiar danych jest większy niż rozmiar głównej pamięci urządzenia. Nie lekceważ jakości implementacji polecenia sortowania w Uniksie. Sort był używany do obsługi bardzo dużych ilości danych (na przykład danych rozliczeniowych oryginalnych AT&T) na komputerach z 128k (czyli 131.072 bajtów) pamięci (PDP-11). Kiedy sort napotyka więcej danych niż ustalony limit (często dostosowany do wielkości głównej pamięci urządzenia), sortuje dane, które odczytał w pamięci głównej i zapisuje je w pliku tymczasowym. Następnie powtarza akcję z kolejnymi porcjami danych. Wreszcie wykonuje sortowanie scalające na tych plikach pośrednich. Umożliwia to sortowanie pracy na danych wiele razy większych niż pamięć główna maszyny.

cat ip_addresses | sort | uniq -c | sort -nr | awk '{print $2 " " $1}'

to polecenie dałoby pożądany wynik

Wygląda na to, że musisz użyć dużej ilości kodu do symulacji skrótów w bashu, aby uzyskać zachowanie liniowe, lub trzymać się kwadratowych wersji superlinearnych.

Wśród tych wersji rozwiązanie saui jest najlepsze (i najprostsze):

sort -n ip_addresses.txt | uniq -c

Znalazłem http://unix.derkeiler.com/Newsgroups/comp.unix.shell/2005-11/0118.html . Ale to brzydkie jak diabli ...

Rozwiązanie (pogrupuj według mysql)

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

Wynik

3249  googleplus
4211 linkedin
5212 xing
7928 facebook

Prawdopodobnie możesz użyć samego systemu plików jako tabeli skrótów. Pseudo-kod w następujący sposób:

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

Na koniec wystarczy przejrzeć wszystkie pliki i wydrukować w nich nazwy i numery plików. Alternatywnie, zamiast utrzymywać liczbę, możesz za każdym razem dodawać spację lub znak nowej linii do pliku, a na koniec spójrz na rozmiar pliku w bajtach.

Uważam, że tablica asocjacyjna awk jest również przydatna w tym przypadku

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

Grupa pocztą tutaj

Większość innych rozwiązań liczy duplikaty. Jeśli naprawdę musisz pogrupować pary klucz-wartość, spróbuj tego:

Oto moje przykładowe dane:

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

Spowoduje to wydrukowanie par wartości klucza pogrupowanych według sumy kontrolnej md5.

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

Czysty grzmotnąć (bez widelca!)

Jest sposób, używając grzmotnąćfunkcja . Ta droga jest bardzo szybka, ponieważ nie ma widelca! ...

... Podczas gdy paczka adresów IP pozostaje niewielka !

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
}

Uwaga: Adresy IP są konwertowane na 32-bitową liczbę całkowitą bez znaku, używaną jako indeks tablicy . Używaj prostych tablic bash , a nie tablic asocjacyjnych (co jest droższe)!

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

Na moim hoście jest to o wiele szybsze niż używanie forksów, do około 1 000 adresów, ale zajmie około 1 całej sekundy, kiedy spróbuję posortować i policzyć 10 000 adresów.

Zrobiłbym to w ten sposób:

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

ale uniq może dla ciebie pracować.

Rozumiem, że szukasz czegoś w Bash, ale na wypadek, gdyby ktoś inny szukał czegoś w Pythonie, możesz rozważyć:

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

Ponieważ wartości w zestawie są domyślnie unikalne, a Python jest w tym całkiem niezły, możesz tutaj coś wygrać. Nie testowałem kodu, więc może być uszkodzony, ale może Cię tam doprowadzić. A jeśli chcesz policzyć zdarzenia, użycie dykta zamiast zestawu jest łatwe do wdrożenia.

Edycja: Jestem kiepskim czytelnikiem, więc odpowiedziałem źle. Oto fragment kodu ze słowem uwzględniającym zdarzenia.

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

Słownik mydict przechowuje teraz listę unikatowych adresów IP jako kluczy i liczbę ich wystąpień jako wartości.

Sortowanie można pominąć, jeśli kolejność nie jest znacząca

uniq -c <source_file>

lub

echo "$list" | uniq -c

jeśli lista źródeł jest zmienną