В предыдущем номере газеты была опубликована статья Андрея Колесникова "Как заставить счетчик бегать по кругу, не используя условных конструкций". Хотелось бы сделать по этому поводу несколько дополнений.
Во-первых, посмотрим на предложенную формулу получения циклической последовательности от 1 до n:
i=i+1-(i div n)*n
и рассмотрим старую конструкцию:
if(i=n) then i=1 else i=i+1
которая является аналогом предыдущей формулы.
Старая конструкция состоит из следующих операций:
- Сравнить i и n
- Если они-неравны, то перейти к операции 5
- Занести в i значение 1
- Перейти к операции 6
- Увеличить i на единицу
- ...
причем операции 1, 2 выполняются при любом значении i, 3,4 - при i=n, и операция 5 - при i=[1..n-1]
То есть для генерации последовательности от 1 до n понадобится 2*n+2+1*(n-1)=3*n+1 операция
В случае предложенной формулы мы имеем следующие операции:
- Получить результат от целочисленного деления i на n
- Полученный результат умножить на n
- Отнять от i полученный результат
- Увеличить i на единицу
Причем все операции выполняются для каждого шага цикла.
То есть для генерации последовательности от 1 до n понадобится 4*n операций. При этом, заметьте, не учитывалось то, что операции целочисленного деления и умножения занимают больше тактов процессора, чем остальные.
А ведь можно было слегка видоизменить формулу:
i=i+1-(i div n)*n=1+i-(i div n)*n=1+(i-(i div n)*n)=1+(i mod n)
То есть с помощью элементарных преобразований получаем формулу
i=(i mod n)+1
где mod - это операция получения остатка от целочисленного деления.
Таким образом, получаем следующую последовательность операций:
- Получить остаток от целочисленного деления i на n.
- К полученному результату прибавить единицу.
То есть, для генерации последовательности от 1 до n требуется 2*n операции.
Нельзя однозначно сказать, что эта формула будет работать быстрее конструкции с условным оператором, так как операция получения остатка от целочисленного деления сравнима с самой операцией челочисленного деления. Для этого надо сравнивать операции по тактам. Но она будет работать примерно вдвое быстрее предложенной формулы. И ее можно (и нужно) использовать тогда, когда необходимо получать обсуждаемые последовательности.
Перейдем к следующему замечанию. Дело в том, что високосный год - это не тот год, который делится на 4. Ведь 1900-й не был високосным годом. А 2000-й, например, будет. На самом деле формула получения високосного года такая:
если год делится на 400
то
| год - високосный
иначе
| если год делится на 100
| то
| | год - не високосный
| иначе
| | если год делится на 4
| | то
| | | год - високосный
| | иначе
| | | год - не високосный
Формулу, определяющую количество дней в феврале без условных операторов, я указывать не буду. Сделаем так - имя того, кто пришлет самую быструю формулу, определяющую количество дней в феврале в зависимости от года, мы напечатаем в следующем выпуске газеты... Если такой найдется. Шлите письма в редакцию с пометкой "Формула-Февраль".
Вадим НАРЕЙКО,
ghost@belcaf.minsk.by,
www.belcaf.com
Версия для печати
