Как вы определяете, четное число или нет? Есть много способов, но всегда хочется пользоваться самым эффективным. Мой преподаватель показал один интересный способ, который я решил испытать в данной статье.
Кроме того, хотелось бы проверить данный способ и эффективность алгоритмов, при использовании Perl и PHP.
Как вы определяете, четное число или нет? Есть много способов, но всегда хочется пользоваться самым эффективным. Мой преподаватель показал один интересный способ, который я решил испытать в данной статье.
Кроме того, хотелось бы проверить данный способ и эффективность алгоритмов, при использовании Perl и PHP.
Итак, задача: нужно максимально эффективно узнать четное число, содержащееся в переменной, или нет.
Самый, пожалуй, напрашивающийся вариант сделать это - поделить число на 2 и посмотреть остаток. Если он равен 0, значит, число четное, иначе - нечетное. Оформим это на php:
if ($a%2 != 0)
print 'Нечетное';
else
print 'Четное';
Вариант, о котором мне поведал мой преподаватель, не столь очевиден, но претендует на более высокую скорость выполнения. Дело в том, что процессор работает с двоичными кодами. Языки высокого уровня - лишь надстройка над ассемблером. Число, которое мы проверяем, будет переведено в двоичный код, при обработке. Четные двоичные числа оканчиваются на ноль. Нечетные - на единицу. Чувствуете, к чему веду?
Сколько операций ассемблера потребуется совершить компьютеру, чтобы вернуть остаток от деления числа на два - загадка. А чтобы совершить единственное И - потребуется 1 такт. Соответственно, вот решение:
if ($a & 1)
print 'Нечетное';
else
print 'Четное';
Если сомневаетесь - можете проверить, это действительно работает!
Стоит ли говорить, что на Perl это так же, будет работать.
if ($a%2 != 0)
{print 'Нечетное'}
else
{print 'Четное'}
if ($a & 1)
{print 'Нечетное'}
else
{print 'Четное'}
Чтобы измерить эффективность такого простого действия, нужно, для начала, повторить его несколько тысяч раз. Так и сделаем, но сначала, нужно определить функцию, которая будет засекать текущий момент времени, с максимальной точностью.
function getmicrotime()
{
list($usec, $sec) = explode(" ", microtime());
return ((float)$usec + (float)$sec);
}
Эта функция возвращает число, характеризующее текущее время. Теперь проводим замеры для варианта с & и для варианта с %.
$start = getmicrotime(true);
for($a=0; $a<=1000000; $a++)
{
if ($a & 1)
$a;
}
$end = getmicrotime(true);
$result1 =$end-$start;
print "Время выполнения с &: $result1";
print "<br/>";
$start = getmicrotime(true);
for($a=0; $a<=1000000; $a++)
{
if ($a%2 !=0)
$a;
}
$end = getmicrotime(true);
$result2 =$end-$start;
print "Время выполнения с %: $result2";
print "<br/>";
$res = $result1 - $result2;
print "Разница: $res";
Мы засекаем время в начале выполнения цикла, а затем - в конце. Для простоты, я не стал делать никаких посторонних действий с числами, прошедшими проверку, однако, сама проверка занимает время. Его-то мы и меряем. Мы прокручиваем два разных цикла, с разными условиями в теле, затем вычисляем разницу во времени.
Результат получается, в среднем, каким-то таким:
Время выполнения с &: 0.813378095627
Время выполнения с %: 0.970089912415
Разница: -0.156711816788
То есть, при использовании метода &, скорость выполнения получается выше, хоть и не на много. Люди, пользуйте этот метод.
Но мы совсем забыли про Perl! Давайте проведем аналогичный тест и на нем, и посмотрим результаты.
#!/usr/bin/perl
print "Content-type: text/html\n\n";
$start = times;
for($a=0; $a<=1000000; $a++)
{
if ($a & 1)
{$a}
}
$end = times;
$result1 =$end-$start;
print "Время выполнения с &: $result1";
print "<br/>";
$start = times;
for($a=0; $a<=1000000; $a++)
{
if ($a%2 != 0)
{$a}
}
$end = times;
$result2 =$end-$start;
print "Время выполнения с %: $result2";
print "<br/>";
$res = $result1 - $result2;
print "Разница: $res";
Результат, хоть и не столь точен, однако, демонстрирует некоторую прибавку к скорости. Солидную, надо сказать:
Время выполнения с &: 0.531
Время выполнения с %: 0.625
Разница: -0.094
Итак, мы убедились, что определять четность числа эффективнее всего с помощью конструкции $a & 1. Однако, применяя ее, убедитесь, что те, кто потом будет сопровождать ваш код, поймут, что вы имели ввиду;)
PS. Если вам понравилась эта статья, предлагаю вам полазить еще по этому сайту. Можете найти еще что-то полезное для себя. А если вы хотите быть всегда в курсе последних обновлений, то подпишитесь на RSS этого блога. Как, вы не знаете что такое RSS!?