Принципы выбора подсчитываемых операций

В большинстве случаев нет нужды точно подсчитывать количество выполненных операций как функцию от размера входных данных N. Разница между алгоритмом, который делает N + 5 операций, и тем, который делает N + 250 операций, становится незаметной, как только N становится очень большим.

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

Инициализация

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

Алгоритм подсчета числа вхождений различных символов в файл

Рассмотрим, например, алгоритм подсчета числа вхождений различных символов в файл:

• bash
• c

Он делает 256 проходов цикле инициализации. В цикле for сначала инициализируется переменная цикла, затем в каждом проходе проверяется, что переменная не выходит за границы выполнения цикла, и переменная получает приращение. Это означает, что цикл инициализации делает:

• 257 присваиваний (одно для переменной цикла и 256 для счетчика);
• 256 приращений переменной цикла;
• 257 проверок того, что эта переменная находится в пределах цикла (одна дополнительная для остановки цикла).

Если во входном файле N символов, то во втором цикле N проходов. Во втором цикле нужно сделать N + 1 раз проверку условия (+1 для последней проверки, когда файл пуст) и N приращений счетчика.

Всего операций:

• Приращения: N + 256
• Присваивания: 257
• Проверка условий: N + 258

Таким образом, при размере входного файла в 500 символов в алгоритме делается 1771 операция, из которых 770 приходится на инициализацию (43%). Теперь посмотрим, что происходит при увеличении величины N. Если файл содержит 50 000 символов, то алгоритм сделает 100 771 операцию, из которых только 770 связаны с инициализацией (что составляет менее 1% общего числа операций). Число операций инициализации не изменилось, но в процентном отношении при увеличении N их становится значительно меньше.

Теперь посмотрим с другой стороны. Данные в компьютере организованы таким образом, что копирование больших блоков данных происходит с той же скоростью, что и присваивание. Мы могли сначала присвоить 16 счетчикам начальное значение, равное 0, а затем скопировать этот блок 15 раз, чтобы заполнить остальные счетчики. Это приведёт к тому, что в циклах инициализации число проверок уменьшится до 33, присваиваний - до 33 и приращений - до 31. Количество операций инициализации уменьшается с 770 до 97, то есть на 87%. Если же мы сравним полученный выигрыш с числом операций по обработке файла в 50 000 символов, экономия составит менее 0,7% (вместо 100 771 операций мы затратим 100 098). Заметим, что экономия по времени могла бы быть даже больше, если бы мы сделали все эти инициализации без циклов, поскольку понадобилось бы только 31 простое присваивание, но этот дополнительный выигрыш дает лишь 0,97% экономии. Овчинка не стоит выделки.

Сокращенные вычисления булевых выражений

В некоторых языках программирования значения булевых выражений вычисляются сокращенным образом. Это означает, что член B в выражении A and B вычисляется, только если выражение A истинно, поскольку в противном случае результат оказывается ложным независимо от значения B. Аналогично член B в выражении A or B не будет вычисляться, если выражение A истинно. Неважно, считать ли число сравнений при проверке сложного условия равным 1 или 2.