Quanto è importante per un programmatore sapere come implementare un algoritmo QuickSort / MergeSort dalla memoria? [chiuso]

57

Stavo rivedendo i miei appunti e sono incappato nell'implementazione di diversi algoritmi di ordinamento.

Mentre tentavo di dare un senso all'implementazione di QuickSort e MergeSort, mi è venuto in mente che sebbene io stia programmando per vivere e mi considero decente in quello che faccio, non ho né la memoria fotografica né la capacità mentale di implementare quegli algoritmi senza fare affidamento sui miei appunti. Tutto ciò che ricordo è che alcuni di questi algoritmi sono stabili e altri no. Alcuni richiedono O (nlog (n)) o O (n ^ 2) per il completamento. Alcuni usano più memoria di altri ...

Mi sento come se non mi meritassi questo tipo di lavoro se non fosse perché la mia posizione non richiede che io usi un algoritmo di ordinamento diverso da quelli che si trovano nelle API standard. Voglio dire, quanti di voi hanno una posizione di programmazione in cui è effettivamente necessario ricordare o inventarsi questo genere di cose da soli?

    
posta John Smith 07.10.2012 - 00:38
fonte

7 risposte

117

Chiediamo ad Albert e vediamo cosa ha da dire sull'argomento:

“I don't need to know everything, I just need to know where to find it, when I need it”

-- Albert Einstein, paraphrased

Amen, fratello Albert, Amen.

Una volta che hai fatto una buona analisi degli algoritmi essenziali in una particolare disciplina (ordina, cerca, qualunque cosa), puoi dimenticare i dettagli di implementazione finché non hai effettivamente bisogno dell'algo, nel qual caso vai a cercarlo o usare una lib preesistente. 25 anni fa ho costruito un sistema di ricerca importante usando B * -trees, ma oggi avrei bisogno di RTFM per poterli usare bene.

    
risposta data 07.10.2012 - 04:21
fonte
48
  1. Non è davvero una questione di memorizzazione. È una questione di comprensione profonda di classi generali di algoritmi come divide et impera. Se capisci veramente dividi e conquista, non hai bisogno di memorizzare quicksort. È possibile ri-derivare sul posto, se necessario. Inoltre, il vero guadagno non è nemmeno in grado di ri-derivare quicksort da solo, è che puoi riconoscere quando un nuovo problema è suscettibile di una soluzione divide et impera.

  2. Non tutti i lavori di programmazione sono uguali. Alcuni lavori hanno bisogno di una profonda conoscenza degli algoritmi, alcuni hanno bisogno di persone che capiscono la teoria dei tipi, e alcuni hanno solo bisogno di gente che possa raschiare i dati da un modulo web e spostarli in un database. Alcuni lavori richiedono anche tutte quelle abilità contemporaneamente. A che tipo di lavoro vuoi lavorare?

risposta data 07.10.2012 - 03:16
fonte
10

Penso che l'unica volta che devi ricordare tutto è quando fai domanda per un posto di lavoro quando devi trovare le risposte sul posto e non avere risorse esterne.

I miei colleghi hanno riscritto quicksort e quant'altro, ma continuo a dire loro di tornare a utilizzare le funzioni di ordinamento incorporate che sono nella lingua. So che, a seconda del tipo di progetti su cui lavoriamo, dobbiamo ricordare altri algoritmi poiché solitamente non sono inclusi nelle librerie standard, ma l'ordinamento non è uno di quelli che si presentano dato che di solito è incorporato nella lingua.

Quando però abbiamo bisogno di ricordare quegli algoritmi, di solito ci rivolgiamo a google o a un libro, e di solito non è alla ricerca di un'implementazione specifica, ma quale sarebbe la migliore implementazione per il nostro problema.

    
risposta data 07.10.2012 - 01:02
fonte
6

Basta ricordare quale algoritmo è utile in quali scenari, sarebbe più che sufficiente per aiutarti durante il tuo lavoro. In effetti, la maggior parte dei lavori di programmazione non richiede la memorizzazione di approccio, piuttosto sono interessati al tuo modo di riconoscere il pattern algoritmico di fronte al problema .

Di fatto, vi è abbondanza di informazioni nella maggior parte dei blog / articoli di programmazione sugli argomenti dell'algoritmo. Pertanto, la memorizzazione dell'esatta implementazione non ha importanza. Le informazioni più preziose potrebbero essere l'idea di base su quale tipo di algoritmo è disponibile e quali problemi specifici sono utili a risolvere . Cercare un'implementazione esatta una volta che sai cosa stai cercando è piuttosto veloce.

In sintesi, è sempre meglio sapere cosa cerchi e dove sono i riferimenti - che ti guideranno alla fonte.

    
risposta data 07.10.2012 - 00:57
fonte
5

L'esatta implementazione non è molto importante. Ma il principio alla base di mergesort / quicksort - ricorsione, partizionamento, ecc. È molto semplice e ogni programmatore dovrebbe capirlo. Questi algoritmi sono in realtà molto semplici da descrivere a parole una volta compreso.

Non è davvero un problema se si può cercare o se si può google, è se il programmatore capisce queste tecniche di risoluzione dei problemi e in grado di applicare ad altre situazioni.

    
risposta data 12.10.2012 - 18:25
fonte
3

Sono di due menti su questo argomento. Conosco molti programmatori che non sanno cosa sia un algoritmo di ordinamento, ma fanno il loro lavoro abbastanza bene. Credo anche nella comprensione dei principi per comprendere veramente il dominio.

È difficile per me avere una risposta imparziale su questo argomento poiché ho programmato per così tanto tempo che probabilmente ho dimenticato più algoritmi che attualmente conosco - ma conosco ancora gli ordinamenti menzionati in questa domanda. Penso che i leader del pensiero in Agile (ad esempio Ron Jeffries, Alistair Cockburn) abbiano alcune buone idee vicino a questa idea (ad esempio Shu-Ha-Ri).

In sintesi a questa risposta sconclusionata: usa decisamente l'API (NIH è un segno di immaturità dello sviluppatore), ma comprendi sempre i principi di base. Spero che questo aiuti.

    
risposta data 07.10.2012 - 17:27
fonte
2

L'ordinamento e la ricerca sono incredibilmente importanti, che tu sia un fan di Donald Knuth o che desideri diventare il prossimo Larry Page. A seconda del business in cui ti trovi e del livello di competizione che puoi comandare tra i tuoi candidati, ti consiglio di includere alcuni dei seguenti concetti nell'intervista.

L'ordinamento

  • Schizzo di un qualche tipo di algoritmo di ordinamento.
  • Elenca alcuni esempi di algoritmi di ordinamento.
  • Confronta / contrasto due tipi con caratteristiche di rendimento diverse.
  • Se non menzionano l'uso della memoria, chiedi informazioni.

Ricerca

  • Indica il numero di algoritmi di ricerca che puoi.
  • Confronta / contrasto due algoritmi di ricerca.
  • Disegna qualsiasi ricerca diversa dalla ricerca lineare.

Alcuni potrebbero dire che richiedere il codice per questi algoritmi è eccessivo se il lavoro non si svolge su un'isola deserta senza connessione a Internet. Un'altra considerazione è che se hai 30 minuti e vuoi chiedere altro, per molti candidati, implementare l'ordinamento potrebbe richiedere una grossa fetta del tuo tempo.

    
risposta data 07.10.2012 - 04:35
fonte

Leggi altre domande sui tag