Nelle "5 regole di programmazione di Rob Pike", afferma, "Gli algoritmi di fantasia sono lenti quando n è piccolo, e n di solito è piccolo. Gli algoritmi di fantasia hanno grandi costanti." e come regola successiva afferma che "Algoritmi elaborati sono più bugge di quelli semplici, e sono molto più difficili da implementare. " Cosa intende per algoritmi "fantasiosi"? Quali sono alcuni algoritmi elaborati e cosa li rende fantasiosi?
"Fancy" in questo caso è l'opposto di "Simple".
Ad esempio, trova la ricerca del percorso. Un algoritmo "semplice" sarebbe l'algoritmo di Dijkstra . Un algoritmo "elaborato" sarebbe, ad esempio, bidirezionale Memoria semplificata-A limitata .
L'algoritmo "semplice" non sembra molto buono quando si osserva la sua complessità di runtime di tipo O grande, ma è possibile scriverlo rapidamente e ottenere il risultato desiderato.
L'algoritmo più elaborato potrebbe portare a risultati migliori nella maggior parte dei casi, ma al costo di richiedere molto più codice per farlo, il che significa molte più possibilità di nascondere gli errori. Inoltre, più l'algoritmo è complesso, più è probabile che abbia alcuni casi d'angolo esotici in cui si comporta molto peggio del previsto. Quindi, mentre potrebbe far risparmiare tempo al processore, potrebbe essere molto più costoso per quanto riguarda i tempi di sviluppo, perché tutto quel codice aggiuntivo richiede più tempo per svilupparsi e ancora più tempo per essere mantenuto.
Come regola generale, devi prima implementare un algoritmo "semplice" e solo quando si scopre che non è abbastanza veloce, cerca un'implementazione più "appassionata".
Modifica: un altro esempio in cui l'argomento "dimensione di n" si applica più sarebbe costituito da generatori di numeri pseudocasuali. Un "semplice" registro di spostamento lineare delle risposte ha uno stato interno uguale alla dimensione dell'output, mentre il più lontano Mersenne Twister ha uno stato interno di 2.5Kb. Quando hai bisogno solo di una breve serie di numeri casuali, il costo di inizializzare lo stato interno della MT supererà di gran lunga i vantaggi che ha.
Quando confronti due algoritmi in cui uno ha un tempo di esecuzione di c * log(n) e l'altro un tempo di esecuzione di c * n² , tieni presente che stai guardando diversi valori di c . Dato un set di dati molto grande, il primo algoritmo si interromperà anche alla fine, anche se il suo c è più grande di diversi ordini di grandezza. Ma per valori più piccoli di n un valore inferiore di c potrebbe essere più importante.
Leggi altre domande sui tag algorithms