Un buon programmatore dovrebbe rendersi conto che un grande algoritmo è già stato scritto per risolvere un problema e non perde tempo a reinventare le ruote.

Dubito che Dijkstra abbia elaborato l'algoritmo del percorso più breve in poche ore, quindi sembra uno standard veramente alto da usare per determinare se qualcuno è un "buon programmatore"

Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?

In primo luogo, potresti confondere la programmazione con l'informatica teorica. Un programmatore fantastico ha bisogno di una buona conoscenza dell'informatica, ma non ha bisogno di essere fantastico. Dijkstra è stato fantastico in informatica.

In secondo luogo, mi aspetterei che chiunque abbia una buona comprensione dei grafici per sviluppare il proprio traversal grafico dopo un po 'di pensiero. Ma non un algoritmo di percorso più breve. L'algoritmo di Dijkstra in particolare è altamente sofisticato. Una volta che lo capisci, è incredibilmente ovvio. Ma la maggior parte delle cose sono così.

Probabilmente potresti derivare qualche tipo dell'algoritmo del percorso più breve dopo aver provato alcune cose e aver dato l'idea un po 'di tempo. Ma non essere deluso se ciò richiede ore o addirittura pochi giorni. Questo è completamente OK e normale.

(Caveat: beh, dovresti essere in grado di forzare il problema in poche ore al massimo, ma questo non darebbe un algoritmo funzionante anche su grafici abbastanza piccoli.)

Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?

Sicuramente non realistico. Le persone non si limitano a "inventare" algoritmi in poche ore. Ci vuole un grande sforzo e lavoro. Per citare questo blog:

In Programming Pearls, Bentley, quoting Donald Knuth, says "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962."

e la versione di Bentley era anche problematica quando implementata per set di grandi dimensioni.

Inoltre, un buon programmatore sa quali strumenti sono a sua disposizione e quando utilizzare tali strumenti. Non ottieni punti extra per originalità o cose diverse, vuoi che funzioni e funzioni bene.

È molto improbabile che tu possa trovare una soluzione migliore rispetto a quella che puoi scegliere.

Venendo fuori con un algoritmo migliore di quello considerato "il migliore" (nel tuo caso, il più breve) non è qualcosa che tutti possono fare. Probabilmente non è nemmeno possibile.

Un buon programmatore dovrebbe essere in grado di capire la logica dietro l'algoritmo e perché è migliore o peggiore (o semplicemente inadeguato per quel particolare problema) rispetto ad altri algoritmi che cercano di risolvere lo stesso problema.

(s) Dovrebbe essere anche in grado di sapere se è davvero il modo migliore per risolvere quel particolare problema.

Ad ogni modo se vuoi fare pratica, puoi comunque provare a scrivere la tua implementazione personale di un algoritmo, cercando di risolvere un problema usando la tua mente. Potrebbe non essere il migliore, ma è una buona pratica per la risoluzione dei problemi.

Questo mi ricorda qualcosa che ho letto sulla differenza tra "ingegneria del software" (quella che chiamerei programmazione) e le altre discipline ingegneristiche. Vieni a pensarci, penso che sia stato il libro originale di Design Patterns. Sono sicuro che qualcuno qui può citarla dalla cima della sua testa.

In ogni caso, il punto (sebbene non esattamente orientato verso la progettazione dell'algoritmo) era che le discipline ingegneristiche sono codificate; nessun ingegnere civile è probabile che passi il tempo a cercare di reinventare l'I-beam, ma i programmatori lo fanno sempre. Il problema (e mi rendo conto che sto semplicemente echeggiando i sentimenti di molti) è che questo comportamento è dispendioso e soggetto a errori, e serve l'ego più della soluzione.

L'informatica mi ha portato alla programmazione, e adoro entrambi. Tuttavia, sono un programmatore molto più bravo di un informatico. Non ti accuserei mai di essere incompetente perché non potresti reinventare l'algoritmo di Dijkstra in un pomeriggio. Metterei in discussione la tua competenza come programmatore se non riuscissi a riconoscere un problema che potrebbe essere risolto tramite un algoritmo del grafico del percorso più breve.

Detto questo, credo che pensare agli algoritmi e provare a progettarne e implementarne di nuovi sia (potenzialmente) divertente e (quasi) sempre istruttivo. Cerco solo di separare in modo pulito il mio tempo CS dal mio tempo di programmazione. Per i programmatori, il nostro tempo (specialmente pagato) è meglio spendere per risolvere problemi pratici invece di quelli astratti. Inoltre, il tempo di CS mi schiaccia quasi sempre la fiducia.

Non noterai le stesse cose che fanno tutti gli altri. Penso che sia solo un fatto della vita con cui dobbiamo convivere. Gran parte di ciò si riduce al tuo apprendimento passivo e ai modelli mentali che hai sviluppato come risultato di loro.

Conosco alcuni molto programmatori intelligenti e competenti che hanno dovuto insegnare la legge di DeMorgan a scuola prima che potessero farlo in modo coerente. Mi è capitato di capire l'Algoritmo di Dijkstra da solo (e devo ammettere che ne sono un po 'orgoglioso), ma mi ci è voluto molto tempo prima che potessi persino capire il tipo di bolla.

Più notoriamente, Einstein, che penseresti sarebbe un esperto di teoria dei nodi, non poteva legare i lacci delle sue scarpe fino a quando non aveva circa dieci anni.

È probabile che tu abbia inconsapevolmente reinventato molte cose che molti altri non avrebbero mai capito se non fosse stato insegnato loro esplicitamente.

Mi permetto di dissentire per ciò che la maggior parte delle risposte dice. Mentre non mi aspetto che un programmatore di qualsiasi livello sia in grado di venire da solo sull'algoritmo di Dijkstra, mi aspetterei sicuramente che potesse trovare un modo (efficiente o meno) per risolvere il problema.

Ad esempio, hai detto come commento a parte che sei riuscito a creare bubble sort da solo. So che è il più difficile degli algoritmi di ordinamento, ma hai trovato un modo per risolvere un problema, ed è quello che mi aspetto che i programmatori siano in grado di: trovare un modo per risolvere i problemi.

Naturalmente, anche investigare e trovare soluzioni fatte da altri funzionano, ma l'estremo di quel punto è un ragazzo che non pensa a se stesso e i cui programmi sono un compendio di ricerche su Google.

Penso di sembrare più duro di quanto io voglia realmente, ma il mio punto è: mi aspetto che un programmatore sia abbastanza creativo da trovare una soluzione a un problema, anche se la soluzione è buggata o disordinata.

Quindi, tornando al tuo caso, non penso che dovresti venire con l'algoritmo di Dijkstra, ma se hai la possibilità di scrivere un algoritmo per provare diverse possibilità e trovare il percorso più breve senza finire su un ciclo infinito, quindi hai la mia approvazione.

(A proposito la mia approvazione conta nello stesso ordine di importanza di un coupon gratuito per l'autolavaggio.)

Sì, dovrebbe.

Potrebbe essere l'equivalente morale di bubble sort, ma penso che un buon programmatore dovrebbe essere in grado di inventare almeno qualcosa che funzioni, per quanto inefficiente possa essere.

Inutile dire che se si presentasse un problema particolare, un buon programmatore dovrebbe prima cercare se esiste una libreria per farlo, o quali algoritmi pubblicati lo fanno e sono facili da implementare.

Naturalmente, molte attività di programmazione sono molto meno difficili e non tutti devono essere in grado di affrontare tali problemi difficili. Ma vorresti avere qualcuno con una mente del genere nel tuo team, perché potresti avere alcuni problemi specifici del progetto in cui non puoi fare affidamento su un sacco di ricerche scientifiche precedenti.

Non preoccuparti

In qualità di programmatore Perl, mi occupo di mai reinventare la ruota. Questo è il lavoro di CPAN. Se esiste un algoritmo o un modulo semplice e ben supportato, lo usiamo. Se non c'è un buon modulo, allora noi inviamo la ruota. Questa è una delle cose migliori di Perl.

Quindi quello che sto dicendo è questo:

1. Non consiglio di reinventare la ruota ma quando lo fai ...
2. Cerca di non reinventarlo completamente e ...
3. Non preoccuparti se non puoi farlo. Ecco perché abbiamo una community di programmazione: -).

La teoria dei grafi e gli algoritmi che si applicano ad essa appaiono semplici sulla superficie ma generalmente lontani da esso. Penseresti che la formazione di grafici non planari (planari) sia semplice, ad esempio, a prima vista. L'anno scorso ho approfondito questo problema (la planarità attraverso l'eliminazione dei sottografi di Kuratowski). Posso dirti, da quell'esperienza, che le persone che scrivono questi algoritmi in genere passano la durata dei loro studi di dottorato, e talvolta la ricerca viene svolta in team. E come ricercatori , questo è il loro unico obiettivo di lavoro per quel periodo di tempo. Non è ragionevole pensare che noi ingegneri sul campo possiamo aspettarci lo stesso. Come giustamente ha detto qualcun altro, è ovvio che una volta la soluzione è di fronte a voi. Sembra sempre che sia così!

Is this the kind of thing a good programmer should be able to "reinvent" in a couple of hours or am I being unrealistic?

Direi che se sei in grado di inventare un algoritmo per un problema noto come Shortest Path tutto da solo, sei un cattivo programmatore.

Significa che ignori una discreta storia sul problema del percorso più breve , passando da una O (| V | ^ 4) algoritm pubblicato nel 1955 sull'algoritmo O (E + V log V) pubblicato nel 1984 (che è l'algoritmo di Dijkstra con gli alberi di Fibonacci). Sei quasi sicuro di fare peggio degli algoritmi già ideati. Peggio ancora, ci sono buone possibilità che il tuo algoritmo abbia lacune o errori che lo rendono scorretto. Inoltre, trascorrerai quasi sicuramente molto più tempo a pensare all'algoritmo, a implementarlo e a verificarlo rispetto al tempo necessario per riutilizzare un algoritmo esistente.

Lascia la progettazione degli algoritmi ai progettisti degli algoritmi. I programmatori sono consumatori dei loro risultati. I programmatori combinano algoritmi e li mettono a lavorare su compiti reali. Un ufficiale di polizia non deve essere in grado di reinventare la legge per essere in grado di lavorare o di essere un buon ufficiale.

Ti incoraggio persino a utilizzare le implementazioni fatte da esperti piuttosto che implementare gli algoritmi per un algoritmo moderatamente complicato. È più probabile che sia corretto, è probabile che lo abbiano reso più veloce di quanto tu non voglia e ti farà risparmiare molto tempo. Questo è particolarmente vero per gli algoritmi crittografici, perché ottieni la richiesta aggiuntiva di sicurezza, che di solito solo gli esperti possono fornirti.