Optimisation of algorithms. - page 6

New comment
 
C-4:

The whole problem is in the second cycle. It simultaneously handles left and right branches from potential extremum and hence it only goes through (N - 1)/2 bars, but that is not enough. Measurements show that time spent on searching for an extremum in an arithmetic progression depends on the period N, which is very, very bad:

At least one break is missing:

//Перебираем все бары
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; // А зачем искать дальше?
   }
}

Better still, really split the top and bottom, and stop immediately after an unsuccessful check.

 
Mathemat:

If all else fails, try OCL.

It won't make much difference.
 
TheXpert:
It won't make a big difference.
Yes, it will. This is because the task does not require sequential execution. The entire bar history can be divided into k segments, each of which will be processed by a different CPU core. I do not know the mechanics of OCL, but I think the principle is the same here. Another thing with the zig-zag itself is that it is sequential, each new line starts from the end of the previous one, which makes splitting into subtasks extremely difficult or even impossible.
 
komposter:

At least one break is missing:

Better still, really separate top and bottom, and stop immediately after an unsuccessful check.

Again, separating top and bottom results in two passes for. Which doubles the search time. Separation by itself does not give any performance gain without using multithreading, especially for small n.
 

Still, OCL (or paralleling in the general sense) is not an algorithmic optimization, but rather a technical one.

I doubt that in your case there is a need to parallelize the fastest O(N)-variant solution to the problem.

 
C-4:
He will.

No yada yada? Show me.

So, good luck. To discuss optimization of an algorithm with complexity that is linearly dependent on the value of a parameter is probably something you have nothing to do.

 
TheXpert:

No yada yada? Show me.

Anyway, good luck. Discuss the optimization of an algorithm with complexity linearly dependent on the value of a parameter - you really have nothing to do.

OK, I will finish completing the algorithm and post the paralleling results in the studio.

hrenfx:

Still, OCL (or paralleling in the general sense) is not an algorithmic optimization - it is more of a technical one.

I doubt that there is a need to parallelize the fastest O(N)-variant solution in your case.

How can I put it. Any parallelization is always a serious complication of algorithms. Moreover, if you don't parallelize an algorithm with linear dependence on the amount of data, what else can you parallelize?

In short, I will rewrite the algorithm and see what it brings.

 
C-4:
Again, separation of tops and bottoms results in two passes for. This doubles the time of search. Separation by itself does not give performance gain without using multithreading, especially for small n.

How can you be so sure?

My check shows otherwise:

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

01:29:25 SpeedTest EURUSD,M15: Number of bars = 3780

01:30:46 SpeedTest EURUSD,M15: Original function: 81.558 sec, extrema: 131 / 121

01:31:10 SpeedTest EURUSD,M15: With my edit (break): 23.291 sec, extrema: 131 / 121

01:31:27 SpeedTest EURUSD,M15: With my break (break): 17.565 sec, extrema: 131 / 121

Attached is an mq4 script.

Files:
SpeedTest.mq4  4 kb
 

One more test to complete the picture:

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

01:38:56 SpeedTest EURUSD,M1: Number of bars = 33896

01:50:19 SpeedTest EURUSD,M1: Original function: 683.565 sec, extrema: 121 / 127

01:50:54 SpeedTest EURUSD,M1: With my edit (break): 34.383 sec, extrema: 121 / 127

01:51:16 SpeedTest EURUSD,M1: With my break (break): 22.714 sec, extrema: 121 / 127

 
komposter:
C.T.D. wrote exactly that in his first post.
12345678910
New comment
Reason: