Melhor maneira de simular "agrupar por" no bash?

231

Suponha que você tenha um arquivo que contenha endereços IP, um endereço em cada linha:

10.0.10.1
10.0.10.1
10.0.10.3
10.0.10.2
10.0.10.1

Você precisa de um script de shell que conte para cada endereço IP quantas vezes ele aparece no arquivo. Para a entrada anterior, você precisa da seguinte saída:

10.0.10.1 3
10.0.10.2 1
10.0.10.3 1

Uma maneira de fazer isso é:

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

No entanto, está realmente longe de ser eficiente.

Como você resolveria esse problema com mais eficiência usando o bash?

(Uma coisa a acrescentar: eu sei que pode ser resolvido a partir de perl ou awk, estou interessado em uma solução melhor no bash, não nesses idiomas.)

INFORMAÇÃO ADICIONAL:

Suponha que o arquivo de origem tenha 5 GB e a máquina executando o algoritmo tenha 4 GB. Portanto, classificar não é uma solução eficiente, nem ler o arquivo mais de uma vez.

Gostei da solução semelhante à hashtable - alguém pode oferecer melhorias nessa solução?

INFORMAÇÕES ADICIONAIS # 2:

Algumas pessoas perguntaram por que eu me incomodaria em fazê-lo no bash, quando é muito mais fácil, por exemplo, em perl. O motivo é que na máquina que eu tinha que fazer esse perl não estava disponível para mim. Era uma máquina Linux customizada, sem a maioria das ferramentas que estou acostumada. E acho que foi um problema interessante.

Então, por favor, não culpe a pergunta, apenas a ignore se não gostar. :-)

Zizzencs
fonte
Eu acho que o bash é a ferramenta errada para o trabalho. Perl provavelmente será uma solução melhor.
Francois Wolmarans

Respostas:

412
sort ip_addresses | uniq -c

Isso imprimirá a contagem primeiro, mas fora isso, deve ser exatamente o que você deseja.

Joachim Sauer
fonte
71
que você pode canalizar para "classificar -nr" para classificar em ordem decrescente, da contagem mais alta para a mais baixa. iesort ip_addresses | uniq -c | sort -nr
Brad Parks
15
E sort ip_addresses | uniq -c | sort -nr | awk '{ print $2, $1 }'para obter o endereço IP na primeira coluna e contar na segunda.
Raghu Dodda 19/09/16
mais um ajuste para a parte de classificação:sort -nr -k1,1
Andrzej Martyna
50

O método rápido e sujo é o seguinte:

cat ip_addresses | sort -n | uniq -c

Se você precisar usar os valores no bash, poderá atribuir o comando inteiro a uma variável do bash e percorrer os resultados.

PS

Se o comando de classificação for omitido, você não obterá os resultados corretos, pois o uniq apenas analisa sucessivas linhas idênticas.

Francois Wolmarans
fonte
É a eficiência-wise muito semelhante, você ainda tem comportamento quadrático
Vinko Vrsalovic
Significado quadrático O (n ^ 2) ?? Isso dependeria certamente do algoritmo de classificação, é improvável que você use uma classificação bogo como essa.
22468
Bem, no melhor dos casos, seria O (n log (n)), pior do que duas passagens (que é o que você obtém com uma implementação trivial baseada em hash). Eu deveria ter dito 'superlinear' em vez de quadrático.
Vinko Vrsalovic
E ainda está no mesmo limite que o que o OP pediu para melhorar a eficiência ...
Vinko Vrsalovic 19/12/2008
11
uuoc, uso inútil de gato
22

para resumir vários campos, com base em um grupo de campos existentes, use o exemplo abaixo: (substitua $ 1, $ 2, $ 3, $ 4 de acordo com seus requisitos)

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
Anônimo
fonte
2
+1 porque mostra o que fazer quando não é apenas necessária a contagem
user829755 26/09/14
1
+1 porque sorte uniqsão mais fáceis para fazer a contagem, mas não ajuda quando você precisa para calcular / valores campos de soma. A sintaxe da matriz do awk é muito poderosa e essencial para agrupar aqui. Obrigado!
odony
1
mais uma coisa, observe que a printfunção do awk parece reduzir o número inteiro de 64 bits para 32 bits; portanto, para valores int superiores a 2 ^ 31, convém usar printfcom o parâmetro%.0f formato em vez de print
odony
1
As pessoas que procuram "agrupar por" com concatenação de strings em vez de adição de números substituiriam arr[$1,$2]+=$3+$4por, por exemplo, 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) `com sucesso.
Stéphane Gourichon
20

A solução canônica é a mencionada por outro entrevistado:

sort | uniq -c

É mais curto e conciso do que o que pode ser escrito em Perl ou awk.

Você escreve que não deseja usar a classificação, porque o tamanho dos dados é maior que o tamanho da memória principal da máquina. Não subestime a qualidade de implementação do comando de classificação Unix. A classificação foi usada para lidar com grandes volumes de dados (pense nos dados de cobrança originais da AT&T) em máquinas com 128k (131.072 bytes) de memória (PDP-11). Quando a classificação encontra mais dados do que um limite predefinido (geralmente ajustado perto do tamanho da memória principal da máquina), ela classifica os dados lidos na memória principal e os grava em um arquivo temporário. Em seguida, repete a ação com os próximos blocos de dados. Por fim, ele executa uma classificação de mesclagem nesses arquivos intermediários. Isso permite que a classificação funcione em dados muitas vezes maiores que a memória principal da máquina.

Diomidis Spinellis
fonte
Bem, ainda é pior do que uma contagem de hash, não? Você sabe qual algoritmo de classificação a classificação usa se os dados couberem na memória? Isso varia no caso de dados numéricos (opção -n)?
Vinko Vrsalovic 21/12/08
Depende de como o tipo (1) é implementado. A classificação GNU (usada nas distribuições Linux) e a classificação BSD se esforçam para usar o algoritmo mais apropriado.
Diomidis Spinellis
9
cat ip_addresses | sort | uniq -c | sort -nr | awk '{print $2 " " $1}'

este comando daria a saída desejada

zjor
fonte
4

Parece que você precisa usar uma grande quantidade de código para simular hashes no bash para obter um comportamento linear ou seguir as versões superlineares quadráticas .

Entre essas versões, a solução da saua é a melhor (e mais simples):

sort -n ip_addresses.txt | uniq -c

Encontrei http://unix.derkeiler.com/Newsgroups/comp.unix.shell/2005-11/0118.html . Mas é feio como o inferno ...

Vinko Vrsalovic
fonte
Concordo. Esta é a melhor solução até agora e soluções semelhantes são possíveis em perl e awk. Alguém pode fornecer uma implementação mais limpa no bash?
Zizzencs
Não que eu saiba. Você pode obter melhores implementações em idiomas que suportam hashes, onde você faz para o meu $ ip (@ips) {$ hash {$ ip} = $ hash {$ ip} + 1; } e apenas imprima as chaves e os valores.
Vinko Vrsalovic
4

Solução (agrupe como mysql)

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

Resultado

3249  googleplus
4211 linkedin
5212 xing
7928 facebook
kairouan2020
fonte
3

Você provavelmente pode usar o próprio sistema de arquivos como uma tabela de hash. Pseudocódigo da seguinte forma:

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

No final, tudo o que você precisa fazer é percorrer todos os arquivos e imprimir os nomes e números dos mesmos. Como alternativa, em vez de manter uma contagem, você pode acrescentar um espaço ou uma nova linha de cada vez ao arquivo e, no final, apenas ver o tamanho do arquivo em bytes.

PolyThinker
fonte
3

Eu sinto matriz associativa awk também é útil neste caso

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

Um grupo por correio aqui

SriniV
fonte
Sim, ótima solução awk, mas o awk não estava disponível na máquina em que eu estava fazendo isso.
Zizzencs 23/12/08
1

A maioria das outras soluções conta duplicatas. Se você realmente precisar agrupar pares de valores-chave, tente o seguinte:

Aqui estão os meus dados de exemplo:

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

Isso imprimirá os pares de valores-chave agrupados pela soma de verificação 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
fonte
1

Puro (sem garfo!)

Existe uma maneira, usando um função . Desta forma, é muito rápido, pois não há garfo! ...

... Enquanto vários endereços IP permanecem pequenos !

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
}

Nota: Os endereços IP são convertidos em um valor inteiro não assinado de 32 bits, usado como índice para a matriz . Este usa matrizes simples do bash , não o array associativo (que é mais caro)!

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

No meu host, fazer isso é muito mais rápido do que usar garfos, até aproximadamente 1'000 endereços, mas leva aproximadamente 1 segundo inteiro quando vou tentar classificar e contar 10'000 endereços.

F. Hauri
fonte
0

Eu teria feito assim:

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

mas o uniq pode funcionar para você.

nicerobot
fonte
Como eu disse no post original, perl não é uma opção. Eu sei que é fácil em perl, nenhum problema com isso :-)
Zizzencs
0

Entendo que você está procurando algo no Bash, mas, caso outra pessoa esteja procurando algo no Python, considere o seguinte:

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

Como os valores no conjunto são únicos por padrão e o Python é muito bom nisso, você pode ganhar algo aqui. Como não testei o código, ele pode estar com erros, mas isso pode levá-lo até lá. E se você deseja contar ocorrências, é fácil implementar um ditado em vez de um conjunto.

Edit: Eu sou um péssimo leitor, então eu respondi errado. Aqui está um trecho com um ditado que contaria ocorrências.

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

O dicionário mydict agora contém uma lista de IPs exclusivos como chaves e a quantidade de vezes que ocorreram como seus valores.

wzzrd
fonte
isso não conta nada. você precisa de um ditado que mantenha a pontuação.
Doh. Má leitura da pergunta, desculpe. Originalmente, eu tinha um pouco de como usar um dict para armazenar a quantidade de vezes que cada endereço IP ocorreu, mas o removi, porque, bem, eu não li a pergunta muito bem. * tenta acordar corretamente
wzzrd 20/12/08
2
Há um itertools.groupby()que combinado com sorted()faz exatamente o que o OP pede.
JFS
É uma ótima solução em python, que não estava disponível para este :-)
Zizzencs
-8

A classificação pode ser omitida se o pedido não for significativo

uniq -c <source_file>

ou

echo "$list" | uniq -c

se a lista de fontes for uma variável

Sudden Def
fonte
1
Para esclarecer melhor, na página do manual uniq: Nota: 'uniq' não detecta linhas repetidas, a menos que elas sejam adjacentes. Você pode classificar a entrada primeiro ou usar 'sort -u' sem 'uniq'.
converter42