Optimisation of algorithms. - page 5

[TheXpert]

Mathemat:
In principle, yes. But still no more than O(n).

Not less :) with a good imagination you can make an exponential dependence :)

[Vasiliy Sokolov]

Mathemat:

Well this is not an optimization problem.

Finding an extremum is always a problem of order O(n), where n is the number of data. How one can make this asymptotic worse - I have no idea.

The simplest algorithm is ArraySort(), which is built-in fast enough, but it is probably redundant for this problem.

You could come up with something recursive that would be faster.

How long does it take to find the minimum and for how many bars?

I gave the statistics in the first post. The calculation for 1,000,000 bars arithmetically increases as the period increases. So for period 3, the calculation takes 0.54 seconds, for period 51 it takes 0.94 seconds, and for period 99 it takes 1.59 seconds.

This is worse because it uses the loop in the loop, which is an error. So, for period 3 the number of iterations will be 1 000 000 * (3-1/2) = 1 000 000, while for period 99 it will be 1 000 000 * (99-1)/2 = 49 000 000! Therefore we need to rewrite the algorithm in such a way that the number of iterations would not qualitatively increase with increasing the period - this is a pure optimization problem. This is what I am doing now. So far I have written this:

static void Up(Bars MyQuotes)
        {
            BitArray bits = new BitArray(MyQuotes.Count);
            double max = double.MinValue;
            int pperiod = (23 - 1) / 2;
            int bar = pperiod;
            int count = MyQuotes.Count - pperiod;
            //последняя позиция второго перебора.
            int pos = bar;
            while (bar < count)
            {
                for (int i = 1; i <= pperiod; i++)
                {
                    max = MyQuotes.High[bar - i] > MyQuotes.High[bar + i]
                              ? MyQuotes.High[bar - i]
                              : MyQuotes.High[bar + i];
                    pos = bar + i;
                    if(max > MyQuotes.High[bar])
                    {
                        //Начинаем с последнего бара
                        bar = pos;
                        break;
                    }
                    if(i == pperiod)
                    {
                        bits[bar + i] = true;
                        bar = pos;
                    }
                }
            }
        }

To search for the minimum, the corresponding function Down() will be launched in a parallel thread. When both functions terminate, their results will be written in the general list. It goes something like this.

[Sceptic Philozoff]

C-4: I gave the statistics in the first post. The calculation for 1,000,000 bars grows arithmetically as the period increases. So for period 3, the calculation takes 0.54 seconds, for period 51 0.94 seconds, and for period 99 it is already 1.59 seconds.

There you go, you got it wrong. It's not the sum of a richmetic progression, C-4. The sum grows quadratically.

OCL is unambiguous.

[Vasiliy Sokolov]

Mathemat:

The simplest algorithm is ArraySort(), built-in fast enough, something around O(n * ln( n ) ). But it's probably redundant for this problem.

Thought. Any sorting will be inherently slower than going through the whole array via for. For gives one iteration, while arraysort at best will sort values in each subwindow n, which itself will mean dozens of actions.

No, you should still aim for the total number of iterations to be qualitatively the same as the number of bars.

[Vasiliy Sokolov]

Mathemat:

There you go, you got it wrong. It's not the sum of a richmetic progression, C-4. The sum grows quadratically.

OCL is unambiguous.

If it's quadratic, it's even worse. Without multithreading, as I understand it, there is no way around it.

[hrenfx]

The condition for such an extremum search is strange to say the least... But even so, it is extremely unreasonable to use a brute force search method.

A one-pass classic ZigZag with ExtDepth = n comes immediately to mind with a slight adjustment to the current condition. OCL is 100% unnecessary here.

[TheXpert]

You guys are on fire. All three of you.

[Vasiliy Sokolov]

hrenfx:

The condition for such an extremum search is strange to say the least... But even so, it is extremely unreasonable to use a brute force search method.

The one-pass classic ZigZag with ExtDepth = n comes immediately to mind with a slight adjustment to the current condition. OCL is 100% unnecessary here.

Well in principle I need these extrema for a la zig-zag. Then which algorithms are better to use? Is there a more efficient code than the one I cited in the second version?

[hrenfx]

Check out the single-pass ZigZags in CodeBase MT4 - O(N).

[Sceptic Philozoff]

TheXpert: You guys are on fire. All three of you.

Why? O(n) will still be there, no matter how you look at it.

If all else fails, try OCL. There are no other ways without dll-type perversions in 5.