Optimización de algoritmos. - página 6

[Andrey Khatimlianskii]

C-4:

Todo el problema está en el segundo ciclo. Maneja simultáneamente las ramas izquierda y derecha del extremo potencial y, por lo tanto, sólo pasa por (N - 1)/2 barras, pero eso no es suficiente. Las mediciones muestran que el tiempo empleado en buscar un extremo en una progresión aritmética depende del periodo N, lo que es muy, muy malo:

Falta al menos un descanso:

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

Mejor aún, dividir realmente la parte superior y la inferior, y parar inmediatamente después de un control infructuoso.

[TheXpert]

Mathemat:

Si todo lo demás falla, pruebe con la OCL.

No habrá mucha diferencia.

[Vasiliy Sokolov]

TheXpert:
No habrá una gran diferencia.

Sí, lo hará. Esto se debe a que la tarea no requiere una ejecución secuencial. Todo el historial de barras puede dividirse en k segmentos, cada uno de los cuales será procesado por un núcleo de CPU diferente. No conozco la mecánica de la OCL, pero creo que el principio es el mismo aquí. El zig-zag en sí mismo es otro asunto: es secuencial, cada nueva línea comienza desde el final de la anterior, por lo que dividirlo en subtareas es extremadamente difícil o incluso imposible.

[Vasiliy Sokolov]

komposter:

Falta al menos un descanso:

Mejor aún, separe realmente la parte superior y la inferior, y deténgase inmediatamente después de un control infructuoso.

Una vez más, al separar la parte superior y la inferior se obtienen dos pases para. Lo que duplica el tiempo de búsqueda. La separación por sí misma no ofrece ninguna ganancia de rendimiento sin utilizar el multithreading, especialmente para n pequeños.

[hrenfx]

Aun así, la OCL (o el paralelismo en sentido general) no es una optimización algorítmica, sino técnica.

Dudo que en tu caso haya necesidad de paralelizar la solución más rápida O(N)-variable del problema.

[TheXpert]

C-4:
Lo hará.

¿No hay yada yada? Muéstrame.

Así que, buena suerte. Discutir la optimización de un algoritmo cuya complejidad depende linealmente del valor de un parámetro es probablemente algo que no tiene nada que ver.

[Vasiliy Sokolov]

TheXpert:

¿No hay yada yada? Muéstrame.

De todos modos, buena suerte. Discutir la optimización de un algoritmo cuya complejidad depende linealmente del valor de un parámetro.

Bien, terminaré de completar el algoritmo y publicaré los resultados del paralelismo en el estudio.

hrenfx:

Aun así, la OCL (o el paralelismo en sentido general) no es una optimización algorítmica, sino más bien técnica.

Dudo que haya necesidad de paralelizar la solución más rápida de O(N)-variante en su caso.

¿Cómo puedo decirlo? Cualquier paralelización es siempre una grave complicación de los algoritmos. Además, si no se paraleliza un algoritmo con dependencia lineal de la cantidad de datos, ¿qué más se puede paralizar?

En resumen, voy a reescribir el algoritmo y ver lo que trae.

[Andrey Khatimlianskii]

C-4:
De nuevo, la separación de las partes superiores e inferiores da lugar a dos pases para. Esto duplica el tiempo de búsqueda. La separación por sí misma no proporciona una ganancia de rendimiento sin utilizar el multithreading, especialmente para n pequeños.

¿Cómo puedes estar tan seguro?

Mi comprobación muestra lo contrario:

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

01:29:25 SpeedTest EURUSD,M15: Número de barras = 3780

01:30:46 SpeedTest EURUSD,M15: Función original: 81.558 seg, extrema: 131 / 121

01:31:10 SpeedTest EURUSD,M15: Con mi edición (ruptura): 23.291 seg, extrema: 131 / 121

01:31:27 SpeedTest EURUSD,M15: Con mi ruptura (break): 17.565 seg, extrema: 131 / 121

Se adjunta un script mq4.

[Andrey Khatimlianskii]

Una prueba más para completar el cuadro:

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

01:38:56 SpeedTest EURUSD,M1: Número de barras = 33896

01:50:19 SpeedTest EURUSD,M1: Función original: 683,565 seg, extrema: 121 / 127

01:50:54 SpeedTest EURUSD,M1: Con mi edición (ruptura): 34.383 seg, extrema: 121 / 127

01:51:16 SpeedTest EURUSD,M1: Con mi ruptura (break): 22.714 seg, extrema: 121 / 127

[TheXpert]

komposter:

C.T.D. escribió exactamente eso en su primer post.