[Desafio Bash 7] Você pode resolver este quebra-cabeça Bash Script?

23 de julho de 2017

Bem-vindo ao Bash Challenge nº 7 de Yes I Know IT e It's FOSS. Neste desafio semanal mostraremos uma tela de terminal, e contaremos com você para nos ajudar a obter o resultado que desejamos. Pode haver muitas soluções, e ser criativo é a parte mais divertida do desafio.

Se você ainda não fez isso, dê uma olhada nos desafios anteriores:

Você também pode comprar esses desafios (com desafios não publicados) na forma de livro e nos apoiar:

Pronto para jogar ? Então aqui está o desafio desta semana.

O contador de tokens

Esta semana, vamos voltar a um desafio mais orientado para a programação. A descrição sendo um pouco abstrata, tente ficar comigo por alguns minutos - e espero que a descrição abaixo seja clara o suficiente:

! [Bash Script Challenge](bash-challenge-7-description.webp) Bash Script Challenge

Eu tenho um fluxo de tokens 'RED' ou 'AZUL'. Se desejar, você pode considerar isso como uma representação de um fluxo de eventos, por exemplo. Não tenho nenhum controle específico sobre esse fluxo. Só sei que produz um ou outro token, de forma imprevisível. E eu sei que o vapor é finito (ou seja: em algum ponto, não haverá mais dados para ler).

Por causa deste desafio, usei uma função Bash para produzir esse fluxo. Você não tem permissão para mudar isso de forma alguma.

Comandos para usar no terminal

# You MUST NOT change that : stream() { TOKENS=( "RED" "BLUE" ) for((i=0;i<100;++i)) ; do echo ${TOKENS[RANDOM%2]} done }

Meu objetivo é contar ambos o número de fichas VERMELHAS e AZUIS que havia no fluxo. Por conta própria, consegui encontrar uma solução para contar apenas o número de tokens RED:

Comandos para usar no terminal

# You MUST change that stream | grep -F RED | wc -l > RED.CNT cat RED.CNT

Infelizmente, não consegui encontrar nenhuma solução para contar os tokens VERMELHOS e AZUIS. É por isso que preciso de sua ajuda. Qualquer ideia ?

Estamos ansiosos para ler suas soluções na seção de comentários abaixo!

Alguns detalhes

Para criar este desafio, usei:

  • GNU Bash, versão 4.4.5 (x86_64-pc-linux-gnu)

  • Debian 4.8.7-1 (amd64)

  • Todos os comandos são fornecidos com uma distribuição Debian padrão

  • Nenhum comando recebeu alias

A solução

Como reproduzir

Aqui está o código bruto que usamos para produzir este desafio. Se você executá-lo em um terminal, poderá reproduzir exatamente o mesmo resultado exibido na ilustração do desafio (assumindo que você esteja usando a mesma versão de software que eu):

Comandos para usar no terminal

rm -rf ItsFOSS mkdir -p ItsFOSS cd ItsFOSS clear stream() { TOKENS=( "RED" "BLUE" ) for((i=0;i<100;++i)) ; do echo ${TOKENS[RANDOM%2]} done } stream | grep -F RED | wc -l > RED.CNT cat RED.CNT

Qual era o problema?

A única dificuldade aqui foi minha tentativa inicial de descartar alguma parte da entrada, porque eu diretamente envio o fluxo de dados para o grep.

Basicamente, existem três abordagens para resolver esse problema:

  • Armazene os dados do stream e processe-os posteriormente;

  • Duplique o stream e processe dois caminhos independentes para tokens RED e BLUE;

  • Trate os dois casos no mesmo comando conforme eles chegam.

Depois de cada solução, eu forneço o uso em tempo real observado no meu sistema. Esta é apenas uma indicação e deve ser tomada com cautela. Portanto, sinta-se à vontade para fazer a sua própria comparação!

A loja e abordagem do processo

A implementação mais simples da abordagem de armazenamento e processo é óbvia:

Comandos para usar no terminal

stream > stream.cache grep -F RED < stream.cache | wc -l > RED.CNT grep -F BLUE < stream.cache | wc -l > BLUE.CNT rm stream.cache (1.3s for 10,000,000 tokens)

Funciona, mas tem várias desvantagens: você precisa armazenar os dados e eles são processados sequencialmente para cada token. Mais sutil, ao ler duas vezes o arquivo stream.cache, você pode ter alguma condição de corrida se um processo simultâneo atualizar esse arquivo durante o processamento.

Ainda na categoria de armazenamento e processo, aqui está uma solução completamente diferente:

Comandos para usar no terminal

stream | sort | uniq -c (5.9s for 10,000,000 tokens)

Considero que uma abordagem de armazenamento e processamento, uma vez que o comando sort tem que primeiro ler e armazenar (na RAM ou no disco) todos os dados antes de poder processá-los. Mais precisamente, no meu sistema Debian, o comando sort cria vários arquivos temporários em /tmp com permissões rw . Basicamente, essa solução tem as mesmas desvantagens da primeira, mas com desempenhos muito piores.

Duplicar stream

Nós realmente temos que/armazenar/os dados/antes/processá-los? Não. Uma ideia muito mais inteligente seria dividir o fluxo em duas partes, processando um tipo de token em cada sub-fluxo:

Comandos para usar no terminal

stream | tee >(grep -F RED | wc -l > RED.CNT)

(grep -F BLUE | wc -l > BLUE.CNT) /dev/null (0.8s for 10,000,000)

Aqui, não há arquivos intermediários. O comando tee replica os dados do fluxo conforme eles chegam. Cada unidade de processamento obtém sua própria cópia dos dados e pode processá-los em tempo real.

Esta é uma ideia inteligente porque não apenas manipulamos os dados conforme eles chegam, mas agora temos processamento paralelo .

Gerenciar dados conforme eles chegam

Em ciência da computação, provavelmente diríamos que a solução anterior adotou uma abordagem funcional para o problema. Por outro lado, as próximas serão soluções puramente imperativas. Aqui, leremos cada token e/se/este for um token VERMELHO,/então/iremos incrementar um contador VERMELHO,/senão se/este for um token AZUL, iremos incrementar um contador AZUL.

Esta é uma implementação simples do Bash dessa ideia:

Comandos para usar no terminal

declare -i RED=0 BLUE=0 stream | while read TOKEN; do case "$TOKEN" in RED) RED+=1 ;; BLUE) BLUE+=1 ;; esac done (103.2s for 10,000,000 tokens)

Finalmente, sendo um grande fã do comando AWK, não resistirei à tentação de usá-lo para resolver esse desafio de uma forma simples e elegante:

Comandos para usar no terminal

stream | awk ' /RED/ { RED++ } /BLUE/ { BLUE++ } END { printf "%5d %5d ",RED,BLUE } ' (2.6s for 10,000,000 tokens)

Meu programa AWK é feito de três regras:

  • Ao encontrar uma linha contendo a palavra RED, aumente (++) o contador RED

  • Ao encontrar uma linha contendo a palavra AZUL, aumente o contador AZUL

  • No FIM da entrada, exiba os dois contadores.

É claro que, para entender completamente, você precisa saber, para o propósito de operadores matemáticos, variáveis não inicializadas AWK são consideradas zero.

Isso funciona muito bem. Mas requer a duplicação da mesma regra para cada token. Não é um grande problema aqui, pois temos apenas dois tokens diferentes. Mais irritante se tivermos muitos deles. Para resolver isso, poderíamos contar com matrizes:

Comandos para usar no terminal

stream | awk ' { C[$0]++ } END { printf "%5d %5d ",C["RED"],C["BLUE"] } ' (2.0s for 10,000,000 tokens)

Precisamos apenas de duas regras aqui, qualquer que seja o número de tokens:

  • Qualquer que seja o token de leitura ($0), aumente a célula da matriz correspondente (aqui, C["RED"] ou C["BLUE"])

  • No END da entrada, exiba o conteúdo da matriz para as células "RED" e "BLUE".

Observe que "RED" e "BLUE" são agora cadeias de caracteres (você viu as aspas duplas em torno deles?) E isso não é um problema para AWK, pois ele oferece suporte a matrizes associativas. E, assim como as variáveis simples, as células não inicializadas em uma matriz associativa AWK são consideradas zero para os operadores matemáticos.

Como expliquei antes, optei por usar AWK aqui. Mas os fãs do Perl podem ter uma opinião diferente sobre o assunto. Se você é um deles, por que não postar sua própria solução na seção de comentários?

De qualquer forma, esperamos que você tenha gostado desse desafio. E fique ligado para mais diversão!

Confira também a versão original desse post em inglês
Esse post foi originalmente escrito por Sylvain Leroux e publicado no site itsfoss.com. Tradução sujeita a revisão.

[Bash Challenge 7] Can You Solve This Bash Script Puzzle?

Propaganda
Blog Comments powered by Disqus.
Propaganda