Это должно быть значительно быстрее
#!/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
Строка base62
использует bc
для преобразования десятичного исходного числа в эквивалент с основанием 62. Он выводит двухзначные десятичные пары, из которых мы удаляем все начальные нули (, т.е. 02
переписывается как 2
, но 45
остается без изменений ).
Вход
1|5147634738948389685
Выход
1|5147634738948389685|6 8 16 13 46 17 20 35 9 49 43
Вы можете выполнить некоторые оптимизации.
Изменить
grp_rem=`echo $sub_rem" "$grp_rem`
с по
grp_rem="$sub_rem $grp_rem"
Изменить
x=`echo $i |cut -d"|" -f2`
-
x="${i#*|}"
Возможно, вы тоже захотите изменить
if [[ ${#quo} -ge 2 ]]
-
if [[ ${quo} -ge 62 ]]
Немного уменьшите количество подоболочек. Если вам нужна большая скорость, используйте язык, например C.
Вам не нужно обращаться к каким-либо внешним инструментам. :ksh может выполнять арифметические операции. Я также использую массив для хранения остатков
#!/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
Поиграв немного с Perl-модулем Math ::Base ::Convert , я придумал
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
Могут существовать более быстрые альтернативы Perl, как описано здесь. Базовое преобразование , хотя я не уверен, обладают ли они такой же гибкостью для управления отображением вывода.
Есть несколько вещей, которые можно сделать (и увеличить скорость):
grp_rem=`echo $sub_rem" "$grp_rem`
вgrp_rem="$sub_rem $grp_rem"
set IFS='|'; set -f
; и используйте разделение оболочки сset -- $1
)IFS='|' read a x <<<"$i"
(, хотя <<<
создает временный файл)$((...))
Результирующий скрипт:
#!/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
Эквивалент скрипта awk. Я не знаю, является ли это более быстрым сценарием awk, но работает нормально. Быстрее оболочки более чем на 10к строк. Примечание.:Здесь используется GNU awk с опцией-M
(произвольной точности ), которая необходима для обработки чисел в порядке 19 цифр, которые вы представили. Он может обрабатывать и более длинные числа, я не проверял, как долго, но я почти уверен, что предел довольно высок. :-)Обратите внимание, что awk должен быть скомпилирован с включенной опцией (проверьте с помощью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
Сdc
:
sed 's/.*|\(.*\)/[&|]P\1p/;1s/^/62o/' base62_while.txt | dc > base62_while.out
Илиbc
(обратите внимание, что исторические реализации bc
на самом деле являются обертками вокругdc
):
sed 's/.*|\(.*\)/"&|";\1/;1s/^/obase=62;/' base62_while.txt | bc > base62_while.out
Обратите внимание, что dc
и bc
переносят длинные строки вывода. В реализациях GNU вы можете установить для переменных среды DC_LINE_LENGTH
и BC_LINE_LENGTH
значение 0, чтобы этого избежать.
$ echo '1|167883826163764944817996215305490271305728' | sed 's/.*|\(.*\)/[&|]P\1p/;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/.*|\(.*\)/[&|]P\1p/;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
Оболочка работает медленно :использовать другой язык. Если мы сравним исходный скрипт KSH (, модифицированный для использования stdin и stdout ), что-то очень похожее на Perl-код Steeldriver(скрипт вместо одного -лайнера, который показывает скорость, аналогичную скорости гленна джекмана. собственная версия KSH )и реализация LISP с 10 000 строк ввода в тестовой системе 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
Очевидно, что исходный код быстро становится непрактичным по мере увеличения количества входных строк, как и языки сценариев по сравнению с LISP со значительным объемом входных данных. Время base62.sbcl
взято из рекурсивной реализации хвостового вызова:
#|
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))))
Прочитав "Common Lisp :Нежное введение в символьные вычисления" и выполнив все приведенные в нем упражнения, я научился этому. Немного быстрее (и очень лаконично )является do*
реализация, основанная на коде KSH Гленна Джекмана :
#|
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))))