Approccio alla semplificazione di un algoritmo

Di solito, per me è come prima cosa scrivere codice che esegue letteralmente il calcolo o esegue alcune operazioni nell'ovvio modo non intelligente. Quindi cerco dei pattern in cui posso sostituire il codice "migliore".

Alcune bandiere rosse o "odori di codice" che vedo nel codice di esempio:

1. C'è un ciclo "for" all'interno di un altro. Se stiamo eseguendo un ciclo su i e j, forse potremmo considerare la somma i + j e la differenza i-j, con limiti appropriati. Molto utile in meccanica quantistica. Probabilmente senza senso per la tipica app di business. Ci possono essere altri modi per indicizzare le cose. Solo un semplice scambio di loop interni / esterni può portare a intuizioni anche se probabilmente non migliora di per sé la velocità.

2. Ancora, con cicli annidati. forse c'è un modo intelligente di considerare la bidimensionalità come un problema unidimensionale. Calcola qualcosa, forse. Nel tentativo di migliorare il codice, potrei avere una visione che mi consente di cambiare la matematica o l'algoritmo a livello astratto.

3. Cerca le semplificazioni matematiche ovvie o quasi ovvie. (4 + 4 + 4 + 4) ovviamente è 4 * 4 = 4 ^ 2, e quindi per il termine generale userei n ^ 2. Proprio lì, perdiamo un ciclo. Dopodiché, riconoscendo la formula come calcolatrice 1 * 2 * 3 * 4 * ... è solo n !, sceglierò di usare una tabella di ricerca. Se non stessimo aggiungendo o moltiplicando, ma usando cose più complicate come i polinomi di Legendre, il quadrato della somma delle radici, o usando dati sperimentali rumorosi invece di interi piacevoli e puliti, è necessaria una matematica più sofisticata. Ma poi lavoro in fisica e in grafica, non in business, quindi la maggior parte dei programmatori in generale potrebbe non aver bisogno di approfondire queste cose.

4. cogliere cose che vengono ripetute più e più volte. Nel tuo esempio vogliamo fare "per n volte: aggiungi n a un totale parziale" e questo potrebbe essere messo in una funzione o oggetto di scatola nera o qualcosa del genere. Supponiamo che i tuoi "4 + 4 + 4 + 4" e simili non fossero solo numeri e semplici aggiunte, ma qualcosa di più elaborato come immagini o tracce audio e filtri digitali, FFT e modulatori. Spalatelo in una scatola nera. Potrebbe non ridurre immediatamente la complessità del Big-O, ma il contenuto di quella scatola nera potrebbe sempre essere studiato e ottimizzato in seguito. Speriamo di ridurre la crescita dell'ampio O, ma in caso contrario, è probabile che troveremo qualche ottimizzazione per ridurre il coefficiente. (Ad es. Aiuta ancora a cambiare il tempo di esecuzione di un algoritmo da 8 * n ^ 3 a 4 * n ^ 3.)

A volte, mentre eseguo il lavoro di ottimizzazione e aspetto la compilazione, posso eseguire il websurf per altri tentativi di risolvere il problema e trovare una formula o un metodo di soluzione completamente diversa, qualcosa di così buono che il mio algoritmo può essere abbandonato, non importa come è implementato.

Se esistesse un algoritmo in grado di ottimizzare gli algoritmi, noi programmatori saremmo tutti senza un lavoro. Tuttavia, eseguiamo già piccole ottimizzazioni nei compilatori. Piccole ottimizzazioni possono essere apportate che non cambiano il significato previsto dell'operazione, tuttavia la nostra limitazione è precisamente quella: significato inteso. Ad esempio, se sapessimo che un numero è sempre positivo, potremmo sostituire la moltiplicazione per 2 con lo spostamento dei bit. Tuttavia, quando vengono lasciati interi con segno, anche se sono usati puramente per numeri positivi, il compilatore non può fare questo tipo di ipotesi.

Il vero trucco è capire cosa dovrebbe fare l'algoritmo. Se lo capisci, allora ti rendi conto che un algoritmo non riguarda i passi necessari ma il risultato finale. Senza questo, c'è ben poca speranza di migliorare su un algoritmo. Ad esempio, se dai al tuo amico le istruzioni per arrivare a casa tua e non vedi l'immagine più grande, potresti non rendertene conto che hai fatto fare al tuo amico un percorso più lungo per arrivarci.

Quindi come definisci il contesto di un algoritmo? Si riduce a input e output. Se puoi fare assunzioni matematiche sull'input e descrivere le ipotesi attese sull'output, allora un algoritmo è semplicemente una dimostrazione matematica nella sua forma più pura, descrivendo tutti i passi che dovresti eseguire per garantire che per l'input dato , ricevi l'output atteso.

Ogni passaggio viene trasformato in una trasformazione matematica equivalente (ad esempio, l'esecuzione di un ciclo che accumula valori potrebbe essere considerata un'operazione di somma). Una volta che hai questo, non solo puoi iniziare a dimostrare la correttezza e la correttezza, ma puoi anche semplificare in modo molto simile a come combinerai termini simili in una formula matematica.

Naturalmente tutto ciò è molto teorico e continuo, ma l'idea è che un giorno potremo scrivere compilatori che non solo possono dirti che il tuo algoritmo non funzionerà come previsto, ma anche su quale linea e come risolverlo così come eventuali ottimizzazioni che possono essere fatte per migliorare le prestazioni (questo sarebbe probabilmente fatto automaticamente).

Purtroppo non siamo ancora in questa fase, ma spero di vederlo comunque nella mia vita comunque. Spero che risponda alla tua domanda.

Mi sembra che tu abbia risposto alla tua stessa domanda.

n! è un'operazione O (n). n ^ 2 (quadrato) è O (1).

Perché non calcolare il factorial e poi squadrarlo, come implicito nel tuo commento (n!) ^ 2?

Non puoi semplicemente quadrare i nel ciclo interno, invece di moltiplicare per aggiunta?

EDIT: non è scienza missilistica.

(3 + 3 + 3)

uguali

3 * 3

Non è chiaro cosa intendi con "migliorare l'algoritmo".

ULTERIORE MODIFICA: poiché hai chiarito la domanda, permettimi di provare a rispondere. Permettetemi di fare una distinzione tra 1) algoritmi (programmi 1 pagina) e 2) programmi (1000 LOC e successivi).

1. Algoritmi. Per prima cosa familiarizzare con la ricerca, l'ordinamento e il big-O. Il modo in cui questi funzionano è l'esecuzione di una serie di punti decisionali. Ad ogni punto di decisione, chiedi qual è la probabilità di prendere ogni ramo della decisione. Se queste probabilità sono molto diseguali, i cicli vengono sprecati, molto tempo. Quindi se il tuo ciclo interno è fondamentalmente for(i=0; i<n; i++) qual è la probabilità che i<n ? Quasi sempre quasi 1, giusto? Questa è una bandiera rossa. Quindi la differenza tra, per esempio, ricerca lineare e ricerca binaria, è se le probabilità sono molto diverse o quasi la stessa in ogni punto di decisione.

2. Programmi. Questo è un argomento molto diverso. Qui il problema è che, a causa del modo in cui tu o io o qualcun altro abbiamo progettato il programma, contiene cose stupide che non indovinerai mai. Più grande è il programma, più roba stupida si nasconde in essa. Il modo per eliminarlo è esporre prima le cose più importanti. Lo faccio tramite in pausa casuale, come in questo esempio . È un terzo cugino di profilazione. Le persone ti diranno "usa un profiler", ma quello che non ti diranno è quanta velocità hanno ottenuto in quel modo. Questo esempio mostra un aumento della velocità di 43 volte. Il segreto è che dopo aver trovato e risolto il primo problema, trova e risolvi il secondo , e così via fino a quando non sei davvero in grado di trovare altro. Quello che succede è dopo aver risolto ciascun problema, i restanti diventano più grandi in percentuale, perché il tempo totale è diventato più piccolo. In questo modo, puoi continuare a spremerlo finché non lo hai ridotto al minimo assoluto.