Попробуйте сравнить быстродействие рекурсии и итерации - Статьи и техническая библиотека по автоматическому трейдингу

Nikolai Semko 2019.04.03 23:00 #21

fxsaber:

Например, получение списка всех файлов песочницы удобно реализовывать именно через рекурсию.

захотелось сравнить быстродействие рекурсии и итерации.

Оказалось, что рекурсия побыстрее работает более чем в два раза...

Наверное из-за того что стек работает быстрее...

Удивительное рядом. Ожидал обратный эффект. ))

#define size 1000000
uint sum1=0,sum2=0;
int i;
int X[];
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
   ArrayResize(X,size);
   for(i=0;i<size;i++) X[i]=rand();

   ulong t=GetMicrosecondCount();
   i=0;
   while(i<size) { sum1+=X[i]; i++;}
//Recursion();
   ulong t1=GetMicrosecondCount()-t;

   t=GetMicrosecondCount();
   i=0;
//while(i<size) { sum1+=X[i]; i++;}
   Recursion();
   ulong t2=GetMicrosecondCount()-t;
   Print("время выполнения цикла    = "+string(t1)+" , контрольная сумма = "+string(sum1));
   Print("время выполнения рекурсии = "+string(t2)+" , контрольная сумма = "+string(sum2));
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void Recursion()
  {
   sum2+=X[i];
   i++;
   if(i<size) Recursion();
  }
//+------------------------------------------------------------------+

2019.04.03 19:06:40.776 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1667 , контрольная сумма = 3510404212
2019.04.03 19:06:40.776 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 697 , контрольная сумма = 3510404212
2019.04.03 19:06:41.697 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1653 , контрольная сумма = 3492310620
2019.04.03 19:06:41.697 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 699 , контрольная сумма = 3492310620
2019.04.03 19:06:42.549 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1529 , контрольная сумма = 3510953577
2019.04.03 19:06:42.549 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 696 , контрольная сумма = 3510953577
2019.04.03 19:06:43.332 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1559 , контрольная сумма = 3512212419
2019.04.03 19:06:43.332 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 698 , контрольная сумма = 3512212419
2019.04.03 19:06:44.098 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1707 , контрольная сумма = 3497178596
2019.04.03 19:06:44.098 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 472 , контрольная сумма = 3497178596
2019.04.03 19:06:44.839 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 2088 , контрольная сумма = 3485051380
2019.04.03 19:06:44.839 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 482 , контрольная сумма = 3485051380
2019.04.03 19:06:45.538 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1612 , контрольная сумма = 3487817581
2019.04.03 19:06:45.538 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 448 , контрольная сумма = 3487817581
2019.04.03 19:06:46.397 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1742 , контрольная сумма = 3475121003
2019.04.03 19:06:46.397 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 497 , контрольная сумма = 3475121003
2019.04.03 19:06:47.262 TestLoopVsRecursion (EURUSD,M1) время выполнения цикла    = 1701 , контрольная сумма = 3485556615
2019.04.03 19:06:47.262 TestLoopVsRecursion (EURUSD,M1) время выполнения рекурсии = 701 , контрольная сумма = 3485556615

Файлы:

TestLoopVsRecursion.mq5 3 kb

Sergey Pavlov 2019.04.04 03:15 #22

Интересный результат...

fxsaber 2019.04.04 04:24 #23

Nikolai Semko:

Оказалось, что рекурсия побыстрее работает более чем в два раза...

По-моему, такой результат полного цикла - баг оптимизации.

Надо звать @Ilyas для анализа.

Nikolai Semko 2019.04.04 09:22 #24

fxsaber:

По-моему, такой результат полного цикла - баг оптимизации.

Надо звать @Ilyas для анализа.

возможно.

1.7 наносекунды на одну итерацию (сумма с элементом массива+приращение индекса+проверка индекса) - как-то многовато.

Ilyas 2019.04.04 12:59 #25

fxsaber:

По-моему, такой результат полного цикла - баг оптимизации.

Надо звать @Ilyas для анализа.

Да, тут есть над чем поработать

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

Для скорости (более лучших оптимизаций компилятором) работы программы в циклах, старайтесь избегать использования (адресации к) глобальных переменных и членов объектов.

Попробуйте в приведённом примере использовать локальную sum1 вместо глобальной

Ошибки, баги, вопросы Помогите с организацией кода ООП для школьников.

Nikolai Semko 2019.04.04 13:24 #26

Ilyas:

Для скорости (более лучших оптимизаций компилятором) работы программы в циклах, старайтесь избегать использования (адресации к) глобальных переменных и членов объектов.

т.е. и внутренние static переменные лучше не использовать, т.к. они по сути глобальные?

Nikolai Semko 2019.04.04 13:35 #27

Ilyas:

Представленная рекурсия вырождается в цикл, который очень похож на сравниваемый, только оптимизируется он лучше.

Я правильно понял, что линковщик из рекурсии формирует цикл и в такой форме рекурсивной функции переполнения стека можно не бояться?

Nikolai Semko 2019.04.04 14:17 #28

Ilyas:

Попробуйте в приведённом примере использовать локальную sum1 вместо глобальной

#define size 1000000

void OnStart()
  {
   uint sum1=0,sum2=0;
   uint i;
   uint X[];
   ArrayResize(X,size);
   for(i=0;i<size;i++) X[i]=rand();

   ulong t=GetMicrosecondCount();
   i=0;
   while(i<size) { sum1+=X[i]; i++;}
//Recursion(X,sum2,i);
   ulong t1=GetMicrosecondCount()-t;

   t=GetMicrosecondCount();
   i=0;
//while(i<size) { sum1+=X[i]; i++;}
   Recursion(X,sum2,i);
   ulong t2=GetMicrosecondCount()-t;
   Print("время выполнения цикла    = "+string(t1)+" , контрольная сумма = "+string(sum1));
   Print("время выполнения рекурсии = "+string(t2)+" , контрольная сумма = "+string(sum2));
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void Recursion(uint &X[],uint &sum, uint &i)
  {
   sum+=X[i];
   i++;
   if(i<size) Recursion(X,sum,i);
  }
//+------------------------------------------------------------------+

цикл стал работать чуть быстрее, но все равно рекурсия в выигрыше.

Не понятно только, почему при локальных переменных рекурсия стала работать медленнее. (Хотя может быть и нет).

2019.04.04 10:12:58.543 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 1336 , контрольная сумма = 3487162002
2019.04.04 10:12:58.543 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 731 , контрольная сумма = 3487162002
2019.04.04 10:12:59.699 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 1245 , контрольная сумма = 3506532416
2019.04.04 10:12:59.699 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 564 , контрольная сумма = 3506532416
2019.04.04 10:13:00.817 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 1339 , контрольная сумма = 3496835181
2019.04.04 10:13:00.817 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 707 , контрольная сумма = 3496835181
2019.04.04 10:13:01.914 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 934 , контрольная сумма = 3500433162
2019.04.04 10:13:01.914 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 706 , контрольная сумма = 3500433162
2019.04.04 10:13:06.490 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 677 , контрольная сумма = 3497819967
2019.04.04 10:13:06.490 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 517 , контрольная сумма = 3497819967
2019.04.04 10:13:07.639 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 697 , контрольная сумма = 3486763121
2019.04.04 10:13:07.639 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 524 , контрольная сумма = 3486763121
2019.04.04 10:13:08.687 TestLoopVsRecursion (NZDUSD,M1) время выполнения цикла    = 1281 , контрольная сумма = 3499858159
2019.04.04 10:13:08.687 TestLoopVsRecursion (NZDUSD,M1) время выполнения рекурсии = 699 , контрольная сумма = 3499858159

Ilyas 2019.04.04 14:53 #29

Nikolai Semko:
Я правильно понял, что линковщик из рекурсии формирует цикл и в такой форме рекурсивной функции переполнения стека можно не бояться?

Не закладывайтесь на это, мы можем пересмотреть оценку для подобной оптимизации рекурсивной функций

А так да, при удалении рекурсии, тело функции превращается в цикл, вместо рекурсивного вызова, соответственно, стек не может быть переполнен

Новая версия платформы MetaTrader Рекурсия и передача ссылок Бета-версия платформы MetaTrader 5

Renat Akhtyamov 2019.04.07 07:16 #30

Николай, как выполнить ползунок, т.е. просто код, без библиотек?

Индикаторы: MaFromMa - страница 3