Optimización de algoritmos. - página 5

[TheXpert]

Mathemat:
En principio, sí. Pero aún así no es más que O(n).

No menos :) con una buena imaginación se puede hacer una dependencia exponencial:)

[Vasiliy Sokolov]

Mathemat:

Bueno, esto no es un problema de optimización.

Encontrar un extremo es siempre un problema de orden O(n), donde n es el número de datos. Cómo se puede empeorar esta asintótica, no tengo ni idea.

El algoritmo más sencillo es ArraySort(), que es lo suficientemente rápido incorporado, pero es probablemente redundante para este problema.

Podrías idear algo recursivo que fuera más rápido.

¿Cuánto tiempo se tarda en encontrar el mínimo y para cuántas barras?

He dado las estadísticas en el primer post. El cálculo para 1.000.000 de barras aumenta aritméticamente a medida que aumenta el periodo. Así, para el periodo 3, el cálculo tarda 0,54 segundos, para el periodo 51 tarda 0,94 segundos y para el periodo 99 tarda 1,59 segundos.

Esto es peor porque utiliza el bucle en el bucle, lo que es un error. Así, para el periodo 3 el número de iteraciones será de 1 000 000 * (3-1/2) = 1 000 000, mientras que para el periodo 99 será de 1 000 000 * (99-1)/2 = ¡49 000 000! Por lo tanto, tenemos que reescribir el algoritmo de tal manera que el número de iteraciones no aumente cualitativamente con el aumento del período - este es un problema de optimización pura. Esto es lo que estoy haciendo ahora. Hasta ahora he escrito esto:

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;
                    }
                }
            }
        }

Para buscar el mínimo, se lanzará la función correspondiente Down() en un hilo paralelo. Cuando ambas funciones terminan, sus resultados se escriben en la lista general. Es algo así.

[Sceptic Philozoff]

C-4: He dado las estadísticas en el primer post. El cálculo para 1.000.000 de barras crece aritméticamente a medida que aumenta el periodo. Así, para el periodo 3, el cálculo tarda 0,54 segundos, para el periodo 51 0,94 segundos, y para el periodo 99 ya es de 1,59 segundos.

Ahí lo tienes, lo has entendido mal. No es la suma de una progresión rica, C-4. La suma crece cuadráticamente.

La OCL no es ambigua.

[Vasiliy Sokolov]

Mathemat:

El algoritmo más sencillo es ArraySort(), bastante rápido incorporado, algo así como O(n * ln( n ) ). Pero probablemente sea redundante para este problema.

Pensamiento. Cualquier ordenación será intrínsecamente más lenta que recorrer todo el array mediante for. Para da una iteración, mientras que arraysort en el mejor de los casos ordenará los valores en cada subventana n, lo que en sí mismo significará docenas de acciones.

No, el objetivo es que el número total de iteraciones sea cualitativamente igual al número de barras.

[Vasiliy Sokolov]

Mathemat:

Ahí lo tienes, lo has entendido mal. No es la suma de una progresión rica, C-4. La suma crece cuadráticamente.

La OCL no es ambigua.

Si es cuadrática, es aún peor. Sin multithreading, según tengo entendido, no hay manera de evitarlo.

[hrenfx]

La condición para una búsqueda tan extrema es, cuando menos, extraña... Pero aun así, es muy poco razonable utilizar un método de búsqueda de fuerza bruta.

Un ZigZag clásico de una pasada con ExtDepth = n viene inmediatamente a la mente con un ligero ajuste a la condición actual. La OCL es 100% innecesaria aquí.

[TheXpert]

Ustedes están en llamas. Los tres.

[Vasiliy Sokolov]

hrenfx:

La condición para una búsqueda tan extrema es, cuando menos, extraña... Pero aun así, es muy poco razonable utilizar un método de búsqueda de fuerza bruta.

Un ZigZag clásico de una pasada con ExtDepth = n viene inmediatamente a la mente con un ligero ajuste a la condición actual. La OCL es 100% innecesaria aquí.

Bueno en principio necesito estos extremos para una la zig-zag. Entonces, ¿qué algoritmos es mejor utilizar? ¿Existe un código más eficiente que el que he citado en la segunda versión?

[hrenfx]

Compruebe los ZigZags de una sola pasada en CodeBase MT4 - O(N).

[Sceptic Philozoff]

TheXpert: Ustedes están en llamas. Los tres.

¿Por qué? O(n) seguirá estando ahí, se mire como se mire.

Si todo lo demás falla, pruebe con la OCL. No hay otros caminos sin perversiones de tipo dll en 5.