Оптимизация алгоритмов. - страница 6

Новый комментарий
 
C-4:

 Вся проблема во втором цикле. Он одновременно обрабатывает левую и правую ветки от потенциального экстремума, а потому перебирает лишь (N - 1)/2 баров, но этого не достаточно. Иземерения показывают, что время затраченное на поиск экстремума в арифметической прогрессии зависит от периода N, а это очень, очень плохо:

Как минимум, одного break-а не хватает:

//Перебираем все бары
for (int bar = 0; bar < MyQuotes.Count; bar++)
{
   //Подготовка данных
   ...
   int pperiod = (N - 1)/2;
   //Перебираем бары относительно потенциального экстремума
   for (int i = 1; i <= pperiod; i++)
   {
      if (MyQuotes.High[bar - i] > MyQuotes.High[bar] ||
         MyQuotes.High[bar + i] > MyQuotes.High[bar])
         up = false;
      if (MyQuotes.Low[bar - i] < MyQuotes.Low[bar] ||
         MyQuotes.Low[bar + i] < MyQuotes.Low[bar])
         down = false;

      if ( !up && !down ) break; // А зачем искать дальше?
   }
}

 А лучше действительно разделить верх и низ, и останавливаться сразу после неудачной проверки. 

 
Mathemat:

Если ничего не помогает - попробуй OCL.

Не даст большого выигрыша.
 
TheXpert:
Не даст большого выигрыша.
Еще как даст. А все потому что задача не требует последовательного выполнения. Всю историю баров можно разбить на k сегментов, каждый из которых будет обрабатывать своё ядро ЦП. Механики OCL не знаю, но думаю здесь тот же самый принцип. Другое дело с самим зиг-загом - он последователен, каждая новая линия начинается с окончания предыдущей, а значит разделение на подзадачи крайне сложно, либо вообще невозможно. 
 
komposter:

Как минимум, одного break-а не хватает:

 А лучше действительно разделить верх и низ, и останавливаться сразу после неудачной проверки. 

Опять-таки разделение верха и низа выливается в два прохода for. Что в двое увеличивает время перебора. Само по себе разделение без использования многопоточности выигрыш в производительности не дает, особенно на малых n.
 

Все же OCL (или распараллеливание в общем смысле) не является алгоритмической оптимизацией, скорее технической.

Сомневаюсь, что в вашем случае есть необходимость параллелить быстрейший O(N)-вариант решения задачи.

 
C-4:
Еще как даст.

А без ля-ля? Покажите.

Короче удачи. Обсуждать оптимизацию алгоритма со сложностью линейно зависимой от значения параметра это видимо реально нечем заняться.

 
TheXpert:

А без ля-ля? Покажите.

Короче удачи. Обсуждать оптимизацию алгоритма со сложностью линейно зависимой от значения параметра это видимо реально нечем заняться.

О.К. Допишу алгоритм, и выложу результаты распараллеливания в студию.

hrenfx:

Все же OCL (или распараллеливание в общем смысле) не является алгоритмической оптимизацией, скорее технической.

Сомневаюсь, что в вашем случае есть необходимость параллелить быстрейший O(N)-вариант решения задачи.

Как сказать. Любое распараллеливание это всегда серьезное усложнение алгоритмов. Тем более, если не параллелить алгоритм с линейной зависимостью от количества данных, тогда что тогда имеет смысл парралелить? 

Короче, перепишу алгоритм, и посмотрим что это даст.

 
C-4:
Опять-таки разделение верха и низа выливается в два прохода for. Что в двое увеличивает время перебора. Само по себе разделение без использования многопоточности выигрыш в производительности не дает, особенно на малых n.

Откуда такая уверенность?

Моя проверка показывает обратное:

01:29:25 SpeedTest EURUSD,M15 inputs: Interations=10000; pperiod=10; 

01:29:25 SpeedTest EURUSD,M15: Количество баров = 3780

01:30:46 SpeedTest EURUSD,M15: Оригинальная функция: 81.558 сек, экстремумов: 131 / 121

01:31:10 SpeedTest EURUSD,M15: С моей правкой (break): 23.291 сек, экстремумов: 131 / 121

01:31:27 SpeedTest EURUSD,M15: С разделением на циклы: 17.565 сек, экстремумов: 131 / 121

 Скрипт mq4 в аттаче.

Файлы:
SpeedTest.mq4  4 kb
 

Для полноты картины еще один тест:

01:38:56 SpeedTest EURUSD,M1 inputs: Interations=1000; pperiod=100; 

01:38:56 SpeedTest EURUSD,M1: Количество баров = 33896

01:50:19 SpeedTest EURUSD,M1: Оригинальная функция: 683.565 сек, экстремумов: 121 / 127

01:50:54 SpeedTest EURUSD,M1: С моей правкой (break): 34.383 сек, экстремумов: 121 / 127

01:51:16 SpeedTest EURUSD,M1: С разделением на циклы: 22.714 сек, экстремумов: 121 / 127

 
komposter:
Ч.Т.Д. именно это и писал в первом же посте.
12345678910
Новый комментарий
Причина обращения: