commutazione delle implementazioni dinamicamente in base alle stime del tempo di esecuzione

L'approccio standard per, ad esempio, l'ordinamento di una lista consiste nell'utilizzare quicksort per gli elenchi superiori a una soglia k e all'inserimento di ordinamento in caso contrario. Pertanto, gli elenchi partizionati che utilizzano quicksort di una certa dimensione non vengono gestiti utilizzando quicksort fino in fondo, perché l'ordinamento di inserimento batte in realtà quicksort per gli array più piccoli.

Raccomanderei di eseguire simulazioni Monte Carlo per trovare il "punto debole" in cui entrambi i metodi eseguono lo stesso per lo stesso input. Quindi il tuo metodo di wrapper controlla semplicemente il numero di elementi e chiama il metodo appropriato che è più efficiente per quell'input in modo da garantire che tu stia utilizzando sempre il metodo migliore.

Per fare un esempio, supponendo di eseguire simulazioni Monte Carlo e di ricevere i seguenti risultati:

n       method 1   method 2
10      0.013 s    0.001 s
100     0.130 s    0.130 s
1000    1.130 s    5.245 s
10000   11.30 s    109.313 s

Come possiamo vedere da questo, il metodo 2 supera il metodo 1, ma solo fino a quando non si raggiungono 100 voci. Oltre 100 voci, il metodo 1 supera il metodo 2.

Quindi il tuo metodo di ottimizzazione dovrebbe essere:

function bestMethod(array) 
    if(array.length < 100)
        method2(array)
    else 
        method1(array)

Se dovessi eseguire simulazioni Monte Carlo sul nuovo metodo bestMethod, otterrai qualcosa di simile alla seguente tabella:

n       best method  method 1   method 2
10      0.001 s      0.013 s    0.001 s
100     0.130 s      0.130 s    0.130 s
1000    1.130 s      1.130 s    5.245 s
10000   11.30 s      11.30 s    109.3 s

Ovviamente le prestazioni potrebbero cambiare in base all'input, quindi ti incoraggio a utilizzare input molto simili al tipo di input che riceverai nel tuo programma per eseguire le simulazioni Monte Carlo, e, se dovessi sospettare che le prestazioni variano notevolmente in base all'input, è necessario testare con più input in quanto potrebbe avere un impatto sul valore di soglia.

Il codice stesso non farebbe analisi, né avrebbe bisogno di conservare informazioni riguardanti le prestazioni, solo un rapido controllo sul numero di elementi o altre metriche, purché sia veloce da controllare.

E nel peggiore dei casi in cui le prestazioni variano enormemente in base all'input senza una chiara indicazione a priori, stai guardando qualcosa che potrebbe essere meglio gestito utilizzando algoritmi di apprendimento automatico, ma sospetto che non sia il tuo caso.

Questa è un'idea interessante, ma in gran parte riecheggia la risposta di Neil, penso che sia necessario indagare perché una funzione è più veloce dell'altra e viceversa per determinati tipi di input, idealmente con un profiler in mano.

L'idea di provare a fare in modo che il codice generi una stima temporale al volo della velocità con cui entrambe le funzioni potrebbero essere eseguite per determinare quale usare è accurato ma anche abbastanza indicativo che trarrai vantaggio da una migliore comprensione del perché uno supera l'altro in alcuni casi, in modo da poter scegliere un mezzo più semplice per scegliere tra queste due funzioni se si intende conservare e consentire l'uso di entrambi (come la dimensione dei dati da elaborare come nell'esempio di Neil sull'uso della dimensione dell'elenco per l'introsorting). ).

Personalmente secondo la mia sensibilità, mi siedo per un po 'con la funzione che sembra essere più veloce in più casi e profilo e sintonizzarsi per un bel po', sviluppando una maggiore comprensione delle caratteristiche delle prestazioni. Si potrebbe anche finire con una funzione che finisce per essere più veloce in tutti i casi dopo aver affrontato alcuni hotspot. Altrimenti, dovresti per lo meno avere una comprensione superiore del perché si comporta meglio in certi casi e peggio in certi casi rispetto all'altro. Anche se la maggior parte del lavoro è di natura molto algoritmica, trovo spesso che la profilazione accresce anche la mia comprensione degli algoritmi e dove trascorrono più tempo e perché.

In effetti, quando sto sviluppando una nuova struttura dati che verrà utilizzata molto in loop stretti, mi piace fare lo "sviluppo profiling-driven", come l'equivalente analogico dello sviluppo basato sui test, ma fuso con TDD dal momento che sto descrivendo i test che sto scrivendo contro le strutture di dati man mano che la struttura dei dati viene messa a punto. Spesso così tante nuove idee di miglioramento arrivano attraverso questo processo, e la struttura dei dati e la sua rappresentazione dei dati vengono plasmati e rimodellati dalle scoperte lungo la strada fino a quando posso chiamarla e sentirmi fiduciosamente come se avessi questa struttura di dati tosta ora che posso appoggiarmi alla combinazione del test unitario, dei benchmark e di tutto il profilo che ho fatto per guidare il suo sviluppo. È la cosa più divertente del mondo per me e vorrei poterlo fare tutto il giorno invece di lavorare su GUI e roba noiosa del genere. Ad ogni modo, sto divagando, ma la profilazione del tuo codice potrebbe farti fare un ulteriore passo avanti.