Почему мой код такой медленный?

[Climber]

Нашел интересный сайтец: http://www.codechef.com
Там проходят соревнования по программированию. Есть куча задач и т. п.
Решил блеснуть интеллектом. Выбрал для разминки одну задачку наугад (http://www.codechef.com/problems/FCTRL/). Придумал алгоритм, написал. Программа тестируется автоматически. Получил результат: время выполнения - 0.23 секунды.
Там же есть таблица решений для каждой задачи. Для самых быстрых решений на С, С++ и Java указано время выполнения - 0.00 секунд, т. е. мгновенно почти. Посмотрел эти "чемпионские" решения. Там мой алгоритм один в один! Причем там еще выводится объем использованной памяти. У "чемпионов" - 0.00 МБ, у меня - 0.2 МБ.
Что-то я явно делаю не так, да?

Мой код:

Код: Выделить всё

program ZofN;

function Z(N: longint): longint;
var divider: longint = 5;
begin
  Z:=0;
  while divider <= N do
    begin
      Z:=Z+ (N div divider);
      divider:=divider * 5;
    end;
  end;

var count, i, num: longint;
begin
  ReadLn(count);
  for i:=0 to count - 1 do
    begin
      readln(num);
      WriteLn(Z(num));
    end;
end.

[Sergei I. Gorelkin]

У программы не может быть ни нулевого времени выполнения, ни нулевого расхода памяти. Если эти товарищи рисуют нули, значит, они либо не умеют измерять, либо у них политические мотивы.

[Climber]

Ну, с точки зрения математики, округление до 0.00 означает, что округляемое число меньше 0.005. Хотя с измерениями у них там проблемы наверняка есть. Я смотрел код на С, который выполнялся за 0,23 секунды - он почти не отличается от того, который был самым быстрым. Алгоритм тот же.

А вот расход памяти в 204 КБ меня смущает. Не многовато ли для консольного приложеня, 6 переменных и 1 функции? И вообще, в нем есть, что оптимизировать, хотя бы на пару тактов?

[Odyssey]

Я не специалист по оптимизации, просто стало интересно. Для наглядности стоит привести решение-чемпион на C:

Код: Выделить всё

#include<stdio.h>
int main(){
   int cases,i;
   long int num,count,tmp;
   scanf("%d",&cases);
   for(i=0;i<cases;i++){
      count=0;
      scanf("%ld",&num);
      tmp=num/5;
      count+=tmp;
      while(tmp >= 5){
         tmp=tmp/5;
         count+=tmp;
      }
      printf("%ld\n",count);
   }
   return 0;
}

Что теоретически может приводить к замедлению:
1. У чемпиона код заинлайнен, а у вас происходит вызов функции.
2. В итерации внутреннего цикла (while) чемпион делает только одно деление и инкремент, а вы - деление, умножение и инкремент.

[Climber]

Я тоже хитрый чукча!
1. Первым делом, когда я увидел этот код, я перенес функцию внутрь основной программы. Время не изменилось - 0.23.
2. Если дело в этих трех операциях, тогда время выполнения кода на С должно быть 0.12 минимум (при условии, что умножение примерно равно по сложности делению и намного сложнее сложения - на самом деле я вообще не знаток, как эти операции реализованы). Ну или у меня время должно быть 0.01 максимум.

А вообще, судя по количеству индусов на сайте (когда регистрируешься, сайт предлагает ввести свою страну, а по умолчанию там - Индия ) есть подозрение, что там все немного "индусское"...

[hinst]

значит так,
№1: ставим inline у всех функций.
№1.1: ставим register, дабы параметры передавались по регистрам... ну, это спорно. по-моему, там register сам включается для маленького числа параметров.
№2: везде где можно сделать const - параметр, ставим const, чтобы не было копирования. у вас там можно поставить
№3: for заменить на i:=count - 1; while i <> 0 do begin dec(i); ... end; ибо сравнение с нулём быстрее
№4: у них там какой компилятор и какой fpc, возможно, стоит {$mode fpc} указать, хорошо бы 2.4.х, а там 2.2.4 - ОМГОМГОМГ

Код: Выделить всё

     
Z:=Z+ (N div divider);
divider:=divider * 5;


это чё??

Код: Выделить всё

  inc(z, n div divider);
  divider *= 5; //в fpc так можно


З.Ы только что попробовал первую задачку из еasy, получил 0.00 гы

[Sergei I. Gorelkin]

А вот расход памяти в 204 КБ меня смущает. Не многовато ли для консольного приложеня, 6 переменных и 1 функции? И вообще, в нем есть, что оптимизировать, хотя бы на пару тактов?

Это расход не твоей программы, а RTL. Отхапал себе менеджер памяти начальный блок, вот тебе и 64-256 кБ. Или сама программа с необрезанной отладочной информацией примерно столько весит. Как измеряли - непонятно. Но судя по тесту фрактала Мандельброта на http://shootout.alioth.debian.org/ , с FPC 2.4 подобная программа занимает только 60кБ.

Что касается скорости - можно компилировать с ключом -O2, обычно скорость при этом повышается. Сам компилятор тоже улучшается со временем, почему они там тестируют совсем уж ископаемый 2.0.4, опять-таки непонятно.

Добавлено спустя 15 минут 28 секунд:
Напиши сразу вставку на ассемблере. По правилам конкурса оно, конечно, не пройдет, но есть шанс узнать, какую цифру нарисует для нее чудный индусодвижок...

[Maxizar]

Кстати, а как ВЫ делаете измерение времени выполнения кода. Мне вот как то нужно было измерить скорость выполнения до и после оптимизации… Нужно ли для этого выполнять процедуру в дополнительном потоке или можно в основном. И мне очень интересно как это делать правильно и без лишних телодвижений, и есть ли кросплотформенный вариант?. (Достаточно для Win and Linux) Заранее спасибо.

[Odyssey]

Если ВЫ -- это "вы все", то я делаю такие замеры нехитро, через

Код: Выделить всё

Now()*24*60*60*1000

Точность не ахти: у меня была 16 миллисекунд, т.е. 0..16 = 16, 17..32 = 32 и т.д., это связано с разрешением системного таймера. Зато работает на всех платформах и не требует лишних зависимостей. Если кто-то подскажет способ лучше, буду очень рад.

[Vadim]

Maxizar
Для Windows - два раза получить GetTickCount до и после выполнения процедуры, потом вычесть из второго первое. Для Linux - fpGetTimeOfDay(). Кроссплатформенность обеспечивается с помощью {$DEFINE ... }
Это для однопоточного приложения.

[Maxizar]

Vadim Следуя вашим советам вот, что у меня получилось. Модуль PerformanceTime содержит подпрограммы:
Procedure InitPerformance(var PerfTime:TPerformanceTime);
Procedure StartPerformance(var PerfTime:TPerformanceTime);
Function StopPerformance(var PerfTime:TPerformanceTime):Real;
Function GetTimeInSec:Real;

Смысл: InitPerformance – необходима для подсчета времени задержки самой функции подсчета времени. (ну чтоб наш результат был более точным.)

Код: Выделить всё

unit PerformanceTime;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils,
  {$IFDEF windows}
  Windows;
  {$ENDIF}
  {$IFDEF UNIX}
  Unix, BaseUnix;
  {$ENDIF}

Type
   TPerformanceTime=record
      TimerDelay:Real;   //Задержка (время) самого вычисления в секундах
      StartTime :Real;  //Время начала теста в секундах
   end;


  Procedure InitPerformance(var PerfTime:TPerformanceTime);
  Procedure StartPerformance(var PerfTime:TPerformanceTime);
  Function  StopPerformance(var PerfTime:TPerformanceTime):Real;
  Function  GetTimeInSec:Real;

implementation

procedure InitPerformance(var PerfTime: TPerformanceTime);
begin
  PerfTime.TimerDelay:=0;
  StartPerformance(PerfTime);
  PerfTime.TimerDelay:=StopPerformance(PerfTime);
end;

procedure StartPerformance(var PerfTime: TPerformanceTime);
begin
   PerfTime.StartTime:=GetTimeInSec;
end;

function StopPerformance(var PerfTime: TPerformanceTime): Real;
begin
  Result:=GetTimeInSec-PerfTime.StartTime-PerfTime.TimerDelay;
end;

function GetTimeInSec: Real;
var
  {$IFDEF windows}
  StartCount, Freq: Int64;
  {$ENDIF}

   {$IFDEF UNIX}
  TimeLinux:timeval;
  {$ENDIF}
begin
  {$IFDEF windows}
   if QueryPerformanceCounter(StartCount) then //возвращает текущее значение счетчика
    begin
      QueryPerformanceFrequency(Freq);   //Кол-во тиков в секунду
      Result:=StartCount/Freq;           //Результат в секундах
    end
  else
    Result:=GetTickCount*1000;           //*1000 т.к  GetTickCount вернем милиСекунды
  {$ENDIF}

  {$IFDEF UNIX}
   fpGetTimeOfDay(@TimeLinux,nil);
   Result:=TimeLinux.tv_sec + TimeLinux.tv_usec/1000000;
  {$ENDIF}
end;
end.


Пользоваться можно так:

Код: Выделить всё

procedure TForm1.Button1Click(Sender: TObject);
var
  T:TPerformanceTime;
begin

     InitPerformance(T);
     StartPerformance(T);
     Sleep(1000);
     Caption:=FloatToStr(StopPerformance(T));
end;


На первый взгляд все работает, даже в Linux (хотя в Linux я не силен ).
Хотелось бы услышать мнение мэтров и если кто знает более правильный метод подскажите.

[SII]

2. Если дело в этих трех операциях, тогда время выполнения кода на С должно быть 0.12 минимум (при условии, что умножение примерно равно по сложности делению и намного сложнее сложения - на самом деле я вообще не знаток, как эти операции реализованы).

Чрезвычайно краткий ликбез по скорости выполнения операций

1) Операции типа сложения-вычитания, логических, одноразрядных сдвигов (так называемые простые операции) практически на всех машинах во все века выполнялись с максимально возможной скоростью (быстрей могли быть только операции пересылки и сравнения, и то обычно время было одинаковым). Можем условно принять время, затрачиваемое на выполнение подобных операций, за 1.

2) Операции умножения на основной массе ранних (с нынешней точки зрения) процессоров либо вообще не были реализованы (их приходилось выполнять с помощью подпрограммы -- скорость понятно какая), либо присутствовали, но сводились к цепочке сложений и одноразрядных сдвигов. Время их выполнения тогда обычно было не меньше, чем разрядность операндов. Правда, уже тогда были машины, где для умножения применялись более хитрые и быстрые алгоритмы. В наши же дни почти на всех процессорах умножение выполняется со скоростью, близкой к сложению. Например, на 8-разрядных микроконтроллерах ATmega сложение и большинство других операций выполняются за 1 такт, а умножение -- за 2 такта. Для процессоров ПК точно сказать сложно, ибо участвует много факторов (на самом деле все процессоры, начиная с первого пентиума, умели выполнять в определённых условиях несколько команд одновременно). Так что грубо можем считать, что для ПК скорость умножения не слишком меньше скорости простых операций.

3) А вот с операцией деления полная задница. В отличие от умножения, её невозможно ускорить алгоритмически, поскольку каждый следующий шаг зависит от результатов предыдущего. В результате самые что ни на есть навороченные процессоры современных компутеров по относительной скорости если и быстрей делят, то ненамного, чем компутеры 1950-х годов (прирост скорости обеспечивается главным образом за счёт ускорения и совмещения вспомогательных операций, а не за счёт собственно деления). В случае с 32-разрядным кодом можем грубо считать, что деление выполняется в 15-30 раз медленней, чем умножение. Именно поэтому многие компиляторы заменяют деление на константу цепочкой умножений, сложений, сдвигов и логических операций: команд больше, но скорость всё равно выше. К сожалению, заменить деление на переменную невозможно.

[wolfheart]

2. Если дело в этих трех операциях, тогда время выполнения кода на С должно быть 0.12 минимум (при условии, что умножение примерно равно по сложности делению и намного сложнее сложения - на самом деле я вообще не знаток, как эти операции реализованы).

Чрезвычайно краткий ликбез по скорости выполнения операций

1) Операции типа сложения-вычитания, логических, одноразрядных сдвигов (так называемые простые операции) практически на всех машинах во все века выполнялись с максимально возможной скоростью (быстрей могли быть только операции пересылки и сравнения, и то обычно время было одинаковым). Можем условно принять время, затрачиваемое на выполнение подобных операций, за 1.

2) Операции умножения на основной массе ранних (с нынешней точки зрения) процессоров либо вообще не были реализованы (их приходилось выполнять с помощью подпрограммы -- скорость понятно какая), либо присутствовали, но сводились к цепочке сложений и одноразрядных сдвигов. Время их выполнения тогда обычно было не меньше, чем разрядность операндов. Правда, уже тогда были машины, где для умножения применялись более хитрые и быстрые алгоритмы. В наши же дни почти на всех процессорах умножение выполняется со скоростью, близкой к сложению. Например, на 8-разрядных микроконтроллерах ATmega сложение и большинство других операций выполняются за 1 такт, а умножение -- за 2 такта. Для процессоров ПК точно сказать сложно, ибо участвует много факторов (на самом деле все процессоры, начиная с первого пентиума, умели выполнять в определённых условиях несколько команд одновременно). Так что грубо можем считать, что для ПК скорость умножения не слишком меньше скорости простых операций.

3) А вот с операцией деления полная задница. В отличие от умножения, её невозможно ускорить алгоритмически, поскольку каждый следующий шаг зависит от результатов предыдущего. В результате самые что ни на есть навороченные процессоры современных компутеров по относительной скорости если и быстрей делят, то ненамного, чем компутеры 1950-х годов (прирост скорости обеспечивается главным образом за счёт ускорения и совмещения вспомогательных операций, а не за счёт собственно деления). В случае с 32-разрядным кодом можем грубо считать, что деление выполняется в 15-30 раз медленней, чем умножение. Именно поэтому многие компиляторы заменяют деление на константу цепочкой умножений, сложений, сдвигов и логических операций: команд больше, но скорость всё равно выше. К сожалению, заменить деление на переменную невозможно.

Да наверное тема старая, но на будущее скажу, что умножение и деление на PC скоростью мало отличаются, потому как деление - это умножение на обратное число. А получить обратное число не проблема.

[kipar]

потому как деление - это умножение на обратное число. А получить обратное число не проблема.

Там наверное речь о целых числах шла, для целых чисел деление медленнее.

[sign]

Делов то, по ссылке глянуть. Я про целочисленность и деление.

Код: Выделить всё

Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.


Output

For every number N, output a single line containing the single non-negative integer Z(N).
Example

Sample Input:
6
3
60
100
1024
23456
8735373

Sample Output:
0
14
24
253
5861
2183837