Ненормальное программирование (cерия 1). Проверка на нечетность

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

Казалось бы, нет ничего проще, чем проверить остаток от деления на 2, но не тут-то было. Мы провели серию опытов, в которых сравнили 3 алгоритма проверки числа на нечетность:

  1. Собственно, проверка остатка от деления на 2.
  2. Побитовая конъюнкция исходного числа и единицы (в случае, если в результате получим единицу, то исходное число является нечетным).
  3. Побитовый сдвиг исходного числа на 1 бит вправо и на 1 бит влево (в случае, если число при этом изменится, то оно нечетное).

Помимо этого, для компиляторов Delphi и FPC проверялось использование стандартной функции Odd из модуля System.

Тестирование проводилось с использованием 4 компиляторов:

  • C++/CLI (Visual Studio 2010, .NET Framework 4.0)
  • C++ (Qt 4.7)
  • Delphi (Embarcadero Delphi 2010 Architect)
  • FPC (Free Pascal 2.4)

на следующей машине:

  • Intel Core 2 Duo E7500 с частотой 2,93 ГГц
  • 2 Гбайт оперативной памяти
  • под управлением ОС Microsoft Windows XP Service Pack 3

Тестирование производилось в 10 заходов при проверке по 1 млрд. значений в каждом. Все результаты даны в миллисекундах.

Таблица результатов C++/CLI
Таблица результатов C++ (Qt)
Таблица результатов Delphi 2010
Таблица результатов Free Pascal
Ну и те же самые результаты в графическом представлении:

График результатов C++/CLI
График результатов C++ (Qt)
График результатов Delphi 2010
График результатов Free Pascal
Даже при беглом анализе полученных данных становится понятно, что широко используемый алгоритм проверки остатка от деления на 2 является далеко не самым быстрым.

Практически для любого языка, напротив, такое решение будет либо одним из самых медленных, либо вообще самым медленным. Самым же быстрым оказывается выполнение побитовой конъюнкции с единицей. Хотя, например, для Delphi можно использовать любой способ, за исключением MOD, т.к. их быстродействие почти одинаково.

Победителем у нас сегодня оказывается Delphi 2010 с ее результатом в 2,5 секунды. Аутсайдером же становится C++/CLI с результатом работы алгоритма с использованием сдвигов более 31,5 секунд.

На сегодня это все. Старайтесь писать быстрый код… ;)

Похожие записи для топика «Ненормальное программирование (cерия 1). Проверка на нечетность»

Комментарии (7) свернуть  |  развернуть

  • avatar
  • belan
  • 25 ноября 2011, 17:11
+2
— очень познавательно, буду и дальше следить за вашими исследованиями :)
  • avatar
  • Chiliec
  • 25 ноября 2011, 21:56
+1
Действительно познавательно… MOD — это единственный способ проверки на нечетность который я знаю. А теперь оказывается, что он не только не единственный, но еще и самый худший…
+1
Спасибо, рад, что заметка понравилась. В Delphi есть еще один способ проверки на нечетность из разряда «экзотических» — путем работы с числом, как с набором битов и проверки младшего. Если интересно, то в следующих сообщениях могу описать работу с числами в виде набора битов.
0
Конечно интересно! =)
  • avatar
  • belan
  • 09 декабря 2011, 09:03
0
— случайно (а возможно и нет :) ) пришла в голову мысль, что для развития культуры программирования имеет смысл разрабатывать нетривиальные алгоритмы для самых тривиальных задач
— предлагаю делиться своими ненормальными решениями и обсуждать их, в ходе диалога можно для себя почерпнуть что-нибудь новенькое…
— вот моё решение проверки числа не нечетность:
program P_odd;
{$APPTYPE CONSOLE}
uses SysUtils;
const m_odd = ['1','3','5','7','9'];
var a: integer;
    s: string;

function my_odd(i: integer): boolean;
begin
  s:=IntToStr(i);
  result:= s[length(s)] in m_odd;
end;

begin
  write('Enter number: '); readln(a);
  if my_odd(a)
    then write(a,' - odd')
    else write(a,' - even');
  readln;
end.
— что скажете? :) ничего особо умного, но есть оригинальность: «result:= s[length(s)] in m_odd;»
  • avatar
  • belan
  • 09 декабря 2011, 09:05
0
— да, s не там объявил
  • avatar
  • belan
  • 09 декабря 2011, 09:28
0
— и тут же ещё вариант :) :
program P_odd_2;
{$APPTYPE CONSOLE}
uses SysUtils;
const m_odd = '13579';
var a: integer;

function my_odd(i: integer): boolean;
var s: string;
begin
  s:=IntToStr(i);
  result:= pos(s[length(s)],m_odd)<>0;
end;

begin
  write('Enter number: '); readln(a);
  if my_odd(a)
    then write(a,' - odd')
    else write(a,' - even');
  readln;
end.

Прокомментировать