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

[TheXpert]

Mathemat:
Em princípio, sim. Mas ainda não mais do que O(n).

Não menos :) com uma boa imaginação pode fazer uma dependência exponencial:)

[Vasiliy Sokolov]

Mathemat:

Bem, isto não é um problema de optimização.

Encontrar um extremo é sempre um problema de ordem O(n), onde n é o número de dados. Como se pode tornar esta assimptótica pior - não faço ideia.

O algoritmo mais simples é o ArraySort(), que é incorporado suficientemente rápido, mas é provavelmente redundante para este problema.

Poderia surgir algo recursivo que fosse mais rápido.

Quanto tempo demora a encontrar o mínimo e por quantos bares?

Dei as estatísticas no primeiro posto. O cálculo para 1.000.000 de barras aumenta aritmeticamente à medida que o período aumenta. Assim, para o período 3, o cálculo leva 0,54 segundos, para o período 51 leva 0,94 segundos, e para o período 99 leva 1,59 segundos.

Isto é pior porque utiliza o laço no laço, o que é um erro. Assim, para o período 3 o número de iterações será de 1 000 000 * (3-1/2) = 1 000 000, enquanto para o período 99 será de 1 000 000 * (99-1)/2 = 49 000 000! Por conseguinte, precisamos de reescrever o algoritmo de modo a que o número de iterações não aumente qualitativamente com o aumento do período - este é um puro problema de optimização. Isto é o que estou a fazer agora. Até agora, escrevi isto:

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 procurar o mínimo, a função correspondente Down() será lançada num fio paralelo. Quando ambas as funções terminam, os seus resultados serão escritos na lista geral. É algo parecido com isto.

[Sceptic Philozoff]

C-4: Dei as estatísticas no primeiro posto. O cálculo para 1.000.000 de barras cresce aritmeticamente à medida que o período aumenta. Assim, para o período 3, o cálculo leva 0,54 segundos, para o período 51 0,94 segundos, e para o período 99 já é de 1,59 segundos.

Aí está, percebeu mal. Não é a soma de uma progressão rica, C-4. A soma cresce quadraticamente.

A OCL é inequívoca.

[Vasiliy Sokolov]

Mathemat:

O algoritmo mais simples é o ArraySort(), incorporado suficientemente rápido, algo em torno de O(n * ln( n ) ), mas é provavelmente redundante para este problema.

Pensamento. Qualquer triagem será inerentemente mais lenta do que percorrer todo o conjunto. Pois dá uma iteração, enquanto que as arraysort na melhor das hipóteses ordenará os valores em cada subjanela n, o que por si só significará dezenas de acções.

Não, deve ainda visar que o número total de iterações seja qualitativamente o mesmo que o número de barras.

[Vasiliy Sokolov]

Mathemat:

Aí está, percebeu mal. Não é a soma de uma progressão rica, C-4. A soma cresce quadraticamente.

A OCL é inequívoca.

Se é quadrático, é ainda pior. Sem multithreading, como eu entendo, não há como contorná-lo.

[hrenfx]

A condição para uma busca tão extrema é, no mínimo, estranha. Mas mesmo assim, é extremamente irrazoável usar um método de busca por força bruta.

Um ZigZag clássico de uma passagem com ExtDepth = n vem imediatamente à mente com um ligeiro ajustamento à condição actual. O OCL é 100% desnecessário aqui.

[TheXpert]

Vocês estão a arder. Vocês os três.

[Vasiliy Sokolov]

hrenfx:

A condição para uma busca tão extrema é, no mínimo, estranha. Mas mesmo assim, é extremamente irrazoável usar um método de busca por força bruta.

Um ZigZag clássico de uma passagem com ExtDepth = n vem imediatamente à mente com um ligeiro ajustamento à condição actual. O OCL é 100% desnecessário aqui.

Bem, em princípio, preciso destes extremos para a la zig-zag. Então que algoritmos são melhores para usar? Existe um código mais eficiente do que aquele que citei na segunda versão?

[hrenfx]

Verifique os ZigZags de passagem única em CodeBase MT4 - O(N).

[Sceptic Philozoff]

TheXpert: Vocês estão a arder. Vocês os três.

Porquê? O(n) ainda lá estará, independentemente da forma como se olhe para ele.

Se tudo o resto falhar, tente OCL. Não há outras formas sem perversões do tipo dll em 5.