Ottimizzazione degli algoritmi. - pagina 5

[TheXpert]

Mathemat:
In linea di principio, sì. Ma ancora non più di O(n).

Non meno :) con una buona immaginazione si può fare una dipendenza esponenziale:)

[Vasiliy Sokolov]

Mathemat:

Beh, questo non è un problema di ottimizzazione.

Trovare un estremo è sempre un problema di ordine O(n), dove n è il numero di dati. Come si possa peggiorare questa asintotica - non ne ho idea.

L'algoritmo più semplice è ArraySort(), che è integrato abbastanza velocemente, ma è probabilmente ridondante per questo problema.

Si potrebbe inventare qualcosa di ricorsivo che sarebbe più veloce.

Quanto tempo ci vuole per trovare il minimo e per quante barre?

Ho dato le statistiche nel primo post. Il calcolo per 1.000.000 di barre aumenta aritmeticamente all'aumentare del periodo. Così per il periodo 3, il calcolo richiede 0,54 secondi, per il periodo 51 richiede 0,94 secondi, e per il periodo 99 richiede 1,59 secondi.

Questo è peggio perché usa il ciclo nel ciclo, che è un errore. Così, per il periodo 3 il numero di iterazioni sarà 1 000 000 * (3-1/2) = 1 000 000, mentre per il periodo 99 sarà 1 000 000 * (99-1)/2 = 49 000 000! Quindi abbiamo bisogno di riscrivere l'algoritmo in modo tale che il numero di iterazioni non aumenti qualitativamente con l'aumentare del periodo - questo è un puro problema di ottimizzazione. Questo è quello che sto facendo ora. Finora ho scritto questo:

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

Per cercare il minimo userò la funzione corrispondente Down() che gira nel thread parallelo. Quando entrambe le funzioni terminano, i loro risultati saranno scritti nella lista generale. Va più o meno così.

[Sceptic Philozoff]

C-4: Ho dato le statistiche nel primo post. Il calcolo per 1.000.000 di barre cresce aritmeticamente all'aumentare del periodo. Così per il periodo 3, il calcolo richiede 0,54 secondi, per il periodo 51 0,94 secondi, e per il periodo 99 è già 1,59 secondi.

Ecco, ti sei sbagliato. Non è la somma di una progressione richmetica, C-4. La somma cresce quadraticamente.

OCL non è ambiguo.

[Vasiliy Sokolov]

Mathemat:

L'algoritmo più semplice è ArraySort(), abbastanza veloce, qualcosa intorno a O(n * ln( n ) ), ma probabilmente è ridondante per questo problema.

Pensiero. Qualsiasi ordinamento sarà intrinsecamente più lento che passare attraverso l'intero array via for. Per dare un'iterazione, mentre arraysort nel migliore dei casi ordina i valori in ogni sottofinestra n, il che significa decine di azioni.

No, si dovrebbe comunque puntare a che il numero totale di iterazioni sia qualitativamente uguale al numero di barre.

[Vasiliy Sokolov]

Mathemat:

Ecco, ti sei sbagliato. Non è la somma di una progressione richmetica, C-4. La somma cresce quadraticamente.

OCL non è ambiguo.

Se è quadratico, è ancora peggio. Senza multithreading, per come la vedo io, non c'è modo di aggirarlo.

[hrenfx]

La condizione per una tale ricerca dell'estremo è strana a dir poco... Ma anche così, è estremamente irragionevole usare un metodo di ricerca a forza bruta.

Il classico ZigZag a un solo passaggio con ExtDepth = n viene subito in mente con un leggero adattamento alla condizione attuale. OCL è inutile al 100% qui.

[TheXpert]

Voi ragazzi siete in fiamme. Tutti e tre.

[Vasiliy Sokolov]

hrenfx:

La condizione per una tale ricerca dell'estremo è strana a dir poco... Ma anche così, è estremamente irragionevole usare un metodo di ricerca a forza bruta.

Un classico ZigZag a un solo passaggio con ExtDepth = n viene subito in mente con un leggero adattamento alla condizione attuale. OCL è inutile al 100% qui.

Beh, in linea di principio ho bisogno di questi estremi per uno zig-zag. Allora quali algoritmi è meglio usare? Esiste un codice più efficiente di quello che ho citato nella seconda versione?

[hrenfx]

Controlla le ZigZags a passaggio singolo in CodeBase MT4 - O(N).

[Sceptic Philozoff]

TheXpert: Voi ragazzi siete in fiamme. Tutti e tre.

Perché? O(n) sarà ancora lì, non importa come lo guardi.

Se tutto il resto fallisce, provate OCL. Non ci sono altri modi senza perversioni di tipo dll in 5.