Циклы,
как их писать эффективно
На базе примера 1
и примера 2 автор предлагает шаги
на пути оптимизации циклов
Прорешетим числа,
или не будем?
Известен алгоритм, решето Эристафена (по другим сведениям - Евклида), который позволяет вычислить таблицу, указывающую, какие числа в интервале от 1 до N являются простыми, а какие - составными (обсуждение алгоритма можно найти в этом учебнике). Существенным его недостатком является потребность в наличии своего элемента массива для каждого из чисел в интервале [1,N]. Такое расточительство оправдано лишь в том случае, когда требуется многократное и быстрое определение "простоты" различных чисел.
Рассмотрим алгоритм, требующий гораздо меньше памяти, причем "дойдем" до него в несколько шагов, путем последовательного улучшения (1).
Первый алгоритм, приходящий в голову примерно таков. Каждое число из интервала проверить на "простоту" по определению: оно должно делиться только на 1 и себя; подсчитаем сколько раз оно делится нацело и получим ответ:
Рассмотрим недостатки данного алгоритма и последовательно исправим их.
- если нас интересует деление целого числа на целое, а точнее - остаток от него, то и следует использовать операции целочисленного деления div и mod;
- на Pascal'е по некоторым причинам результат компиляции Inc(K); работает быстрее, чем K:= K+1; ;
- нет смысла делить i на все числа, большие, чем половина i - все равно нацело не разделится;
- кроме того, подсчет количества делений сам по себе не нужен: любое удачное деление нацело на число, не равное 1 и самому себе свидетельствует о том, что число не является простым. Следовательно, использование цикла For не является рациональным;
- кроме того, делить на 1 также нет смысла.
Переменная K введена для того, чтобы выражение, которому она равна (а оно не меняется на протяжении каждого прохода тела внешнего цикла) не вычислялось каждый раз.
Дальнейшее улучшение алгоритма вычисления множества простых чисел (с точки зрения автора) возможно лишь за счет дополнительных затрат памяти. С другой стороны, любое подобного рода вычисление должно иметь своей целью построение таблицы простых чисел, так что излишество затрат памяти весьма сомнительно. Суть заключается в следующем: нет необходимости производить деления на составные числа, так как каждое составное число есть произведение простых его составляющих.
Наметим канву алгоритма. Необходимо завести массив для простых чисел и занести в него одно простое число - 2. Затем остается каждое число из анализируемого интервала делить последовательно на все уже вычисленные простые числа, меньшие чем его половина. При обнаружении очередного простого числа его следует занести в массив. Реализацию данного алгоритма автор оставляет читателям для тренировки.
И, наконец, последнее ускорение алгоритма возможно при использовании для хранения таблицы простых чисел разреженного массива, в котором на месте простых чисел стоят, собственно, простые числа, а на всех остальных местах - 0. При этом размерность массива - N но от деления можно отказаться. В итоге мы придем к алгоритму трехтысячелетнего возраста - решету Эратосфена.
Сожмем массив
В качестве очередного примера эффективизации цикла приведем решение следующей задачи. Из массива необходимо удалить все элементы, удовлетворяющие некоторому условию. Конкретно - из числового массива исключить все тройки. массив при этом должен сжаться.
Опять же в методических целях приведем вариант, который первым приходит в голову и, к сожалению, часто реализуется.
End;
Принцип понятен и прост. (2) Однако, как и большинство вложенных циклов, вышеприведенный можно оптимизировать. Проведя мелкий анализ можно заметить, что при двух удаляемых элементах, элементы, следовавшие за вторым удаляемым, перемещаются два раза на одну позицию (после третьего удаляемого - три раза, etc.). От этого можно избавиться следующим образом.
K:= 0;
While I < N Do
End;
Как видим, мы смогли вообще избавиться от внутреннего цикла. И пришли к этому только попытавшись сэекономить на перемещениях...
Резюме
Как видно из приведенных элементарных примеров, практически любая задача, использующая вложенные циклы и не предполагающая поголовной обработки элементов массива (вроде вывода матрицы), может и должна быть оптимизирована. Пути, которыми следует идти в поисках оптимального решения следующие
- уменьшение диапазона изменения переменных циклов;
- замена циклов с фиксированным количеством повторений на прерывающиеся по условию;
- вынос вычисления постоянных относительно цикла выражений за его пределы;
- исключение внутренних циклов.
Использование этих несложных приемов может увеличить (и увеличивает) эффективность циклов на порядок, а то и на пару-тройку порядков (как в случае с простыми числами).
(1) Наверх Естественно, делается это лишь в методических целях - как из откровенно плохого алгоритма сделать вполне приличный; нет никакой необходимости начинать с заведомо плохого алгоритма, с другой стороны следует знать, что первый алгоритм, пришедший в голову скорее всего плох.
(2)Наверх Cтоит отметить, что в Borland Pascal приведенная программа работать не будет. Связано это с оптимизацией выполнения цикла в этом языке. Более подробно смотрите здесь.
