como posso aumentar o desempenho abaixo do código

Question

Abaixo está o meu script que está tendo muito problema de desempenho

#!/usr/bin/ksh
while read i
do
  x='echo $i |cut -d"|" -f2'
  rem='expr $x % 62'
  echo "reminder is " $rem
  quo='expr $x / 62'
  echo "quotiont is " $quo

  grp_rem=" "
  if [[ ${#quo} -ge 2 ]]
  then
    while [ $quo -ge 62 ]
    do
      sub_rem='expr $quo % 62'
      quo='expr $quo / 62'
      grp_rem='echo $sub_rem" "$grp_rem'
    done
  fi
  echo $i"|"$quo" "$grp_rem" "$rem >> base62_while.out
done < base62_while.txt

Existe alguma maneira que eu possa aumentar o desempenho com o script acima?

entrada de amostra:

1|5147634738948389685

exemplo de saída

1|5147634738948389685|6 8 16 13 46 17 20 35 9 49 43

    

Answer 1

Isso deve ser consideravelmente mais rápido

#!/usr/bin/ksh
#
while IFS='|' read n x
do
    base62="$(echo "obase=62; $x" | bc | sed -re 's/ 0/ /g' -e 's/^ //')"
    printf "%d|%s|%s\n" $n "$x" "$base62"
done <base62_while.txt >>base62_while.out

A linha base62 usa bc para converter o número da fonte decimal em um equivalente base 62. Ele produz dois pares decimais de dígitos, dos quais retiramos qualquer zero inicial (ou seja, 02 é reescrito como 2 , mas 45 é deixado inalterado).

Entrada

1|5147634738948389685

Saída

1|5147634738948389685|6 8 16 13 46 17 20 35 9 49 43

    

Answer 2

Você não precisa chamar nenhuma ferramenta externa: o ksh pode fazer aritmética. Eu também estou usando uma matriz para armazenar os restos

#!/usr/bin/ksh
div=62
while IFS='|' read -r n x; do
    rem=$(( x % div ))
    quo=$(( x / div ))
    echo "reminder is  $rem" >&2
    echo "quotiont is  $quo" >&2

    remainders=( $rem )
    while (( quo >= div )); do
        sub_rem=$(( quo % 62 ))
        quo=$(( quo / 62 ))
        echo "reminder is  $sub_rem" >&2
        echo "quotiont is  $quo" >&2
        remainders=( $sub_rem "${remainders[@]}" )
    done
    echo "$n|$x|$quo ${remainders[*]}"

    x=$quo
    for r in "${remainders[@]}"; do
        x=$(( x * div + r ))
    done
    echo Verification: $x
done <<END
1|5147634738948389685
END

    

Answer 3

Existem várias coisas que podem ser feitas (e a velocidade é obtida):

• original em 1000 números
  35,023 seg
• substituir todos os comandos expr com expansões aritméticas $ ((x% 62))
  14,473
• converta grp_rem='echo $sub_rem" "$grp_rem' para grp_rem="$sub_rem $grp_rem"
  3,131
• evite o uso de corte ( set IFS='|'; set -f ; e use divisão de casca com set -- $1 )
  • ou use IFS='|' read a x <<<"$i" (embora <<< crie um arquivo temporário)
  • e como uma leitura já está sendo usada, substitua essa leitura.
    0,454
• reduza para apenas um loop (remova o if) e remova o espaço à direita no final | 0,207
• Torne o loop mais estreito Junte-se a ambos os $((...))
  0,113
  
  ---- shell: uma mudança de ~ 300 vezes mais rápido que 35.023 segundos.
  ++++ Este é provavelmente o melhor que pode ser feito com um script de shell.
• mudar para awk 0,123
  ---- awk: uma mudança total de ~ 280 vezes mais rápido

Script resultante:

#!/usr/bin/ksh
while IFS='|' read a b             # read both values split on '|'
do
    x=$b                           # set value of x (quotient)
    grp_rem=""                     # clear value of group
    while (( rem=x%62 , x/=62 ))   # do both math expressions.
    do
        grp_rem="$rem $grp_rem"    # concatenate resulting values
    done
    grp_rem=${grp_rem%?}           # remove one character (an space)
    echo "$a|$b|$rem $grp_rem" 
done  < base62_while.txt  >> base62_while.out

Um equivalente do script awk. Eu não sei se este é o script awk mais rápido possível, mas funciona bem. Mais rápido que o shell por mais de 10k linhas. Nota: Isto está usando o GNU awk com a opção -M (precisão arbitrária), que é uma obrigação para processar números na ordem de 19 dígitos que você apresentou. Pode processar números ainda maiores, não verifiquei por quanto tempo, mas tenho certeza de que o limite é bem alto. :-) Note que o awk deve ter sido compilado com essa opção incluída (verifique com awk 'BEGIN{ print( PROCINFO["gmp_version"], PROCINFO["prec_max"]) }' )

awk -MF'|' '{ x=$2; grp_rem="";
              while(x>0){
                          rem=x%62;
                          x=int(x/62);
                          grp_rem=rem" "grp_rem
                        }
              printf("%-22s|%s\n",$0,grp_rem)
            }
           ' <base62_while.txt >>base62_while.out

    

Answer 4

Depois de jogar um pouco com o módulo Math :: Base :: Convert , eu apareci com

perl -F'\|' -MMath::Base::Convert -lne '
  BEGIN{
    $bc = new Math::Base::Convert(dec,b62); 
    # create a mapping from internal symbol set to desired decimal representation
    $syms = $bc->b62; 
    @h{@$syms} = (0..61);
  } 
  print join "|", @F[0..1], (join " ", map $h{$_}, split //, $bc->cnv($F[1]))
' base62_while.txt

Pode haver alternativas de perl mais rápidas, conforme discutido aqui Conversão de base , embora eu Não tenho certeza se eles têm a mesma flexibilidade para manipular o mapeamento de saída.

    

Answer 5

com dc :

sed 's/.*|\(.*\)/[&|]Pp/;1s/^/62o/' base62_while.txt | dc > base62_while.out

Ou bc (observe que as implementações históricas de bc são na verdade wrappers em torno de dc ):

sed 's/.*|\(.*\)/"&|";/;1s/^/obase=62;/' base62_while.txt | bc > base62_while.out

Observe que dc e bc envolvem linhas longas de saída. Com as implementações GNU, você pode definir as variáveis de ambiente DC_LINE_LENGTH e BC_LINE_LENGTH como 0 para evitar isso.

$ echo '1|167883826163764944817996215305490271305728' | sed 's/.*|\(.*\)/[&|]Pp/;1s/^/62o/' | dc
1|167883826163764944817996215305490271305728| 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\
 00
$ echo '1|167883826163764944817996215305490271305728' | sed 's/.*|\(.*\)/[&|]Pp/;1s/^/62o/' | DC_LINE_LENGTH=0 dc
1|167883826163764944817996215305490271305728| 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

    

Answer 6

Você pode fazer algumas otimizações.

Alterar

grp_rem='echo $sub_rem" "$grp_rem'

para

grp_rem="$sub_rem $grp_rem"

Alterar

x='echo $i |cut -d"|" -f2'

para

x="${i#*|}"

Você provavelmente também deseja alterar

if [[ ${#quo} -ge 2 ]]

para

if [[ ${quo} -ge 62 ]]

Reduzir um pouco o número de sub-unidades ajudará. Se você quiser mais velocidade, use uma linguagem como C.

    

Answer 7

O shell é lento: use um idioma diferente. Se compararmos o script original do KSH (modificado para stdin e stdout usados), algo muito semelhante ao código Perl do steeldriver ( um script em vez de um one-liner que mostra velocidades similares à versão KSH nativa de glenn jackman), e uma implementação LISP com 10.000 linhas de entrada em um sistema de teste Centos 7:

base62.ksh  93.29s user 143.48s system 109% cpu 3:36.73 total
base62.perl  1.32s user 0.00s system 99% cpu 1.326 total
base62.sbcl  0.22s user 0.03s system 99% cpu 0.243 total

Obviamente, o código original rapidamente se torna impraticável à medida que as linhas de entrada aumentam, assim como as linguagens de script comparadas ao LISP com quantidades significativas de entrada. O tempo base62.sbcl é proveniente de uma implementação recursiva de chamada final:

#|
eval 'exec sbcl --script "$0" ${1+"$@"}'
|#
(defun divvy-r (n b l)
  (if (< n b) (cons (truncate n) l)
    (let ((rem (truncate (mod n b))) (quo (/ n b)))
      (divvy-r quo b (cons rem l)))))
(defun divvy (n b)
  (let ((rem (mod n b)) (quo (/ n b)))
    (if (< quo 2)
      (list (truncate quo) (truncate rem))
      (divvy-r n b nil))))
(loop for line = (read-line *standard-input* nil) while line do
      (let ((n (parse-integer (subseq line (1+ (position #\| line))))))
        (let ((out (divvy n 62)))
          (format t "~a|~{~a~^ ~}~&" line out))))

Lendo "Common Lisp: Uma introdução delicada à computação simbólica" e fazendo todos os exercícios nela é como eu aprendi isso. Um pouco mais rápido (e sempre tão sucinto) é uma implementação do* baseada no código KSH de Glenn Jackman:

#|
eval 'exec sbcl --script "$0" ${1+"$@"}'
|#
(defun remainders (n base)
  (do* ((rem (mod n base) (mod quo base))
        (quo (/ n base) (/ quo base))
        (out (cons (truncate rem) nil) (cons (truncate rem) out)))
    ((< quo base) (cons (truncate quo) out))))
(loop for line = (read-line *standard-input* nil) while line do
      (let ((n (parse-integer (subseq line (1+ (position #\| line))))))
        (format t "~a|~{~a~^ ~}~&" line (remainders n 62))))