Início / unix / Perguntas / 748147
Accepted
Hölderlin
Asked: 2023-06-07 03:32:41 +0800 CST

desempenho sed usando espaço padrão e espaço de retenção

  • 772

Dado um arquivo de texto de tamanho 425M com o seguinte conteúdo:

--START--
Data=asdfasdf
Device=B
Lorem=Ipsum
--END--
--START--
Data=asdfasdf
Lorem=Ipsum
Device=A
--END--
--START--
Device=B
Data=asdfasdf
--END--
...

A sedtarefa é imprimir tudo entre --START--e --END--, onde Device=Aestá incluído. Existem duas soluções fornecidas aqui e aqui . Há uma enorme diferença de tempo de execução entre os dois comandos. O segundo comando é bem mais rápido, mas precisa de mais descrição para mim como funciona?

$ sed -n '/--START--/{:a;N;/--END--/!ba; /Device=A/p}' file

$ sed 'H;/--START--/h;/--END--/!d;x;/Device=A/!d' file

A descrição do primeiro comando:

Como funciona:

/--START--/{...}Toda vez que chegarmos a uma linha que contenha --START--, execute os comandos dentro das chaves {...}.

:a;Defina um rótulo "a".

N;Leia a próxima linha e adicione-a ao espaço do padrão.

/--END--/!baA menos que o espaço do padrão agora contenha --END--, volte para o rótulo a.

/Device=A/pSe chegarmos aqui, isso significa que o espaço dos padrões começa com --START--e termina com --END--. Se, além disso, o espaço do padrão contiver Device=A, imprima ( p).

Descrição do 2º comando:

sed 'H              #add line to hold space
     /--START--/h   #put START into hold space (substitute holded in)
     /--END--/!d    #clean pattern space (start next line) if not END
     x              #put hold space into pattern space
     /Device=A/!d   #clean pattern space if it have not "Device=A"
    ' file
sed

1 respostas

  1. Best Answer

    Uma coisa a ter em mente é que a correspondência de regex é "cara" ... portanto, quanto mais coisas você tiver no buffer de padrão, mais lenta será a pesquisa.
    Neste caso particular, sedtem que encontrar três padrões (vamos numerá-los como 1, 2 e 3): o intervalo START (1), o intervalo END (2) e um MATCH (3) (se houver) nesse intervalo.

    A principal diferença entre as duas soluções é o buffer usado para armazenar todas as linhas em um intervalo que, por sua vez, determina como o fim do intervalo é detectado.

    A 1ª solução funciona procurando por START (1) em cada linha e, uma vez que o encontra, começa a anexar linhas ao espaço do padrão e deve verificar o END (2) do intervalo a cada iteração (iow toda vez que adiciona um nova linha aos dados no espaço do padrão, ele procura em todo o buffer novamente por END para saber quando parar). Depois de encontrá-lo, ele procura em todo o espaço do padrão MATCH (3) .

    A 2ª solução funciona de maneira diferente: ela acumula linhas incondicionalmente no espaço de espera via H, faz correspondência de padrão em cada linha duas vezes: para determinar o INÍCIO (1) e, respectivamente, o FIM (2) do intervalo. Isso é muito rápido . Uma vez que detecta o END do intervalo, ele xaltera os buffers (então agora o espaço padrão contém todas as linhas que foram acumuladas no espaço de retenção) e procura em todo o espaço padrão MATCH (3) .

    Como você pode ver, (3) é idêntico em ambos os casos: ambos sedos scripts executam uma única busca por MATCH, uma vez que o espaço padrão contém todas as linhas de START até END . Portanto, não é a busca por MATCH que separa as duas soluções. A principal diferença aqui é causada por (2):
    A segunda solução procura por END em cada linha - se a linha não contiver END, ele a dexclui do espaço padrão e reinicia o ciclo, ou seja, puxa outra linha e, novamente , tenta encontrar o END e assim por diante. Até encontrar o END, nunca haverá mais de uma linha no espaço do padrão.
    A primeira solução, ao contrário, executaráa;N;/--END--/!ba repetidamente em um buffer de texto cada vez maior, embora a diferença em relação à execução anterior consista em uma única linha. Isso nunca é bom quando se trabalha com arquivos de texto grandes - imagine ter intervalos START-END abrangendo milhares de linhas...

    Resumindo: procurar o FIM do intervalo é o que o torna lento.

    Um bom exemplo de como a primeira técnica é lenta, em comparação com a segunda, pode ser encontrado aqui:

    Transforme a lista em uma única linha com delimitador

    Como você pode ver nos meus testes lá, a primeira solução não conseguiu nem terminar o teste.

    • 3

relate perguntas