Quando fa 'ottimizzare il codice' == 'strutturare i dati'?

9

Un recente articolo di ycombinator elenca un commento con i principi di un grande programmatore.

#7. Good programmer: I optimize code. Better programmer: I structure data. Best programmer: What's the difference?

Riconoscere concetti soggettivi e controversi: qualcuno ha una posizione su cosa significa? Lo so, ma mi piacerebbe modificare questa domanda in un secondo momento, con i miei pensieri, in modo da non predisporre le risposte.

    
posta New Alexandria 08.10.2012 - 16:35
fonte

8 risposte

16

Nove volte su dieci, quando si strutturano bene il codice / i modelli, l'ottimizzazione diventa ovvia. Quante volte hai visto un nido di calabroni e l'hai trovato totalmente subottimale, dove alla sua ristrutturazione, molti licenziamenti sono diventati estremamente evidenti.

A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away. - Antoine de Saint-Exupery

Un sistema ben strutturato sarà di natura minima e, vista la sua natura minimale, sarà ottimizzato perché il poco che c'è da collegare direttamente a quanto poco fa per raggiungere il suo obiettivo.

Modifica: Per spiegare il punto che gli altri hanno portato via da questo, è anche completamente accurato vedere la dichiarazione come l'identificazione della relazione tra codice e dati. Tale relazione è quindi: se si modifica la struttura dei dati, sarà necessario modificare il codice per rispettare la struttura modificata. Se desideri ottimizzare il tuo codice, è probabile che dovrai modificare la struttura dei tuoi dati per rendere il tuo codice capace di gestire i dati in modo più ottimale.

Detto questo, c'è una possibilità totalmente separata a cui è stato eluso qui, e questo sarebbe che questo individuo che ha relazioni con YCombinator potrebbe riferirsi a dati di codice AS nella tradizione LISP di omoiconicity. È un tratto supporre che questo sia il significato nella mia mente, ma è YCombinator, quindi non escluderei che la citazione stia semplicemente dicendo che i LISPers sono i "migliori programmatori".

    
risposta data 08.10.2012 - 16:39
fonte
4

Penso che l'autore stia suggerendo che qualsiasi ristrutturazione dei dati porta a una ristrutturazione del codice. Pertanto, la ristrutturazione dei dati con l'obiettivo di ottimizzare il tuo sistema ti costringerà a ottimizzare anche il tuo codice, suggerendo "qual è la differenza?" risposta.

Si noti che un "programmatore super-eccellente" può rispondere a "qual è la differenza?" ci sono alcune differenze: una volta che ci si avventura nell'ottimizzazione per un uso migliore della cache della CPU, si può mantenere lo stesso layout delle strutture dati, ma cambiare l'ordine in cui si accede a loro può fare una grande quantità di differenza.

    
risposta data 08.10.2012 - 16:50
fonte
3

Considera l'esempio più ovvio di questo: "la ricerca dei dati dell'utente è troppo lenta!"

Se i dati dell'utente non sono indicizzati o almeno ordinati, la ristrutturazione dei dati produrrà rapidamente un aumento delle prestazioni del codice. Se i dati sono strutturati correttamente e stai semplicemente iterando attraverso la raccolta (piuttosto che usare gli indici o fare qualcosa come una ricerca binaria), la modifica del codice produce un aumento delle prestazioni del codice.

I programmatori sono risolutori di problemi. Mentre è utile distinguere tra algoritmi e strutture dati, non possono spesso esistere in isolamento. I migliori programmatori lo sanno e non si isolano inutilmente.

    
risposta data 08.10.2012 - 17:05
fonte
1

Non sono d'accordo con la dichiarazione di cui sopra, almeno senza spiegazione. Vedo la codifica è l'attività che comporta l'utilizzo di alcune strutture di dati. Le strutture dati influenzerebbero in genere la codifica. Quindi c'è una differenza tra i due a mio parere.

Penso che l'autore avrebbe dovuto scrivere l'ultima parte come "Miglior programmatore: ottimizzo entrambi."

C'è un grande libro (almeno lo era quando pubblicato) chiamato: Algoritmi + Strutture dati = Programmi .

    
risposta data 08.10.2012 - 17:00
fonte
0

L'ottimizzazione del codice può a volte migliorare la velocità di un fattore due, e occasionalmente di un fattore dieci o anche venti, ma questo è tutto. Può sembrare molto, e se il 75% del tempo di esecuzione di un programma viene speso in una routine a cinque righe la cui velocità potrebbe facilmente essere raddoppiata, potrebbe essere utile effettuare una tale ottimizzazione. D'altra parte, la selezione delle strutture dati può influenzare la velocità di esecuzione di molti ordini di grandezza. Un moderno processore multi-thread ottimizzato per ottimizzare il codice ottimizzato per cercare dati per chiave in un elenco lineare lineare di 10.000.000 elementi archiviato nella RAM sarebbe più lento di un processore molto più lento che esegue una tabella hash nidificata piuttosto semplice. Infatti, se uno avesse i dati disposti correttamente, anche un computer del 1980 che recuperava i dati da un disco rigido potrebbe battere la CPU moderna usando la struttura dati inferiore.

Detto questo, progettare strutture dati efficienti richiede spesso compromessi più complessi rispetto all'ottimizzazione del codice. Ad esempio, in molti casi le strutture dati che consentono l'accesso ai dati in modo più efficiente sono meno efficienti da aggiornare (a volte per ordine di grandezza) rispetto a quelle che consentono aggiornamenti rapidi e quelle che consentono gli aggiornamenti più rapidi possono consentire l'accesso più lento. Inoltre, in molti casi, le strutture dati che sono ottimali per i grandi insiemi di dati possono essere comparativamente inefficienti con quelle piccole. Un buon programmatore dovrebbe sforzarsi di bilanciare quei fattori concorrenti con la quantità di tempo necessario per programmare e mantenere varie strutture di dati, ed essere in grado di raggiungere un equilibrio decente tra loro.

    
risposta data 08.10.2012 - 17:16
fonte
0

Le strutture dati guidano molte cose relative alle prestazioni. Penso che possiamo esaminare i problemi a lungo ea lungo con un'idea preconcetta sulla struttura dati ideale, e in questo contesto di pensiero, persino creare prove (spesso per induzione) di ottimalità. Ad esempio, se inseriamo una lista ordinata in una matrice e valutiamo cose come il costo per inserire un elemento che potremmo decidere in media, dobbiamo spostare 1/2 della matrice per ogni inserimento. Per ogni ricerca binaria , possiamo trovare un elemento corrispondente (o non) in passaggi log n.

In alternativa, se differiamo la nostra decisione sulla struttura dei dati (evita l'ottimizzazione prematura ) e studiamo i dati che arrivano e contesto in cui lo useremo, quanto è grande, quali latenze si verificano e quali sono importanti per gli utenti, quanta memoria abbiamo rispetto alle rappresentazioni dei dati che conosciamo o possiamo elaborare.

In un'area come l'ordinamento e la ricerca, c'è molto da sapere. Davvero grandi programmatori hanno lavorato su questo a lungo. Comprendere bene questi problemi è utile, ed è una grande cosa se si conoscono più metodi rispetto a quando hai terminato la classe delle strutture di dati del sottoscambio. Alberi binari possono offrire prestazioni superiori per gli inserimenti in cambio di un maggiore utilizzo della memoria. Le tabelle hash forniscono miglioramenti ancora più grandi, ma per più memoria ancora. Un albero radix e ordinamento digitale possono apportare ulteriori miglioramenti.

La strutturazione creativa dei dati può aiutare a ridefinire un problema e aprire la porta a nuovi algoritmi che rendono le applicazioni più difficili, attività più veloci e talvolta impossibili.

    
risposta data 08.10.2012 - 18:13
fonte
0

Per articolare la mia ipotesi migliore su cosa significhi l'articolo, assumerò un sottotesto non detto (che sembra mancare nell'articolo) che qualsiasi programmatore dovrebbe capire sull'ottimizzazione:

  • l'ottimizzazione arriva solo dopo aver avviato e avviato correttamente il programma:
    • eseguilo correttamente, quindi fallo correre veloce
    • questo principio è il punto della massima di Knuth, "l'ottimizzazione prematura è la radice di tutti i mali"
  • se e quando hai stabilito che l'ottimizzazione non è prematura, devi prima misurarla in modo appropriato per determinare che cosa ha effettivamente bisogno di ottimizzazione, e ancora e ancora durante l'ottimizzazione , per dire quali effetti stanno avendo i tuoi tentativi di ottimizzazione.
    • se il tuo codice è in fase di sviluppo, il profiler è tuo amico in questo.
    • se il tuo codice viene eseguito in produzione, devi instrumentare il tuo codice e fare amicizia con il tuo sistema di registrazione.

Ora, allora: le tue misurazioni ti diranno dove nel tuo codice la macchina sta bruciando la maggior parte dei cicli. Un programmatore "buono" si concentrerà sull'ottimizzazione di quelle parti del codice, piuttosto che perdere tempo a ottimizzare le parti irrilevanti.

Tuttavia, spesso è possibile ottenere guadagni maggiori guardando al sistema nel suo insieme e trovando un modo per consentire alla macchina di fare meno lavoro. Spesso, queste modifiche richiedono la rielaborazione dell'organizzazione dei dati; quindi, un programmatore "migliore" si troverà a strutturare i dati il più delle volte.

Il "miglior programmatore" avrà un modello mentale completo di come funziona la macchina, una buona base nella progettazione dell'algoritmo e una comprensione pratica di come interagiscono. Ciò gli consente di considerare il sistema come un tutto integrato - non vedrà alcuna differenza tra l'ottimizzazione del codice e dei dati, perché li valuta a livello architettonico.

    
risposta data 09.10.2012 - 00:34
fonte
-1

Best programmer: What's the difference?

Miglior programmatore? No. Programmatore scadente. Suppongo che la parola "ottimizzazione" significhi quelle cose che i programmatori tipicamente cercano di ottimizzare, la memoria o il tempo della CPU. In questo senso, l'ottimizzazione va contro la misura di quasi tutte le altre metriche del software. Comprensibilità, manutenibilità, testabilità, ecc .: tutti prendono una piccola deriva quando l'ottimizzazione è l'obiettivo, a meno che ciò che si cerca di ottimizzare sia la comprensibilità umana, la manutenibilità, la testabilità, ecc. Per non parlare dei costi. La scrittura di un algoritmo di velocità / spazio ottimale costa molto di più in termini di tempo di sviluppo rispetto alla codifica ingenua dell'algoritmo come presentato in qualche testo o diario. Un pessimo programmatore non conosce la differenza. Uno buono. Il miglior programmatore sa come determinare esattamente ciò che deve essere ottimizzato e lo fa in modo giudizioso.

    
risposta data 08.10.2012 - 18:05
fonte