A tubulação, a mudança ou a expansão de parâmetros são mais eficientes?

26

Estou tentando encontrar a maneira mais eficiente de iterar através de certos valores que são um número consistente de valores um do outro em uma lista de palavras separadas por espaço (não quero usar uma matriz). Por exemplo,

list="1 ant bat 5 cat dingo 6 emu fish 9 gecko hare 15 i j"

Então, eu quero ser capaz de percorrer a lista e acessar apenas 1,5,6,9 e 15.

EDIT: Eu deveria ter deixado claro que os valores que estou tentando obter da lista não precisam ter um formato diferente do restante da lista. O que os torna especiais é apenas sua posição na lista (neste caso, posição 1,4,7 ...). Então a lista poderia ser,1 2 3 5 9 8 6 90 84 9 3 2 15 75 55mas eu ainda gostaria dos mesmos números. E também quero poder fazê-lo, assumindo que não sei o comprimento da lista.

Os métodos que eu pensei até agora são:

Método 1

set $list
found=false
find=9
count=1
while [ $count -lt $# ]; do
    if [ "${@:count:1}" -eq $find ]; then
    found=true
    break
    fi
    count=`expr $count + 3`
done

Método 2

set list
found=false
find=9
while [ $# ne 0 ]; do
    if [ $1 -eq $find ]; then
    found=true
    break
    fi
    shift 3
done

Método 3 Tenho certeza de que a tubulação faz dessa a pior opção, mas estava tentando encontrar um método que não usa set, por curiosidade.

found=false
find=9
count=1
num=`echo $list | cut -d ' ' -f$count`
while [ -n "$num" ]; do
    if [ $num -eq $find ]; then
    found=true
    break
    fi
    count=`expr $count + 3`
    num=`echo $list | cut -d ' ' -f$count`
done

Então, o que seria mais eficiente ou estou perdendo um método mais simples?

Levi Uzodike
fonte
10
Eu não usaria um script de shell em primeiro lugar se a eficiência fosse uma preocupação importante. Qual é o tamanho da sua lista que faz a diferença?
Barmar 01/02
2
Sem fazer estatísticas sobre instâncias reais do seu problema, você não saberá nada. Isso inclui a comparação com a "programação no awk" etc. Se as estatísticas são muito caras, então procurar eficiência provavelmente não vale a pena.
David Tonhofer 01/02
2
Levi, qual é exatamente o caminho "eficiente" em sua definição? Deseja encontrar uma maneira mais rápida de iterar?
Sergiy Kolodyazhnyy 02/02

Respostas:

18

Muito simples com awk. Isso fornecerá o valor de cada quarto campo para entrada de qualquer tamanho:

$ awk -F' ' '{for( i=1;i<=NF;i+=3) { printf( "%s%s", $i, OFS ) }; printf( "\n" ) }' <<< $list
1 5 6 9 15

Isso funciona alavancando awkvariáveis ​​internas como NF(o número de campos no registro) e executando alguns forciclos simples para percorrer os campos para fornecer as que você deseja sem precisar saber antecipadamente quantas haverá.

Ou, se você realmente deseja apenas esses campos específicos, conforme especificado no seu exemplo:

$ awk -F' ' '{ print $1, $4, $7, $10, $13 }' <<< $list
1 5 6 9 15

Quanto à questão sobre eficiência, o caminho mais simples seria testar esse ou cada um dos outros métodos e usar timepara mostrar quanto tempo leva; você também pode usar ferramentas como stracepara ver como o sistema chama o fluxo. Uso de timeaparência como:

$ time ./script.sh

real    0m0.025s
user    0m0.004s
sys     0m0.008s

Você pode comparar essa saída entre diferentes métodos para ver qual é a mais eficiente em termos de tempo; outras ferramentas podem ser usadas para outras métricas de eficiência.

DopeGhoti
fonte
1
Bom ponto, @MichaelHomer; Eu adicionei uma parte abordando a questão de "como posso determinar qual método é o mais eficiente ".
DopeGhoti 31/01
2
@LeviUzodike Em relação a echovs <<<, "idêntico" é uma palavra muito forte. Você poderia dizer que stuff <<< "$list"é quase idêntico a printf "%s\n" "$list" | stuff. Em relação a echovs printf, direciono-o para esta resposta
JoL
5
@DopeGhoti Na verdade, sim. <<<adiciona uma nova linha no final. É semelhante a como $()remove uma nova linha do final. Isso ocorre porque as linhas são finalizadas por novas linhas. <<<alimenta uma expressão como uma linha; portanto, ela deve ser finalizada por uma nova linha. "$()"usa linhas e as fornece como argumento, portanto, faz sentido converter, removendo a nova linha final.
JoL
3
O @LeviUzodike awk é uma ferramenta muito subestimada. Isso facilitará a solução de todos os tipos de problemas aparentemente complexos. Especialmente quando você está tentando escrever um regex complexo para algo como sed, geralmente você pode economizar horas escrevendo-o procedimentalmente no awk. Aprender pagará grandes dividendos.
Joe
1
@LeviUzodike: Sim, awké um binário independente que precisa ser iniciado. Diferentemente do perl ou especialmente do Python, o intérprete do awk é iniciado rapidamente (ainda com toda a sobrecarga usual do vinculador dinâmico de fazer algumas chamadas de sistema, mas o awk usa apenas libc / libm e libdl. Por exemplo, use stracepara verificar as chamadas de sistema da inicialização do awk) . Muitos shells (como o bash) são bem lentos; portanto, a inicialização de um processo awk pode ser mais rápida do que fazer o loop sobre tokens em uma lista com shell embutidos, mesmo para tamanhos de lista pequenos. E às vezes você pode escrever um #!/usr/bin/awkscript em vez de um #!/bin/shscript.
Peter Cordes
35
  • Primeira regra de otimização de software: não .

    Até você saber que a velocidade do programa é um problema, não há necessidade de pensar em quão rápido é. Se sua lista tiver esse tamanho ou apenas 100-1000 itens, você provavelmente nem perceberá quanto tempo leva. Há uma chance de você gastar mais tempo pensando na otimização do que qual seria a diferença.

  • Segunda regra: Medida .

    Essa é a maneira certa de descobrir e a que fornece respostas para o seu sistema. Especialmente com conchas, são tantas e nem todas são idênticas. A resposta para um shell pode não se aplicar ao seu.

    Em programas maiores, a criação de perfil também ocorre aqui. A parte mais lenta pode não ser a que você pensa que é.

  • Terceiro, a primeira regra de otimização de script do shell: não use o shell .

    Sim mesmo. Muitos shells não são feitos para serem rápidos (já que o lançamento de programas externos não precisa ser) e podem até analisar as linhas do código-fonte novamente todas as vezes.

    Use algo como awk ou Perl. Em um micro-benchmark trivial que fiz, awkfoi dezenas de vezes mais rápido que qualquer shell comum na execução de um loop simples (sem E / S).

    No entanto, se você usar o shell, use as funções internas do shell em vez de comandos externos. Aqui, você está usando o exprque não está embutido em nenhum shell que encontrei no meu sistema, mas que pode ser substituído por expansão aritmética padrão. Por exemplo, em i=$((i+1))vez de i=$(expr $i + 1)incrementar i. Seu uso cutno último exemplo também pode ser substituído por expansões de parâmetro padrão.

    Consulte também: Por que o uso de um loop de shell para processar o texto é considerado uma má prática?

As etapas 1 e 2 devem ser aplicadas à sua pergunta.

ilkkachu
fonte
12
# 0, cite suas expansões :-)
Kusalananda
8
Não é que os awkloops sejam necessariamente melhores ou piores que os loops de shell. É que o shell é realmente bom em executar comandos e direcionar entrada e saída de e para processos, e francamente bastante desajeitado em todo o resto; enquanto ferramentas como awksão fantásticas no processamento de dados de texto, porque é para isso que awksão feitas as conchas e as ferramentas (respectivamente).
DopeGhoti 31/01
2
@DopeGhoti, as conchas parecem ser objetivamente mais lentas, no entanto. Alguns loops de tempo muito simples parecem ser> 25 vezes mais lentos do dashque com gawk, e dashfoi o shell mais rápido que testei ...
ilkkachu 31/01
1
@ Joe, é :) dashe busyboxnão suporta (( .. ))- eu acho que é uma extensão fora do padrão. ++também é mencionado explicitamente como não obrigatório, pelo que sei i=$((i+1))ou : $(( i += 1))são os seguros.
ilkkachu
1
Re "mais tempo pensando" : isso negligencia um fator importante. Com que frequência é executado e para quantos usuários? Se um programa desperdiçar 1 segundo, o que pode ser corrigido pelo programador por 30 minutos, pode ser uma perda de tempo se houver apenas um usuário que o executará uma vez. Por outro lado, se houver um milhão de usuários, isso significa um milhão de segundos ou 11 dias de tempo do usuário. Se o código desperdiçou um minuto de um milhão de usuários, isso representa cerca de 2 anos de tempo do usuário.
agc 04/02
13

Vou apenas dar alguns conselhos gerais nesta resposta, e não referências. Os benchmarks são a única maneira de responder com segurança a perguntas sobre desempenho. Mas como você não diz quantos dados está manipulando e com que frequência executa essa operação, não há como fazer uma referência útil. O que é mais eficiente para 10 itens e o que é mais eficiente para 1000000 itens geralmente não é o mesmo.

Como regra geral, invocar comandos externos é mais caro do que fazer algo com construções de shell puras, desde que o código de shell puro não envolva um loop. Por outro lado, é provável que um loop de shell que itere sobre uma string grande ou uma grande quantidade de string seja mais lento que uma chamada de uma ferramenta para fins especiais. Por exemplo, sua chamada de loop cutpode muito bem ser prática na prática, mas se você encontrar uma maneira de fazer a coisa toda com uma única cutchamada, provavelmente será mais rápida do que fazer a mesma coisa com a manipulação de strings no shell.

Observe que o ponto de corte pode variar muito entre os sistemas. Pode depender do kernel, de como o agendador do kernel está configurado, do sistema de arquivos que contém os executáveis ​​externos, da quantidade de CPU versus pressão de memória existente no momento e de muitos outros fatores.

Não ligue exprpara executar aritmética se você estiver preocupado com o desempenho. Na verdade, não ligue exprpara executar aritmética. Os shells possuem aritmética embutida, mais clara e mais rápida do que a chamada expr.

Você parece estar usando o bash, já que está usando construções do bash que não existem no sh. Então, por que diabos você não usaria uma matriz? Uma matriz é a solução mais natural e provavelmente também a mais rápida. Observe que os índices da matriz começam em 0.

list=(1 2 3 5 9 8 6 90 84 9 3 2 15 75 55)
for ((count = 0; count += 3; count < ${#list[@]})); do
  echo "${list[$count]}"
done

Seu script pode muito bem ser mais rápido se você usar sh, se seu sistema tiver traço ou ksh em shvez de bash. Se você usa sh, não recebe matrizes nomeadas, mas ainda obtém a matriz com um dos parâmetros posicionais, com os quais você pode definir set. Para acessar um elemento em uma posição que não é conhecida até o tempo de execução, você precisa usar eval(lembre-se de citar as coisas corretamente!).

# List elements must not contain whitespace or ?*\[
list='1 2 3 5 9 8 6 90 84 9 3 2 15 75 55'
set $list
count=1
while [ $count -le $# ]; do
  eval "value=\${$count}"
  echo "$value"
  count=$((count+1))
done

Se você quiser acessar a matriz apenas uma vez e estiver indo da esquerda para a direita (pulando alguns valores), poderá usar em shiftvez de índices variáveis.

# List elements must not contain whitespace or ?*\[
list='1 2 3 5 9 8 6 90 84 9 3 2 15 75 55'
set $list
while [ $# -ge 1 ]; do
  echo "$1"
  shift && shift && shift
done

Qual abordagem é mais rápida depende do shell e do número de elementos.

Outra possibilidade é usar o processamento de strings. Tem a vantagem de não usar os parâmetros posicionais, para que você possa usá-los para outra coisa. Será mais lento para grandes quantidades de dados, mas é improvável que faça uma diferença notável para pequenas quantidades de dados.

# List elements must be separated by a single space (not arbitrary whitespace)
list='1 2 3 5 9 8 6 90 84 9 3 2 15 75 55'
while [ -n "$list" ]; do
  echo "${list% *}"
  case "$list" in *\ *\ *\ *) :;; *) break;; esac
  list="${list#* * * }"
done
Gilles 'SO- parar de ser mau'
fonte
" Por outro lado, um loop de shell que itera sobre uma string grande ou uma grande quantidade de string provavelmente será mais lento que uma chamada de uma ferramenta para fins especiais ", mas e se essa ferramenta tiver loops como awk? @ikkachu disse que os loops awk são mais rápidos, mas você diria que, com menos de 1000 campos para iterar, o benefício de loops mais rápidos não superaria o custo de chamar awk, pois é um comando externo (supondo que eu possa executar a mesma tarefa com shell loops com o uso de apenas comandos internos)?
Levi Uzodike 01/02
@LeviUzodike Por favor, releia o primeiro parágrafo da minha resposta.
Gilles 'SO- stop be evil'
Você também pode substituir shift && shift && shiftcom shift 3a sua terceira exemplo - a menos que o shell que você está usando não apoiá-lo.
Joe
2
@ Joe Na verdade, não. shift 3falharia se houvesse muito poucos argumentos restantes. Você precisaria de algo comoif [ $# -gt 3 ]; then shift 3; else set --; fi
Gilles 'SO- stop be evil'
3

awké uma ótima opção, se você puder fazer todo o processamento dentro do script Awk. Caso contrário, você acaba encaminhando a saída do Awk para outros utilitários, destruindo o ganho de desempenho de awk.

basha iteração sobre uma matriz também é excelente, se você pode ajustar sua lista inteira dentro da matriz (o que para shells modernos provavelmente é uma garantia) e não se importa com a ginástica de sintaxe da matriz.

No entanto, uma abordagem de pipeline:

xargs -n3 <<< "$list" | while read -ra a; do echo $a; done | grep 9

Onde:

  • xargs agrupa a lista separada por espaços em branco em lotes de três, cada nova linha separada
  • while read consome essa lista e gera a primeira coluna de cada grupo
  • grep filtra a primeira coluna (correspondente a cada terceira posição na lista original)

Melhora a compreensibilidade, na minha opinião. As pessoas já sabem o que essas ferramentas fazem, por isso é fácil ler da esquerda para a direita e raciocinar sobre o que vai acontecer. Essa abordagem também documenta claramente o comprimento da passada ( -n3) e o padrão do filtro ( 9), por isso é fácil variar:

count=3
find=9
xargs -n "$count" <<< "$list" | while read -ra a; do echo $a; done | grep "$find"

Quando fizermos perguntas de "eficiência", não deixe de pensar em "eficiência total da vida útil". Esse cálculo inclui o esforço dos mantenedores para manter o código funcionando, e nós, os sacos de carne, somos as máquinas menos eficientes em toda a operação.

bispo
fonte
2

Talvez isso?

cut -d' ' -f1,4,7,10,13 <<<$list
1 5 6 9 15
doneal24
fonte
Desculpe por não ter esclarecido antes, mas queria poder obter os números nessas posições sem saber o tamanho da lista. Mas obrigado, esqueci que o corte poderia fazer isso.
Levi Uzodike 31/01
1

Não use comandos shell se quiser ser eficiente. Limite-se a pipes, redirecionamentos, substituições etc. e programas. É por isso que xargse parallelutilitários existe - porque o bash while são ineficientes e muito lento. Use loops bash apenas como a última resolução.

list="1 ant bat 5 cat dingo 6 emu fish 9 gecko hare 15 i j"
if 
    <<<"$list" tr -d -s '[0-9 ]' | 
    tr -s ' ' | tr ' ' '\n' | 
    grep -q -x '9'
then
    found=true
else 
    found=false
fi
echo ${found} 

Mas você provavelmente deve ficar um pouco mais rápido com o bem awk.

KamilCuk
fonte
Desculpe por não ter esclarecido antes, mas estava procurando uma solução capaz de extrair os valores com base apenas na posição deles na lista. Acabei de fazer a lista original assim, porque queria que os valores fossem óbvios.
Levi Uzodike 31/01
1

Na minha opinião, a solução mais clara (e provavelmente também a mais eficiente) é usar as variáveis ​​aw e RS e ORS:

awk -v RS=' ' -v ORS=' ' 'NR % 3 == 1' <<< "$list"
user000001
fonte
1
  1. Usando o shell script GNU sed e POSIX :

    echo $(printf '%s\n' $list | sed -n '1~3p')
  2. Ou com basha substituição de parâmetro :

    echo $(sed -n '1~3p' <<< ${list// /$'\n'})
  3. Não GNU ( ou seja, POSIX ) sede bash:

    sed 's/\([^ ]* \)[^ ]* *[^ ]* */\1/g' <<< "$list"

    Ou, de maneira mais portável, usando o POSIX sed e o shell script:

    echo "$list" | sed 's/\([^ ]* \)[^ ]* *[^ ]* */\1/g'

Saída de qualquer um destes:

1 5 6 9 15
agc
fonte