Expressão Regular é lento?

2 de janeiro de 2014
 |  Nenhum comentário

Gosto bastante de Expressão Regular (E.R ou Regex) e não costumo ver seu uso empregado no dia a dia, acredito que isso se dá devido à dificuldade em compreender a formatação de sua estrutura, pois ninguém quer se arriscar muito, cometer um erro, fazer gambiarra em produção e etc…

Normalmente, ao questionar alguém por não ter adotado uma regex em determinada operação corriqueira, a resposta é sempre a mesma: “E.R é lento”. Isso vindo de uma pessoa com um pouco mais de experiência se torna praticamente um vírus dentro da equipe, em poucos instantes todos já estão defendendo a ideia e pode ter certeza, no próximo questionamento, a resposta será a mesma para outro membro, mas, como estão se embasando? Os dados não foram levantados ou qualquer teste foi feito para mostrar a realidade, o que podemos ganhar com E.R?

Por isso, neste documento irei expor o tempo de duração de um processo do início ao fim, submetendo alguns testes diferentes para um mesmo modelo e vendo como ele se comporta. O melhor tempo de cada execução será registrado.

Irei dividir os testes em três etapas T1,T2 e T3. Na primeira etapa, “T1”, irei passar apenas uma string para extrair uma informação simples e medir o tempo com o comando time do linux, esta será nossa única medida de teste. Na segunda etapa, “T2”, irei utilizar um arquivo com diversos registros e farei com que o sistema encontre o maior número de registros possíveis. Em “T3” irei rodar novamente o “T2”, mas farei com que o sistema gere o menor número de matching possível, assim poderemos comparar T2 e T3 e ver se realmente podemos ter alguma perda de desempenho neste ponto, uma vez que o primeiro teste é bem simples pode não apresentar um resultado tão assustador assim.

Após todos os resultados irei pegar a linguagem que apresentar o pior desempenho nos testes T2 e T3 e montar um script com o mesmo objetivo de T2 e T3.

Equipamento de teste

Sistema Operacional: Linux 3.2.0-4-amd64 #1 SMP Debian 3.2.54-2 x86_64 GNU/Linux

Processador: Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz 4 Núcleos

Memória : 6Gb Ram

14z Dell Inspirion

time

Para quem não conhece, o comando time do linux emite três tipos de informações:

real

Representa o tempo total gasto pela aplicação desde o momento que realiza sua primeira chamada de sistema até o processo ser finalizado como um todo.

user

Representa o tempo real de cpu gasto no processo, somente o tempo do processo em user space.

sys

Representa o tempo gasto pelo processo em kernel space.

Cada programa rodará cinco vezes, das cinco rodadas pegarei somente o melhor resultado.

::: T1 :::

Como dito anteriormente, o T1 é bem simples, criei uma string qualquer e dessa irei extrair uma parte do texto, para não complicar tentarei seguir o mesmo modelo em todos os programas.

String:“Meu nome é Wesley Leite moro na Rua: ABCDEFGHIJ KLMNOPQR 3311, CEP: 19283-983 e Gosto de pêra”

Todos os scripts devem extrair a palavra Rua: até o CEP numérico, todos os códigos estão no github e podem ser visualizados ao clicar na imagem abaixo da palavra source code.

Linguagem adotadas no teste:

  • 01 C
  • 02 Go
  • 03 Python
  • 04 Php
  • 05 Shell Script

01 C

source code:

$ time ./rua
Rua: ABCDEFGHIJ KLMNOPQR 3311, CEP: 19283-983 real    0m0.001s
user    0m0.000s
sys     0m0.000s

02 Go

source code:

$ time ./rua
“Rua: ABCDEFGHIJ KLMNOPQR 3311, CEP: 19283-983” real    0m0.002s
user    0m0.000s
sys     0m0.000s

03 Python

source code:

$ time ./rua.py

[u’Rua: ABCDEFGHIJ KLMNOPQR 3311, CEP: 19283-983′]

real    0m0.016s
user    0m0.012s
sys     0m0.000s

04 Php

source code:

$ time ./rua.php
Rua: ABCDEFGHIJ KLMNOPQR 3311, CEP: 19283-983 real    0m0.014s
user    0m0.008s
sys     0m0.004s

05 Shell Script

source code:

$ time ./rua.bash
Rua: ABCDEFGHIJ KLMNOPQR 3311, CEP: 19283-983 real    0m0.003s
user    0m0.000s
sys     0m0.000s


Temos nosso primeiro resultado, vamos à classificação geral:

  • 01 – C
  • 02 – Go
  • 03 – Shell Script
  • 04 – Php
  • 05 – Python

::: T2 :::

Para este teste vou utiliar um arquivo com 1286 linhas que escolhi aleatoriamente na internet, meu único critério foi selecionar um arquivo que tivesse registros de proteinas, vitaminas ou sequências de DNA. Se você já tiver finalizado o ensino médio, provavelmente conhece a sequência ‘CTAG’.

  • A = Adenina
  • G = Guanina
  • C = Cytosine
  • T = Timina

Este arquivo está cheio desses registros, basicamente, vamos extrair essas sequências, mas com alguns critérios, para este teste iremos extrair todas as sequências com, no minimo, 6 repetições desses caracteres.

Para o teste irei utilizar as seguintes linguagens, a única linguagem compilada será Go:

  • 01 Shell Script
  • 02 Php
  • 03 Python
  • 04 Go

01 Shell Script

source code:

$ time ./T2.bash
…
GAAtaaaatctTAT
GATTAATAAA real    0m0.154s
user    0m0.104s
sys     0m0.020s

02 Php

source code:

$ time ./T2.php
…
Array
(
   [0] => Array
   (
        [0] => GAAtaaaatctTAT
        [1] => GATTAATAAA
   )
)
real    0m0.389s
user    0m0.036s
sys     0m0.136s

03 Python

source code:

$ time ./T2.py
…
[‘GTTtaattgatAAA’, ‘TTTAAATAAAAA’]
[‘GAAtaaaatctTAT’, ‘GATTAATAAA’] real    0m0.134s
user    0m0.036s
sys     0m0.016s

04 Go

source code:

$ time ./T2
…
[“GTTtaattgatAAA” “TTTAAATAAAAA”]
[“GAAtaaaatctTAT” “GATTAATAAA”] real    0m0.137s
user    0m0.072s
sys     0m0.008s

Em nosso segundo resultado teremos:

  • 01 Python
  • 02 Go
  • 03 Shell Script
  • 04 Php

::: T3 :::

Finalmente, nosso ultimo teste, até agora todos os testes estão apresentando resultados bem satisfatórios: milésimos de segundos para percorrer um arquivo com 1286 registros e com expressão regular.

Nesta última etapa irei repetir o T2, mas com uma pequena modificação, vou reduzir o matching, ou seja, teremos menos registros encontrados em cada linha, o objetivo é ver se não encontrando o resultado esperado na linha a regex irá tornar o processo mais lento, vou pegar somente as sequências que se repetem vinte e três vezes, nem mais nem menos.

01 Python

$ time ./T3.py
…
[‘TTATTTTTAATTTAAATAAGATA’]
[]
…. real    0m0.068s
user    0m0.032s
sys     0m0.008s

02 Shell Script

source code:

$ time ./T3.bash
…
CTTCCCTAGAAATAAGCTGCAAA
TGACTAAAGGCTCAAAATCCTTC
TTATTTTTAATTTAAATAAGATA real     0m0.071s
user    0m0.068s
sys     0m0.000s

03 Go

source code:

$ time ./T3
…
[“TTATTTTTAATTTAAATAAGATA”]
[] real    0m0.088s
user    0m0.080s
sys     0m0.000s

04 Php

source code:

$ time ./T3.php
…
Array
(
   [0] => Array
   (
        [0] => TTATTTTTAATTTAAATAAGATA
   )
) real    0m0.225s
user    0m0.024s
sys     0m0.084s

Todos os resultados são inferiores ao resultado anterior, então,podemos concluir que diminuindo o número de matching a execução será mais rápida.

::: Teste de Conclusão :::

Neste teste irei pegar a linguagem Php por ter apresentando o pior resultado em T2 e T3, o script deve ler o arquivo T2.txt e seguir o mesmo critério de T2 e T3.

Php

source code:

$ time ./T2php.php
…
TTTAAATAAAAA
GAAtaaaatctTAT
GATTAATAAA real    0m0.131s
user    0m0.080s
sys     0m0.008s

source code:

$ time ./T3php.php
…
TTTAAATAAAAA
GAAtaaaatctTAT
GATTAATAAA real    0m0.020s
user    0m0.012s
sys     0m0.004s

::: Conclusão :::

Nenhuma das linguagens testadas apresentou resultado igual a um segundo (1s), sendo php a linguagem que se aproximou, ficando a exatamente seiscentos e onze mile segundos (611ms) de distância de um segundo, no entanto, a utilização de expressão regular se mostrou menos performático que a leitura do array palavra por palavra, este ultimo teste demonstrou exatamente isso, felizmente o arquivo escolhido tem um padrão de tabs que ajudou bastante, de qualquer forma não mudaria muito o resultado.

Expressão regular melhora muito a legibilidade do código, além de melhorar a produtividade do desenvolvedor tendo que pensar em menos linha de código para cumprir com determinada tarefa, isso já é argumento suficiente para incentivar seu uso.

Não sendo uma aplicações que alguns milésimo de segundo fará diferença, não vejo motivo de não usar.

Referências
http://docs.python.org/2/howto/regex.html
http://aurelio.net/regex/
http://thobias.org/doc/er_c.html
http://golang.org
http://en.wikipedia.org/wiki/Regular_expression