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

231

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. :-)

Zizzencs
źródło
Myślę, że bash jest nieodpowiednim narzędziem do tego zadania. Perl będzie prawdopodobnie lepszym rozwiązaniem.
Francois Wolmarans,
Spójrz na urządzenie do czyszczenia listy podsieci IPV4 (w notacji CIDR)
F. Hauri

Odpowiedzi:

412
sort ip_addresses | uniq -c

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

Joachim Sauer
źródło
71
które możesz następnie potokować do „sort -nr”, aby posortować w kolejności malejącej, od najwyższej do najniższej liczby. tj.sort ip_addresses | uniq -c | sort -nr
Brad Parks
15
I sort ip_addresses | uniq -c | sort -nr | awk '{ print $2, $1 }'aby uzyskać adres IP w pierwszej kolumnie i liczyć na sekundę.
Raghu Dodda,
jeszcze jedna poprawka do części sortowania:sort -nr -k1,1
Andrzej Martyna
50

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.

Francois Wolmarans
źródło
Jest to bardzo podobne pod względem wydajności, nadal zachowujesz się kwadratowo
Vinko Vrsalovic
Kwadratowe znaczenie O (n ^ 2) ?? Z pewnością zależy to od algorytmu sortowania, jest mało prawdopodobne, aby użyć takiego fałszywego sortowania.
paxdiablo,
Cóż, w najlepszym przypadku byłoby to O (n log (n)), co jest gorsze niż dwa przejścia (to jest to, co otrzymujesz dzięki trywialnej implementacji opartej na haszowaniu). Powinienem powiedzieć „superlinearny” zamiast kwadratowy.
Vinko Vrsalovic,
I nadal jest w tym samym zakresie, o co OP poprosił o poprawę wydajności ...
Vinko Vrsalovic,
11
uuoc, bezużyteczne korzystanie z cat
22

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
Anonimowy
źródło
2
+1, ponieważ pokazuje, co zrobić, gdy potrzebna jest nie tylko liczba
user829755
1
Daj +1, ponieważ sorti uniqsą najłatwiejsze do zliczania, ale nie pomagają, gdy musisz obliczyć / sumować wartości pól. Składnia tablicy awk jest bardzo potężna i kluczem do grupowania tutaj. Dzięki!
odony
1
jeszcze jedno, uważaj, że awk printfunkcja wydaje się w dół skali 64-bitowe liczby całkowite do 32 bitów, więc dla wartości int przekraczającej 2 ^ 31 może chcesz korzystać printfz %.0fformatu zamiast printtam
odony
1
Ludzie szukający „grupuj według” z konkatenacją ciągów zamiast dodawania liczb zamieniliby arr[$1,$2]+=$3+$4np. 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) `z powodzeniem.
Stéphane Gourichon
20

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.

Diomidis Spinellis
źródło
Cóż, to wciąż gorsze niż liczba mieszania, nie? Czy wiesz, jakiego algorytmu sortowania używa sort, jeśli dane mieszczą się w pamięci? Czy różni się w przypadku danych liczbowych (opcja -n)?
Vinko Vrsalovic
To zależy od sposobu sortowania (1). Zarówno sortowanie GNU (używane w dystrybucjach Linuksa), jak i sortowanie BSD idą na duże długości, aby użyć najbardziej odpowiedniego algorytmu.
Diomidis Spinellis,
9
cat ip_addresses | sort | uniq -c | sort -nr | awk '{print $2 " " $1}'

to polecenie dałoby pożądany wynik

zjor
źródło
4

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 ...

Vinko Vrsalovic
źródło
Zgadzam się. Jest to najlepsze rozwiązanie do tej pory i podobne rozwiązania są możliwe w perl i awk. Czy ktoś może zapewnić czystszą implementację w bash?
Zizzencs,
Nie żebym o tym wiedział. Możesz uzyskać lepsze implementacje w językach obsługujących skróty, gdzie robisz to dla mojego $ ip (@ips) {$ hash {$ ip} = $ hash {$ ip} + 1; }, a następnie po prostu wydrukuj klucze i wartości.
Vinko Vrsalovic,
4

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
kairouan2020
źródło
3

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.

PolyThinker
źródło
3

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

SriniV
źródło
Tak, świetne rozwiązanie awk, ale awk nie był dostępny na komputerze, na którym to robiłem.
Zizzencs,
1

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
Aron Curzon
źródło
1

Czysty (bez widelca!)

Jest sposób, używając 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.

F. Hauri
źródło
0

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ć.

nicerobot
źródło
Jak powiedziałem w oryginalnym poście, perl nie jest opcją. Wiem, że jest to łatwe w Perlu, nie ma z tym problemu :-)
Zizzencs
0

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.

wzzrd
źródło
to się nie liczy. potrzebujesz dykt, który zachowa wynik.
Doh Przepraszam, zła lektura pytania. Początkowo miałem trochę pojęcia o używaniu słownika do przechowywania liczby razy, kiedy wystąpił każdy adres IP, ale go usunąłem, ponieważ, cóż, nie przeczytałem zbyt dobrze pytania. * próbuje się obudzić poprawnie
wzzrd,
2
Istnieje coś, itertools.groupby()co w połączeniu z sorted()robi dokładnie to, o co prosi OP.
jfs
Jest to świetne rozwiązanie w pythonie, które nie było do tego dostępne :-)
Zizzencs
-8

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ą

Sudden Def
źródło
1
Aby to wyjaśnić, na stronie podręcznika użytkownika uniq: Uwaga: „uniq” nie wykrywa powtarzających się linii, chyba że sąsiadują ze sobą. Możesz najpierw posortować dane wejściowe lub użyć „sort -u” bez „uniq”.
converter42