Digamos que eu tenha um arquivo de texto com 20 caracteres por linha como este:
wertzuiopasdfghjkl<
asdfghjkl<yxcvbnm,.-
<yxcvbnm,.-123456789
1234567890QWERTZUIOP
QWERTZUIOPASDFGHJKL<
e assim por diante ...
e eu quero que as linhas contenham pelo menos dois caracteres idênticos, eu posso usar grep como este
grep '\(.\).*' n20x1M
com uma referência anterior. Isso leva 15,7 s na minha máquina por um milhão de linhas sem correspondência.
Se eu dobrar o número de linhas, o tempo de CPU usado também será dobrado para 31,4, como esperado.
Eu também espero que o tempo para dobrar, se eu tiver 28 colunas em vez de 20 (20 caracteres dão 190 combinações possíveis para testar, 28 caracteres dão 378 combinações possíveis). Mas são apenas 28,2 s na minha máquina.
Portanto, a desaceleração do backreferencing não é apenas pelo número puro de combinações a serem testadas? Eu tentei este aqui:
grep '^\(.\).*' n20x1M
que derrete drasticamente o número de combinações de 190 para apenas 19: Basta ler o primeiro caractere e ver se ele corresponde a um dos caracteres restantes. Isso deve levar apenas 1,6 s, mas leva 2,8 s!
Talvez alguma sobrecarga para ler as linhas na memória e no cache? Não, se eu fizer
grep '.*_' n20x1M
é apenas 0,004 s de tempo de processamento! Ele está basicamente fazendo o mesmo (procurando por um caractere em uma linha de 20 caracteres), mas simplesmente não dando um caracter fixo, mas procurando pelo primeiro caractere da linha entre os 19 caracteres restantes, eu tenho uma lentidão de mais do que um fator 1000!
Existe algum erro no meu entendimento?
Há muita sobrecarga oculta introduzida pela referência anterior?
Ou o backreferencing no GNU regex foi mal implementado?
Quem pode explicar o que está acontecendo aqui?
O que posso fazer para melhorar o desempenho?
Atualizar A @Sundeep mencionou o aviso sobre as backreferences lentas. Mas esse é o efeito calculado causado por muitas soluções possíveis. Eu esperava isso, mas há uma penalidade adicional por usá-los, mesmo que eles não adicionem complexidade.
Realmente parece ser um problema de implementação, já que com sua outra dica para usar a opção -P , eu obtenho um aumento de velocidade de 15,4 para 2,0 s!
O caso trivial com a âncora ^ obtém um aumento de velocidade de 2,8 sa 0,25 s, mas ainda não atende à procura de um caracter fixo (0,004 s). Engraçado o suficiente, com a opção -P , o caso de caracteres fixos é reduzido para 0.13 s, portanto, há menos penalidade para a referência anterior, mas mais como uma penalidade total ...
Infelizmente, eu não tenho -P em grep do MacOS nem em qualquer sed versão em que eu uso principalmente referências anteriores.