FórumSeções

Optimização dos algoritmos. - página 6

Novo comentário
C-4:

O problema está todo no segundo ciclo. Lida simultaneamente com ramos esquerdos e direitos a partir de potenciais extremos e, portanto, só passa por (N - 1)/2 barras, mas isso não é suficiente. As medições mostram que o tempo gasto na procura de um extremo numa progressão aritmética depende do período N, que é muito, muito mau:

Falta pelo menos uma pausa:

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

Melhor ainda, dividir realmente o topo e a base, e parar imediatamente após um controlo mal sucedido.

Mathemat:

Se tudo o resto falhar, tente OCL.

Não vai fazer muita diferença.
TheXpert:
Não fará uma grande diferença.
Sim, vai. Isto porque a tarefa não requer execução sequencial. Todo o histórico do bar pode ser dividido em segmentos k, cada um dos quais será processado por um núcleo de CPU diferente. Não conheço a mecânica da OCL, mas penso que o princípio é o mesmo aqui. O zig-zag em si é outra questão - é sequencial, cada nova linha começa a partir do fim da anterior, pelo que dividi-la em subtarefas é extremamente difícil ou mesmo impossível.
komposter:

Falta pelo menos uma pausa:

Melhor ainda, separar realmente topo e fundo, e parar imediatamente após um controlo mal sucedido.

Mais uma vez, a separação entre o topo e a base resulta em dois passes para. O que duplica o tempo de pesquisa. A separação por si só não proporciona qualquer ganho de desempenho sem a utilização de multithreading, especialmente para pequenos n.

Ainda assim, OCL (ou paralelismo no sentido geral) não é uma optimização algorítmica, mas sim uma optimização técnica.

Duvido que no seu caso haja necessidade de paralelizar a solução O(N)-variante mais rápida para o problema.

C-4:
Ele irá.

Sem yada yada? Mostre-me.

Portanto, boa sorte. Discutir a optimização de um algoritmo com complexidade que depende linearmente do valor de um parâmetro é provavelmente algo que não tem nada a fazer.

TheXpert:

Sem yada yada? Mostre-me.

Seja como for, boa sorte. Discutir a optimização de um algoritmo com complexidade linearmente dependente do valor de um parâmetro - não tem realmente nada a fazer.

OK, vou terminar de completar o algoritmo e afixar os resultados do paralelismo no estúdio.

hrenfx:

Ainda assim, OCL (ou paralelismo no sentido geral) não é uma optimização algorítmica - é mais uma optimização técnica.

Duvido que haja necessidade de paralelizar a solução O(N)-variante mais rápida no seu caso.

Como posso dizer? Qualquer paralelização é sempre uma complicação grave dos algoritmos. Além disso, se não paralelizar um algoritmo com uma dependência linear da quantidade de dados, o que mais se pode paralelizar?

Em suma, vou reescrever o algoritmo e ver o que ele traz.

C-4:
Mais uma vez, a separação das partes superiores e inferiores resulta em dois passes para. Isto duplica o tempo de pesquisa. A separação por si só não proporciona ganho de desempenho sem a utilização de multithreading, especialmente para pequenos n.

Como pode ter tanta certeza?

O meu cheque mostra o contrário:

01:29:25 SpeedTest EURUSD,M15 entradas: Interações=10000; pperiod=10;

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

01:30:46 SpeedTest EURUSD,M15: Função original: 81.558 seg, extrema: 131 / 121

01:31:10 SpeedTest EURUSD,M15: Com a minha edição (pausa): 23.291 seg, extrema: 131 / 121

01:31:27 SpeedTest EURUSD,M15: Com o meu intervalo (pausa): 17.565 seg, extrema: 131 / 121

Em anexo está um guião mq4.

Arquivos anexados:
SpeedTest.mq4  4 kb

Mais um teste para completar o quadro:

01:38:56 SpeedTest EURUSD,M1 entradas: Interações=1000; pperiod=100;

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

01:50:19 SpeedTest EURUSD,M1: Função original: 683.565 seg, extrema: 121 / 127

01:50:54 SpeedTest EURUSD,M1: Com a minha edição (pausa): 34.383 seg, extrema: 121 / 127

01:51:16 SpeedTest EURUSD,M1: Com o meu intervalo (pausa): 22.714 seg, extrema: 121 / 127

komposter:
C.T.D. escreveu exactamente isso no seu primeiro post.
12345678910
Novo comentário