6.4. Время выполнения различных элементарных операций

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

Итак, различные арифметические операции выполняются, конечно, за различное время. Но важно понимать, что эти времена очень сильно различаются.

Обязательное :) задание 6.8:

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

begin
вывести текущее время
for i:=1 to 1000000 do begin
    c:=a+b;
    c:=a+b;
    ...
    c:=a+b;
end;
вывести текущее время
end.

Несколько сложений внутри цикла сделано, чтобы основное время программа тратила именно на сложение, а не на «накладные расходы»: увеличение i и сравнение его с верхним пределом цикла. Верхний предел цикла, конечно, стоит подбирать, чтобы программа работала не слишком быстро (иначе таймер успеет слишком мало измениться), но и не слишком медленно (чтобы вам не надоело ждать :)), имхо оптимальное время работы порядка секунды. Обратите внимание на то, как я считаю время работы. Посмотрите, сколько времени занимает сложение/вычитание, умножение, деление (div и mod) целых чисел (на примере integer и/или longint), сколько занимают аналогичные операции с вещественными числами (можете сравнить все четыре вещественных типа: single, double, extended и real); посмотрите, сколько времени занимают shr, shl, побитовые and, or и т.д. При желании можете посмотреть, как влияет {$R+} на время работы с массивами и т.п. Только делайте все c отключённой оптимизацией ({$O-}), иначе она вам такого тут наоптимизирует…

А теперь приведу результаты своих исследований, которые я проводил очень давно и потому могу ошибаться (поэтому обязательно проверьте меня! :) ). Целочисленные операции: битовые операции (shr, and и т.п.) выполняются вроде примерно столько же времени, что и сложение и вычитание, но умножение выполняется на порядок (т.е. раз в 10) дольше, а деление (div и mod) — на два порядка (т.е. раз в сто медленнее!). С вещественными операциями картина примерно такая же: сложение/вычитание, потом умножение и наконец деление, только каждая операция, конечно же, тормознее, чем соответствующая операция с целыми числами (т.е. умножение вещественных чисел тормознее, чем умножение целых, что логично). Про времена работы разных вещественных типов я писал выше, здесь замечу ещё то, что, если я не ошибаюсь, вещественное умножение работает быстрее целочисленного деления (и уж тем более вещественного деления).

Мораль (одна из; конечно, есть и ещё морали из всего этого). Деление — очень тормозное действие, его стоит по возможности избегать. В частности, полезная идея: если вам несколько раз подряд надо делить на одно и тоже число \(x\), то намного быстрее будет посчитать заранее обратное ему — \(xx:=1/x;\) — и дальше умножать на \(xx\). Эта идею можно применить и к целым числам: вместо последовательного деления (div/mod) на одно и то же число \(k\) можно заранее посчитать обратное к этому числу \(kk:=1/k;\) (которое, конечно, будет вещественным) и дальше вместо n div k делать trunc(kk*n); аналогично можно и mod заменить на умножение. Т.к. даже вещественное умножение работает быстрее целочисленного деления, то это будет быстрее (но проверьте!). Ещё раз подчёркиваю, что это имеет смысл только когда вы много раз подряд делите на одно и то же число.

Пример: алгоритм Гаусса решения системы линейных уравнений: там много раз подряд приходится делить на одно и то же число. Если заранее посчитать обратное к нему, и потом умножать, то алгоритм резко ускорится. Ещё пример: в длинной арифметике приходится часть делить и вычислять остаток по модулю, равному основанию системы счисления. Аналогично, тут можно заранее посчитать обратное к основанию системы счисления (причём один раз на всю программу! — или даже забить в const), а потом использовать умножение и trunc (или работать в системе счисления с основанием — степенью двойки :) ). Аналогично в хешировании хеш с модулем, являющимся основанием двойки, работает намного быстрее.

И еще финальные замечания.

Первое: современные компиляторы очень и очень, просто невообразимо круты в оптимизации. Простой и чистый код компиляторы зачастую способны оптимизировать намного лучше, чем вы только можете себе представить. Нередко бывает так, что если вы придумываете какую-то очень хитрую оптимизацию, то она только замедляет программу, потому что компилятор не понял, что вы такое имели в виду, и не смог применить те оптимизации, которые в простой программе он прекрасно применял. Например, раньше имело смысл заменять деление на 2 на побитовый сдвиг. Для современных компиляторов такая оптимизация — одна из самых элементарных, поэтому пишите спокойно div 2 и всё, компилятор сам догадается заменить на shr.

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

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

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