Por que egrep [wW] [oO] [rR] [dD] é mais rápido que grep -i word?

49

Venho usando com grep -imais frequência e descobri que é mais lento que o egrepequivalente, onde eu ligo contra a letra maiúscula ou minúscula de cada letra:

$ time grep -iq "thats" testfile

real    0m0.041s
user    0m0.038s
sys     0m0.003s
$ time egrep -q "[tT][hH][aA][tT][sS]" testfile

real    0m0.010s
user    0m0.003s
sys     0m0.006s

Faz grep -itestes adicionais que egrepnão?

tildearrow
fonte
12
Experimente o grepcontrário, para garantir que você não esteja medindo a diferença entre o armazenamento em disco do disco.
EightBitTony 14/03
3
Eu tenho grep'd o arquivo antes do teste, por isso é armazenado em cache. Quase o mesmo tempo, se feito na ordem inversa.
tildearrow
21
Isso pode depender do código do idioma: alguns códigos de idioma envolvem cálculos complexos para explicar a distinção entre maiúsculas e minúsculas. O grep do GNU é particularmente lento em muitas situações envolvendo Unicode. Quais configurações de localidade você usou? Sob qual variante Unix? Qual é o conteúdo do seu arquivo de teste?
Gilles 'SO- stop being evil'
6
O @Gilles parece bom, repetindo cada teste aqui 100 vezes (cronometrando a coisa toda), egrepé mais rápido do que grepaté eu definir LANG=Ce, então, os dois são praticamente os mesmos.
EightBitTony
2
@EightBitTony Ver as userhoras (que não inclui o tempo de espera do disco). Há uma ordem de magnitude na diferença.
kasperd

Respostas:

70

grep -i 'a'é equivalente a grep '[Aa]'um código de idioma somente ASCII. Em um código de idioma Unicode, as equivalências e as conversões de caracteres podem ser complexas; portanto, é grepnecessário um trabalho extra para determinar quais caracteres são equivalentes. A configuração de localidade relevante é LC_CTYPE, que determina como os bytes são interpretados como caracteres.

Na minha experiência, o GNU greppode ser lento quando invocado em um código de idioma UTF-8. Se você souber que está procurando apenas caracteres ASCII, invocá-lo em um código de idioma somente ASCII pode ser mais rápido. Eu espero isso

time LC_ALL=C grep -iq "thats" testfile
time LC_ALL=C egrep -q "[tT][hH][aA][tT][sS]" testfile

produziria intervalos indistinguíveis.

Dito isto, não consigo reproduzir sua descoberta com o GNU grepno Debian jessie (mas você não especificou seu arquivo de teste). Se eu definir um código de idioma ASCII ( LC_ALL=C), grep -ié mais rápido. Os efeitos dependem da natureza exata da sequência, por exemplo, uma sequência com caracteres repetidos reduz o desempenho (o que é esperado ).

Gilles 'SO- parar de ser mau'
fonte
O autor usa o Ubuntu 14.04, fornecido com o grep 2.10. A velocidade das correspondências -isem distinção entre maiúsculas e minúsculas ( ) com localidades multibyte deve ter melhorado na 2.17 .
Lekensteyn
@Lekensteyn É bom saber, obrigado. O Ubuntu 14.04 realmente vem com o grep 2.16, mas também é pré-2.17; Testei com o grep 2.20, o que explica por que não vi a mesma desaceleração.
Gilles 'SO- stop be evil'
Certo, eu estava olhando para a versão LTS errada, o Ubuntu 12.04 é fornecido com o grep 2.10 enquanto o Ubuntu 14.04 inclui o grep 2.16.
Lekensteyn
11
Tenho certeza de que isso grep -i 'a'é equivalente a grep '[Aa]'qualquer local. O exemplo adequado é grep -i 'i'o que é ou grep '[Ii]'ou grep '[İi]'(Maiúsculas I com ponto acima, L + 130, localidade turco). No entanto, não há maneira eficiente grepde encontrar essa classe de equivalência, dada uma localidade.
MSalters
15

Por curiosidade, testei isso em um sistema Arch Linux:

$ uname -r
4.4.5-1-ARCH
$ df -h .
Filesystem      Size  Used Avail Use% Mounted on
tmpfs           3.9G  720K  3.9G   1% /tmp
$ dd if=/dev/urandom bs=1M count=1K | base64 > foo
$ df -h .                                         
Filesystem      Size  Used Avail Use% Mounted on
tmpfs           3.9G  1.4G  2.6G  35% /tmp
$ for i in {1..100}; do /usr/bin/time -f '%e' -ao grep.log grep -iq foobar foo; done
$ for i in {1..100}; do /usr/bin/time -f '%e' -ao egrep.log egrep -q '[fF][oO][oO][bB][aA][rR]' foo; done

$ grep --version
grep (GNU grep) 2.23
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Mike Haertel and others, see <http://git.sv.gnu.org/cgit/grep.git/tree/AUTHORS>.

E algumas estatísticas são cortesia de Existe uma maneira de obter o mínimo, o máximo, a mediana e a média de uma lista de números em um único comando? :

$ R -q -e "x <- read.csv('grep.log', header = F); summary(x); sd(x[ , 1])"
> x <- read.csv('grep.log', header = F); summary(x); sd(x[ , 1])
       V1       
 Min.   :1.330  
 1st Qu.:1.347  
 Median :1.360  
 Mean   :1.362  
 3rd Qu.:1.370  
 Max.   :1.440  
[1] 0.02322725
> 
> 
$ R -q -e "x <- read.csv('egrep.log', header = F); summary(x); sd(x[ , 1])"
> x <- read.csv('egrep.log', header = F); summary(x); sd(x[ , 1])
       V1       
 Min.   :1.330  
 1st Qu.:1.340  
 Median :1.360  
 Mean   :1.365  
 3rd Qu.:1.380  
 Max.   :1.430  
[1] 0.02320288
> 
> 

Estou no en_GB.utf8local, mas os horários são quase indistinguíveis.

muru
fonte