Para contar o número de correspondências em uma string mega rapidamente

Question

Eu tenho grandes dados de texto sem espaços e sem outras linhas em uma linha. Na realidade, os fluxos são 0,2 Gb / s, situação semelhante aqui , mas nesta tarefa, contando ocorrências que são mais desafiador computacionalmente do que apenas contar linhas vazias. O jogo é

585e0000fe5a1eda480000000d00030007000000cd010000

O subconjunto de dados de exemplo é aqui chamado 30.6.2015_data. txt e seus dados binários completos aqui chamados 0002.raw . A partida ocorre 1 vez em 30.6.2015_data.txt , mas 10 vezes nos dados completos 0002.raw em uma linha. Eu preparei os dados do txt por xxd -ps 0002.raw > /tmp/1 && fold -w2 /tmp/1 > /tmp/2 && gsed ':a;N;$!ba;s/\n//g' /tmp/2 > /tmp/3 . Quanto mais rápida a implementação, melhor. Para preparar a string mega na coluna, você pode usar este xxd -ps 0002.raw > /tmp/1 && fold -w2 /tmp/1 > /tmp/2 . Minha taxa atual é de 0,0012 s por correspondência, ou seja, 0,012 s por dez correspondências no arquivo de dados completo, que é lento.

O grep faz isso em linhas, portanto, não é possível na contagem. No Vim, %s/veryLongThing//gn é insuficiente para a tarefa. O comando wc está dando apenas caractere, byte e linhas, então não é uma ferramenta correta, mas provavelmente combinando-a com outra coisa. Possivelmente a combinação GNU Find e Sed, mas todas as implementações parecem ser muito complicadas.

Saídas da resposta de Mikeserv

$ cat 1.7.2015.sh 
time \
    ( export ggrep="$(printf '^ 6Z2H \r  \a 5')" \
             gtr='\a\rHZ^526'
             LC_ALL=C
      gtr -cs "$gtr" ' [\n*]' |
      gcut -sd\  -f1-6       |
      ggrep -xFc "$ggrep"
    ) <0002.raw

$ sh 1.7.2015.sh 
1

real    0m0.009s
user    0m0.006s
sys 0m0.007s

-----------

$ cat 1.7.2015.sh 
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  ggrep="$(shift;IFS=\;printf "\$*")"    \
                gtr='
585e0000fe5a1eda480000000d00030007000000cd010000
\a\rHXZ^526'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    gcat 0002.raw; done            |
        gtr -cd "$gtr" |gtr 'X
$ cat 1.7.2015.sh 
time \
    ( export ggrep="$(printf '^ 6Z2H \r  \a 5')" \
             gtr='\a\rHZ^526'
             LC_ALL=C
      gtr -cs "$gtr" ' [\n*]' |
      gcut -sd\  -f1-6       |
      ggrep -xFc "$ggrep"
    ) <0002.raw

$ sh 1.7.2015.sh 
1

real    0m0.009s
user    0m0.006s
sys 0m0.007s

-----------

$ cat 1.7.2015.sh 
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  ggrep="$(shift;IFS=\;printf "\$*")"    \
                gtr='%pre%\a\rHXZ^526'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    gcat 0002.raw; done            |
        gtr -cd "$gtr" |gtr 'X%pre%' '\n '      |
        gcut -c-23    |ggrep -xFc "$ggrep"
    ) 

$ sh 1.7.2015.sh 
9990

real    0m4.371s
user    0m1.548s
sys 0m2.167s
' '\n '      |
        gcut -c-23    |ggrep -xFc "$ggrep"
    ) 

$ sh 1.7.2015.sh 
9990

real    0m4.371s
user    0m1.548s
sys 0m2.167s

onde todas as ferramentas são GNU coreutils e elas têm todas as opções que você fornece no código. Eles podem, no entanto, diferir com os devtools do GNU. Mikeserv executa seu código 990 vezes e há 10 eventos, então o total de 9.990 eventos está correto.

Como você pode contar o número de partidas em uma megastring de forma eficiente?

    

Answer 1

A implementação GNU de grep (também encontrada na maioria dos BSDs modernos, embora as últimas versões sejam uma reescrita completa (principalmente compatível)) suporta uma opção -o para produzir todas as partes correspondentes.

LC_ALL=C grep -ao CDA | wc -l

contaria todas as ocorrências.

LC_ALL=C grep -abo CDA

para localizá-los com seu deslocamento de bytes.

LC_ALL=C certifica-se de que grep não tente fazer algumas análises dispendiosas do UTF-8 (embora aqui, com uma pesquisa fixa de string ASCII, grep seja capaz de otimizar a análise UTF-8 por si ). -a é outro GNUism para informar grep para considerar arquivos binários.

    

Answer 2

Então peguei sua string hexadecimal e a imprimi em bytes, mas troquei as NULs por < espaços > (principalmente porque não consigo entender como obter um NUL em um padrão grep ) :

time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  grep="$(shift;IFS=\;printf "\$*")"    \
                tr='
9990
1.06s user 0.94s system 65% cpu 3.054 total
\a\rHXZ^526'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw; done     |
        tr -cd "$tr" |tr 'X
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\;printf "\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '
9990
1.56s user 1.46s system 82% cpu 3.648 total
 ' ' 
time \
   (    set     x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\;printf "\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '
...

241133568:X^  6Z62H   \r 
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  grep="$(shift;IFS=\;printf "\$*")"    \
                tr='
9990
1.06s user 0.94s system 65% cpu 3.054 total
\a\rHXZ^526'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw; done     |
        tr -cd "$tr" |tr 'X
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\;printf "\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '
9990
1.56s user 1.46s system 82% cpu 3.648 total
 ' ' 
time \
   (    set     x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\;printf "\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '
...

241133568:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241157720:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241181872:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241206024:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241230176:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241254328:X^  6Z62H   \r %pre%3 \a   5%pre%1  $

1.59s user 1.41s system 85% cpu 3.496 total
 ' ' %pre%'     |
        grep -baFo "$grep" | sed -n l
   )
'   |
        grep -aFo "$grep"| wc -l
    )
' '\n ' |
        cut -c-23    |grep -xFc "$grep"
    )
3 \a   5%pre%1  $
241157720:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241181872:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241206024:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241230176:X^  6Z62H   \r %pre%3 \a   5%pre%1  $
241254328:X^  6Z62H   \r %pre%3 \a   5%pre%1  $

1.59s user 1.41s system 85% cpu 3.496 total
 ' ' %pre%'     |
        grep -baFo "$grep" | sed -n l
   )
'   |
        grep -aFo "$grep"| wc -l
    )
' '\n ' |
        cut -c-23    |grep -xFc "$grep"
    )

A variável tr é composta de caracteres octal escapes / ASCII para os valores de byte de sua string hexadecimal porque eu queria que tr to -d elete seu complemento. Eu então me certifiquei de que a linha mais longa grep poderia tentar corresponder seria -c-23 bytes com cut , e que a string sempre encabeçaria uma linha por tr anslating X chars para \n ewlines enquanto também trocar as NULs por < espaços & gt ;.

Estou cat ing o binário bruto no pipeline 999 vezes aqui. Como existem 10 correspondências no arquivo, os resultados são:

%pre%

Agora eu também testei ...

%pre%

Eu uso wc -l , mas nos meus testes não pareceu fazer nenhuma diferença na hora de usar -caFo e% wc . As contagens eram as mesmas, de qualquer maneira. Os resultados para isso:

%pre%

Agora, esses dois conjuntos de comandos não são equivalentes. Embora pareça ser um pouco mais rápido ao eliminar bytes indesejados com tr primeiro, uma coisa que significa é que, enquanto você pode obter a contagem, não é possível obter os deslocamentos, adicionando a -b à grep no segundo exemplo ...

%pre% %pre%

E o que você escolher, eu acho, vai depender do que você quiser. Por apenas uma contagem, provavelmente o tr -cd será melhor - completou de forma confiável meio segundo mais rápido que o outro a cada vez - mas não é tão versátil, e talvez, se o seu grep suportá-lo, grep -baFo poderia ser o que você precisa em vez disso.