Нахождение порядкового разряда символа (более быстро)

Пример кода Метода Монте-Карло, найденный в Экстремальном Примере: Монте-Карло (Граница) Метод для Пи, показывает много способов вычислить порядковый номер байта. Версия записанное использование чистого подхода оболочки является крайне медленной, в значительной степени из-за требуемых циклов.

Лучший способ оптимизировать производительность состоит в том, чтобы счесть внешнюю утилиту записанной на скомпилированном языке, который может выполнить ту же задачу более легко. Таким образом решение той проблемы производительности состояло в том, чтобы использовать perl или awk интерпретатор, чтобы сделать тяжелый подъем. Несмотря на то, что они не скомпилированные языки, и Perl и AWK скомпилировали подпрограммы (ord и index, соответственно) для нахождения индекса символа в строке.

Однако при использовании внешних утилит не возможно, можно все еще сократить сложность путем выполнения вне инструментов менее часто. Например, как только у Вас есть инициализированный массив, содержащий все символы от 1–255 (пропускающий нуль), можно сократить количество итераций путем удаления больше чем одного символа за один раз, пока символ не исчезает, затем возвращаясь одним пакетом символов и работая путь вперед снова, один символ за один раз.

Следующий код работает более двух раз настолько же быстро (в среднем) как чисто линейный поиск:

ord2()

{

    local CH="$1"

    local STRING=""

    local OCCOPY=$ORDSTRING

    local COUNT=0;

    # Delete ten characters at a time.  When this loop

    # completes, the decade containing the character

    # will be stored in LAST.

    CONT=1

    BASE=0

    LAST="$OCCOPY"

    while [ $CONT = 1 ] ; do

        LAST=`echo "$OCCOPY" | sed 's/^\(..........\)/\1/'`

        OCCOPY=`echo "$OCCOPY" | sed 's/^..........//'`

        CONT=`echo "$OCCOPY" | grep -c "$CH"`

        BASE=`expr $BASE + 10`

    done

    BASE=`expr $BASE - 10`

    # Search for the character in LAST.

    CONT=1;

    while [ $CONT = 1 ]; do

        # Copy the string so we know if we've stopped finding

        # nonmatching characters.

        OCTEMP="$LAST"

        # echo "CH WAS $CH"

        # echo "ORDSTRING: $ORDSTRING"

        # If it's a close bracket, quote it; we don't want to

        # break the regexp.

        if [ "x$CH" = "x]" ] ; then

                CH='\]'

        fi

        # Delete a character if possible.

        LAST=$(echo "$LAST" | sed "s/^[^$CH]//");

        # On error, we're done.

        if [ $? != 0 ] ; then CONT=0 ; fi

        # If the string didn't change, we're done.

        if [ "x$OCTEMP" = "x$LAST" ] ; then CONT=0 ; fi

        # Increment the counter so we know where we are.

        COUNT=$((COUNT + 1)) # or COUNT=$(expr $COUNT '+' 1)

        # echo "COUNT: $COUNT"

    done

    COUNT=$(($COUNT + 1 + $BASE)) # or COUNT=$(expr $COUNT '+' 1)

    # If we ran out of characters, it's a null (character 0).

    if [ "x$OCTEMP" = "x" ] ; then COUNT=0; fi

    # echo "ORD IS $COUNT";

    # Return the ord of the character in question....

    echo $COUNT

    # exit 0

}

Как Вы настраиваетесь, необходимо быть осведомлены о среднем времени случая. В случае линейного поиска, принимая все возможные символьные значения одинаково вероятны, среднее время является половиной числа элементов в списке или приблизительно 127 сравнениями. Ища в модулях 10, среднее число о 1/10 этого плюс половина из 10, или приблизительно 17,69 сравнений, с худшим случаем 34 сравнений. Оптимальное значение равняется 16 со средним числом 15,9375 сравнений и худшим случаем 30 сравнений.

Конечно, Вы могли записать код как двоичный поиск. Поскольку разделение строки не просто сделать быстро, двоичный поиск работает лучше всего со строками известной длины, в которой можно кэшировать серию строк, содержащих некоторое число периодов. При поиске строки произвольной длины этот метод, вероятно, был бы очень, намного медленнее, чем линейный поиск (если Вы не используете СПЕЦИФИЧНОЕ ДЛЯ BASH расширение подстроки, как описано в Усечении Строк).

При кэшировании строк периодов, используемых во время инициализации увеличений процесса разделения немного, но после этого, время выполнения самого поиска улучшается на приблизительно фактор 2 по сравнению с “пропуском 16” версий. Является ли тот компромисс надлежащим, зависит в основном от того, сколько раз необходимо выполнить эту работу. Если ответ будет один раз, то дополнительное время инициализации, вероятно, сотрет любое увеличение производительности из использования двоичного поиска. Если ответ несколько раз, двоичный поиск предпочтителен.

Перечисление 12-1 содержит версию двоичного поиска.

Перечисление 12-1  версия двоичного поиска Оболочки Bourne ord подпрограмма

# Initialize the split strings.

# This block of code should be

# added to the end of ord_init.

    SPLIT=128

    while [ $SPLIT -ge 1 ] ; do

        COUNT=$SPLIT

        STRING=""

        while [ $COUNT -gt 0 ] ; do

                STRING="$STRING""."

                COUNT=$((COUNT - 1))

        done

        eval "SPLIT_$SPLIT=\"$STRING\"";

        SPLIT=$((SPLIT / 2))

    done

# End of content to add to ord_init

split_str()

{

        STR="$1"

        NUM="$2"

        SPLIT="$(eval "echo \"\$SPLIT_$NUM\"")"

        LEFT="$(echo "$STR" | sed "s/^\\($SPLIT\\).*$/\\1/")"

        RIGHT="$(echo "$STR" | sed "s/^$SPLIT//")"

}

ord3()

{

    local CH="$1"

    OCCOPY="$ORDSTRING"

    FIRST=1;

    LAST=257

    ord3_sub "$CH" "$ORDSTRING" $FIRST $LAST

}

ord3_sub()

{

    local CH="$1"

    OCCOPY="$2"

    FIRST=$3

    LAST=$4

    # echo "FIRST: $FIRST, LAST: $LAST"

    if [ $FIRST -ne $(($LAST - 1)) ] ; then

        SPLITWIDTH=$((($LAST - $FIRST) / 2))

        split_str "$OCCOPY" $SPLITWIDTH

        if [ $(echo "$LEFT" | grep -c "$CH") -eq 1 ] ; then

                # echo "left"

                ord3_sub "$CH" "$LEFT" $FIRST $(( $FIRST + $SPLITWIDTH ))

        else

                # echo "right"

                ord3_sub "$CH" "$RIGHT" $(( $FIRST + $SPLITWIDTH )) $LAST

        fi

    else

        echo $(( $FIRST + 1 ))

    fi

}

Как ожидалось это выполняет значительно лучше, уменьшая время выполнения приблизительно на десять процентов в этом случае. Улучшенная производительность, однако, почти точно смещается дополнительными затратами инициализации, чтобы позволить Вам разделить список. Именно поэтому Вы никогда не должны предполагать, что теоретически оптимальный алгоритм выполнит лучше, чем теоретически менее оптимальный алгоритм. В сценариях оболочки влияние производительности постоянной разницы в стоимости может и часто легко перевешивать улучшения алгоритмической сложности.

Конечно, использование Perl или сценария AWK для нахождения порядкового разряда намного быстрее, чем любой из этих методов. Цель этого примера состоит в том, чтобы продемонстрировать методы для того, чтобы повысить эффективность подобных операций, не показать лучший способ найти порядковый разряд символа.

Сокращение Использования Встроенной оценки

eval встроенный очень мощный инструмент. Однако это добавляет значительные издержки при использовании его.

Если Вы выполняетесь eval встроенный неоднократно в цикле и не должны использовать результаты для промежуточных вычислений, это значительно быстрее, чтобы сохранить каждое выражение как ряд разделенных от точки с запятой команд, затем выполнить их всех в единственной передаче в конце.

Например, следующий код смещает записи в псевдомассиве одной строкой:

test1()

{

        X=1; XA=0

        while [ $X -lt 5 ] ; do

                Y=1;

                while [ $Y -lt 5 ] ; do

                        eval "FOO_$X""_$Y=FOO_$XA""_$Y"

                        Y=`expr $Y + 1`

                done

                X=`expr $X + 1`

                XA=`expr $XA + 1`

        done

}

Можно ускорить эту подпрограмму приблизительно на 20% путем конкатенации операторов присваивания в единственную строку и выполнение eval только один раз, когда показывают в следующем примере:

test3()

{

        X=1; XA=0

        LIST=""

        while [ $X -lt 5 ] ; do

                Y=1;

                while [ $Y -lt 5 ] ; do

                        LIST="$LIST$SEMI""FOO_$X""_$Y=\$FOO_$XA""_$Y"

                        SEMI=";"

                        Y=`expr $Y + 1`

                done

                X=`expr $X + 1`

                XA=`expr $XA + 1`

        done

        # echo $LIST

        eval $LIST

}

Когда можно предварительно кэшировать эти команды в переменную, улучшение еще более театрального представления прибывает. Если необходимо неоднократно выполнять довольно четко определенную серию операторов таким образом (но не хотят тратить впустую сотни строк пространства в коде), можно создать список команд один раз, затем использовать его неоднократно.

Путем кэширования списка команд второе и последующее выполнение улучшается на приблизительно фактор 200, который помещает его производительность в или около скорости вызова подпрограммы со всеми выписанными операторами присваивания.

Другой полезный метод должен предварительно кэшировать фиктивную версию команд с текстом заполнителя вместо определенных значений. Например, в вышеупомянутом коде Вы могли кэшировать серию операторов в форме ROW_X_COL_1=ROW_Y_COL_1;, повторение для каждого значения столбца. Затем когда необходимо было скопировать одну строку в другого, Вы могли сделать это:

eval `echo $ROWCOPY | sed "s/X/$DEST_ROW/g" | sed "s/Y/$SRC_ROW/g"`

Если у Вас нет отдельных переменных для источника и целевых строк, Вы могли бы записать что-то как следующее:

eval `echo $ROWCOPY | sed "s/X/$ROW/g" | sed "s/Y/$(expr $ROW + 1)/g"`

Путем записи кода таким образом, Вы заменили несколько строк кода итератора и десятки eval инструкции с синглом eval инструкция и два выполнения sed. Получающееся повышение производительности является существенным.

Фон или задерживает вывод

Вывод к файлам занимает время, вывод к консоли вдвойне так. Если Вы пишете код, где производительность является рассмотрением, необходимо или выполнить выходные команды в фоновом режиме путем добавления амперсанда (&) до конца команды или собирают в группу многократные выходные операторы.

Например, при привлечении игровой доски самый быстрый путь состоит в том, чтобы сохранить команды получения в единственной переменной и вывести данные сразу. Таким образом Вы избегаете пробивать пенальти массовой казни. Очень быстрый способ сделать это должно отключить буферизацию и установить новую строку для смещения вниз строки, не возвращаясь к левому краю (выполненный stty raw для установки обоих из этих параметров) затем сохраните первую строку в переменную, сопровождаемую новой строкой, сопровождаемой символами возврата для смещения оставленный запуску следующей строки, сопровождаемой следующей строкой, и т.д.

Задержите потенциально Ненужную работу

Если результаты ряда инструкций никогда не могут использоваться, не выполняйте те инструкции.

Например, рассмотрите код, использующий eval встроенный для получения значений из серии переменных в псевдомассиве. Предположим, что код сразу возвращается, если какая-либо из переменных имеет значение 2 или больше.

Если Вы не накапливаете многократные операторы присваивания в единственный вызов к eval (как описано в Сокращении Использования Встроенной оценки), необходимо вызвать eval на первом операторе отдельно, сделайте сравнение, работайте eval для следующего оператора, и т.д. Путем выполнения так, Вы сокращаете среднее количество вызовов к eval.

Выполните сравнения только один раз

Если у Вас есть подпрограмма, выполняющая дорогой тест два или больше раза, кэшируйте результаты того теста и выполните самое легкое сравнение, возможное с тех пор.

Кроме того, если у Вас есть два возможных пути выполнения через Ваш код, совместно использующие некоторый код вместе, это может быть быстрее для использования только сингла if оператор и копия мелкая сумма общего кода вместо того, чтобы неоднократно выполнить то же сравнение. В целом, однако, такие изменения только приведут к одноразрядному улучшению процента производительности, таким образом, это будет обычно не стоить уменьшения в пригодности для обслуживания к дублирующему коду таким образом.

Влияние производительности варьируется в зависимости от расхода теста. Тесты, выполняющие вычисления или вне выполнения, являются особенно дорогими и таким образом должны быть минимизированы как можно больше. Конечно, можно сократить дополнительное влияние путем выполнения вычисления один раз и выполнения легкого теста многократно.

Простой тестовый сценарий привел к результатам, показанным в Таблице 12-1.

Выберите Control Statements Carefully

В большинстве ситуаций надлежащий оператор управления очевиден. Для тестирования, чтобы видеть, содержит ли переменная одно из двух или трех значений Вы обычно выбираете if оператор с небольшим количеством elif операторы. Для большего числа значений Вы обычно выбираете a case оператор. Это не только приводит к большему количеству читаемого кода, но также и приводит к более быстрому коду.

Для небольших чисел случаев (5), как ожидалось, различие между серией if операторы, if оператор с серией elif операторы и a case оператор в основном потерян в шуме, мудром производительностью, даже после 1 000 итераций. Несмотря на то, что результаты, показанные в Таблице 12-2, находятся в ожидаемом порядке, это было только истиной приблизительно половина времени. Для меньшего числа случаев могут в основном быть проигнорированы различия.

С большим числом случаев результаты более очевидно напоминают то, что можно было бы ожидать. case версия является самой быстрой, сопровождается elif версия, сопровождаемая if версия, с eval версия, все еще входящая в последний раз. Эти результаты имели тенденцию быть более непротиворечивыми, хотя eval было часто быстрее, чем серия if операторы.

Несмотря на то, что различия в производительности (показанный в Таблице 12-2) являются относительно небольшими в достаточно сложном сценарии с большим количеством случаев, они могут иметь значительное значение. В частности case оператор имеет тенденцию ухудшаться более корректно, тогда как серия if операторы собой имеют тенденцию вызывать постоянно увеличивающуюся потерю производительности.

Выполните вычисления только один раз

Например, если у Вас есть включающая подпрограмма expr $ROW + 1 в двух или больше строках кода необходимо определить локальную переменную ROW_PLUS_1 и сохраните значение выражения в той переменной. Если Вы используете, кэширование результатов вычисления особенно важно expr для большего количества переносимой математики, но выполнения так последовательно приводит к маленькому повышению производительности даже когда с помощью математики оболочки.

Используйте Shell Builtins везде, где возможно

Используя echo отдельно обычно приблизительно в 30 раз быстрее, чем явное выполнение /bin/echo. Эта улучшенная производительность также применяется к другому builtins такой как umask или test.

Конечно, test особенно важно, потому что это удваивается как скобка ([) команда, которая важна для большинства, проверяет утверждения в оболочке. Если Вы явно пишете использование оператора управления /bin/[, производительность сценария ухудшается очень, К счастью, маловероятно, что любой когда-либо делал бы это случайно.

На связанной ноте, printf встроенный значительно быстрее, чем echo встроенный, если Ваша оболочка обеспечивает его (большинство делает). Таким образом, для максимальной производительности, необходимо использовать printf вместо echo.

Для максимальной производительности используйте математику Shell, не внешние инструменты

Несмотря на то, что значительно менее переносимый, код, использующий ZSH-и СПЕЦИФИЧНЫЙ ДЛЯ BASH $(( $VAR + 1)) математическая нотация выполняется до 125 раз быстрее, чем идентичный код, записанный с expr команда и до 225 раз быстрее, чем идентичный код, записанный с bc команда.

Использовать expr в предпочтении к bc для любой целочисленной математики, превышающей возможности математических возможностей оболочки. Математика с плавающей точкой, используемая bc имеет тенденцию быть значительно медленнее.

Объедините Многократные Выражения с sed

sed инструмент, как любой другой внешний инструмент, является дорогим для запуска. При обработке большого блока данных этот штраф потерян в шуме, но если Вы обрабатываете короткое количество данных, это может быть значительный процент времени выполнения сценария. Таким образом, если можно обработать многократные регулярные выражения в единственном экземпляре sed, это намного быстрее, чем обработка каждого выражения отдельно.

Рассмотрите, например, следующий код, изменяющийся, “Это - тест” в “Это, записывается тост” и затем выбрасывает результаты путем перенаправления их к /dev/null.

function1()

{

    LOOP=0

    while [ $LOOP -lt 1000 ] ; do

        echo "This is a test." | sed 's/a/burnt/g' | sed 's/e/oa/g' > /dev/null

        LOOP=$((LOOP + 1))

    done

}

Можно ускорить это существенно путем перезаписи строки обработки для сходства с этим:

echo "This is a test." | sed -e 's/a/burnt/g' -e 's/e/oa/g' > /dev/null

Путем передачи многократных выражений sed, это обрабатывает их в единственном выполнении. В этом случае обработка второго выражения может быть сокращена больше чем на 60% на типичном компьютере.

Как объяснено в Предотвращении Ненужных Внешних Команд, можно улучшить производительность далее путем конкатенации этих строк в единственную строку и обработки вывода всех 1 000 строк в единственном вызове sed (с двумя выражениями). Это изменение сокращает общее время выполнения на почти фактор 20 по сравнению с исходной версией.

Для маленьких вводов штраф выполнения является относительно большим, настолько объединяющиеся результаты выражений в существенном улучшении. Для больших вводов штраф выполнения является относительно маленьким, настолько объединяющиеся выражения обычно приводит к незначительному улучшению. Однако даже с большими вводами, если sed операторы выполняются в цикле, кумулятивное различие в производительности могло быть примечательным.