Cosa è meglio per le prestazioni scrivere il ciclo come lineare ad es. per, mentre o scrivilo come ricorsione?
Dipende da molti fattori.
Per la maggior parte delle applicazioni, qualsiasi cosa sia più facile per un essere umano per capire è la scelta giusta.
Molto probabilmente dipende dalla lingua che stai usando. L'unico vero modo per rispondere è quello di limitarlo semplicemente.
Per quanto riguarda la ricorsione, a meno che tu non stia attento alla ricorsione in coda, non solo devi prendere in considerazione il tempo nelle metriche sul rendimento ma anche nella memoria.
In molte lingue / implementazioni linguistiche, tutte le differenze sono praticamente eliminate dal compilatore. In tutti gli altri, la differenza è ridicola e assolutamente non vale la pena di fare dei compromessi a livello di codice sorgente - scegliere qualunque cosa sia più leggibile e pulita, nessuno noterà alcuna differenza. (A meno che il codice in questione non sia il ciclo più interno di un programma critico per le prestazioni.) Ma tale software non dovrebbe essere scritto da voi o da chiunque faccia domande del genere anziché (1) individuare dove ottimizzare e (2) come efficaci varie "ottimizzazioni" sono!)
Un'eccezione è quella ricorsione molto profonda (la profondità che si raggiunge solo quando si recita una volta per elemento e l'argomento è un'enorme raccolta - l'attraversamento di un albero ecc. è completamente trovato e, di fatto, risolto meglio mediante ricorsione) di solito (eccetto in un'implementazione linguistica relativamente intelligente, se si tratta di una chiamata a coda ) genera overflow dello stack, quindi se è un vero pericolo, dovrai eliminare manualmente la ricorsione (tutti gli algoritmi ricorsivi possono essere scritti in modo iterativo e viceversa).
Come affermato altrove - la maggior parte delle volte la leggibilità conta più che affettare e tagliare le prestazioni all'ennesima potenza. Se vuoi qualche pratica regola del pollice ti suggerirei questo:
Utilizza un ciclo FOR () {} quando:
Utilizza un ciclo WHILE () {} quando:
Utilizza un ciclo DO {} WHILE () quando:
Usa RECURSION quando:
La maggior parte delle strutture di looping (FOR o WHILE) sono implementate dietro le quinte come "confronta e dirama", quindi il costo sarà lo stesso. Le differenze da considerare sono:
Ciclo FOR:
Ciclo WHILE:
DO WHILE () loop:
Ricorsione:
Souce: Wikipedia sulla ricorsione La risposta dipende dalla lingua. Per le lingue che sono orientate verso l'iterazione come C e Java, la ricorsione è più lenta a causa del sovraccarico delle chiamate di funzione. Per le lingue funzionali, che in genere hanno costi generali più bassi, la differenza è spesso trascurabile.
Un buon consiglio che ho letto è quello di provare entrambi e quindi testare ciascuno per le prestazioni (se le prestazioni sono importanti).
Nella mia esperienza, più che il problema delle funzioni iterative e ricorsive, i maggiori punti di strozzatura tendono ad essere l'accesso alle risorse esterne, cioè database, connessioni di rete, I / O su disco o schermo, che sono candidati molto migliori di qualsiasi loop per l'ottimizzazione. A volte succede che i tuoi loop passino molto tempo ad accedere a risorse esterne, e se questo è il caso, puoi ottimizzarlo abbastanza pesantemente. Molte operazioni possono essere srotolate in attività parallele che è possibile eseguire al termine dell'accesso alla risorsa.
Se stai facendo un sacco di calcoli matematici, forse dovresti considerare di fare in modo che il tuo codice faccia un mix di operazioni in virgola mobile e Integer (un buon compilatore / processore garantirà l'esecuzione simultanea sulle rispettive unità di elaborazione) o la sostituzione di costosi operazioni come sqrt con altri ops, o approssimazioni / tabelle di ricerca. (Se hai sempre bisogno solo della radice quadrata di un numero intero in un intervallo fisso, o di un sin / cosine di numeri interi di gradi, questo è un ottimo candidato per una tabella di ricerca) Cerca di assicurarti di non fare matematica in serie se possibile (risultato - > operando - > risultato - > operando) per consentire alla CPU di suddividere le attività su quante più unità di elaborazione possibili.
Potresti anche prendere in considerazione la possibilità di suddividere il tuo compito in blocchi e di eseguire ogni blocco nel proprio thread o utilizzare un motore di esecuzione come Grand Central di Apple, Java Executors, ecc., che consente anche di trarre il massimo vantaggio da più core / processori . Ancora una volta, quanto mettere in ogni pezzo è una questione di profilazione per vedere quale sia la migliore dimensione del blocco per il tuo particolare compito.
Infine, potresti considerare che il tuo approccio è semplicemente sbagliato. Di solito c'è più di un modo per fare un compito particolare, e non dovresti essere troppo preso da un qualsiasi modo di farlo, anche se sembra la soluzione più "elegante" o "perfetta". Se solo i supercomputer IBM sono in grado di risolvere il problema in un ragionevole periodo di tempo, nessuna ottimizzazione del ciclo può essere d'aiuto e dovresti provare un approccio diverso.
IE: la grafica tracciata di Ray è bellissima, ma se stai programmando un gioco, utilizza invece la grafica raster con accelerazione hardware.
Mi ricordo di quando ero a scuola quando stavo imparando Java, io e un amico avevamo un problema su quale ciclo era migliore, while o for . Ho scritto un programma per misurare quale era più veloce e uno di loro funziona più velocemente dell'altro. Non ricordo quale fosse, ma ho iniziato ad usare quel loop tutto il tempo anche se aveva più senso usare l'altro. In seguito mi sono reso conto che non c'erano differenze misurabili tra i due e che i risultati che avevo visto erano piuttosto casuali. Dopo di ciò ho iniziato ad usare il loop che logicamente aveva più senso.
All'epoca non conoscevo nemmeno la ricorsione, ma dal momento che la ricorsione consuma memoria e non solo i cicli della CPU, i loop sono generalmente preferibili dal punto di vista delle prestazioni. Tuttavia, se un problema viene risolto in modo più elegante con la ricorsione, utilizzo sempre la ricorsione.
Per riassumere:
For the vast majority of applications, whatever is easier for a human being to understand is the proper choice.
Citazione dalla risposta più votata. So che non ho aggiunto alcuna nuova informazione pertinente alla domanda. Volevo solo raccontare questa storia e ricordare il liceo. Per favore non mi sottovalutare per aver sentito il bisogno di condividere la mia storia da pazzi.
La ricorsione è generalmente più lenta. La manipolazione dello stack sulle chiamate è molto più brutta / più lenta dei salti che vengono eseguiti come parte di un ciclo. È solo lo stato del design attuale del processore. Tuttavia, alcuni compilatori ottimizzeranno le chiamate in salti comunque. Potresti scoprire che lo stesso codice esatto è generato in entrambi i modi ...: -)
Cerca sempre il tuo codice per scoprirlo di sicuro.
Dipende da quanto è intelligente il compilatore. In teoria non vi è alcuna differenza tra le funzioni ricorsive e i loop tail, quindi il compilatore probabilmente convertirà comunque la funzione ricorsiva della coda in un loop. In caso di funzioni ricorsive più complicate è probabilmente una buona idea riscriverle come loop se possibile e se no allora è probabilmente una buona idea usare una sorta di tecnica di memoizzazione per mantenere la profondità dello stack il più superficiale possibile.
Mentre l'iterazione e la ricorsione sono funzionalmente equivalenti (isomorfe), le loro prestazioni variano a seconda della lingua e dell'interprete / compilatore utilizzato.
Da wiki :
In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable.
Questo può sicuramente cambiare dato a compilatori sufficientemente avanzati dato l'isomorfismo precedentemente citato.
Detto questo, la decisione di utilizzare l'iterazione o la ricorsione in un caso specifico non dovrebbe essere basata interamente (o anche principalmente) sui problemi di rendimento. Ciò porta spesso a l'ottimizzazione prematura . Altre tensioni, come la leggibilità, di solito saranno più importanti.
Anche nel caso in cui una particolare funzione iterativa o ricorsiva sia mostrata (per misura) come hotspot, non è garantito il passaggio alla ricorsione (o viceversa) per ottenere miglioramenti delle prestazioni.
Leggi altre domande sui tag recursion performance