L'algoritmo è più importante del linguaggio di programmazione?

35

Durante il contest in corso (2013) Google Code Jam , c'era un problema che richiedeva alle persone C ++ e Java oltre 200 linee di codice rispetto alle persone Python che hanno risolto lo stesso problema usando solo 40 linee di codice.

Python non è direttamente confrontabile con C ++ e Java, ma la differenza di verbosità che pensavo avrebbe forse influito sull'efficienza dell'algoritmo.

Quanto è importante conoscere il giusto algoritmo rispetto alla scelta della lingua? Un programma Python ottimamente implementato potrebbe essere implementato in C ++ o Java in un modo migliore (usando lo stesso algoritmo) e questo ha qualche relazione con la naturale verbosità di alcuni linguaggi di programmazione?

    
posta superspacemarines 25.04.2013 - 06:14
fonte

9 risposte

73

Ovviamente, se consideri questa domanda nel contesto di qualcosa come Google Code Jam, allora il pensiero algoritmico è chiaramente più importante quando devi risolvere problemi algoritmici.

Nella vita di tutti i giorni, tuttavia, bisogna considerare anche un milione di altri fattori, il che rende la domanda molto meno black vs white.

Solo un contro-esempio: se hai bisogno di altre 200 linee in Java, ma tutti nella tua azienda conoscono Java, questo non è un grosso problema. Se potessi scriverlo in 5 linee di Python o in qualsiasi altra lingua, ma tu sei l'unico in azienda a conoscere quella lingua - è un grosso problema. Infatti, un affare così grande che non ti sarà nemmeno permesso di farlo e dovresti invece scriverlo in Java.

Dal punto di vista di un artigiano, cerchiamo sempre di avvicinarci con lo strumento giusto per il lavoro, ma la parola destra qui è così complicata che si può facilmente sbagliare.

Al contrario, ho trovato il pensiero algoritmico nelle aziende quasi assente. Solo poche persone selezionate lo possiedono, mentre il joe medio spesso ha già difficoltà a stimare la complessità di runtime di loop, ricerche, ecc.

In termini di competizioni algoritmiche, tuttavia, la mia esperienza personale di competere con loro per diversi anni, mi dice chiaramente che dovresti attenersi a una lingua. La velocità è un fattore importante e semplicemente non puoi permetterti di sprecare tempo sui tuoi strumenti, quando dovresti dedicarlo a risolvere i problemi entro il limite di tempo. Considera anche che scrivere 200 righe di codice Java senza pensare è ancora molto più veloce della realizzazione artigianale di 50 linee di complicato codice Python che richiedono molto pensiero, tuttavia entrambi risolvono più o meno lo stesso problema.

Oh, infine, assicurati di comprendere le principali differenze tra il codice della concorrenza algoritmica e il codice di produzione aziendale. Ho visto fantastici codificatori algoritmici, che hanno scritto codice orribile che non avrei mai accettato in un prodotto.

    
risposta data 25.04.2013 - 07:18
fonte
17

Direi che, anche al di fuori delle competizioni, il pensiero algoritmico è più importante della conoscenza di ogni trucco per una lingua specifica.

Naturalmente, vuoi conoscere la lingua con cui lavori nel modo migliore possibile, ma le lingue vanno e vengono, mentre la capacità di pensare in modo astratto in termini di algoritmi è un'abilità altamente trasferibile.

Caso in questione: se ricordo male, c'era un post qui su Programmers qualche tempo fa in cui qualcuno si lamentava di aver fallito FizzBuzz in un'intervista e ha accusato la sua mancanza di conoscenza dell'operatore modulo di Java per questo. Questa conclusione è sbagliata - la mancanza di conoscenza su come funziona il modulo lo ha reso incapace di pensare in modo algoritmico al problema e risolverlo, anche in assenza di un operatore modulo dedicato. Andando oltre: Java ha una classe Tree - cosa succede se, in futuro, devi lavorare con un linguaggio che non implementa questa classe? Di nuovo, la capacità di pensare al problema supera i dettagli specifici della lingua.

Ammetto che gli esempi sono semplicistici, ma aiutano a portare il punto.

    
risposta data 25.04.2013 - 10:04
fonte
14

La lingua è importante.

DARPA e la US Navy hanno fatto un esperimento shootout quasi 20 anni fa. Il vincitore della corsa scura del cavallo era Haskell. Ada e C ++ erano entrambi rappresentati; Java non lo era.

Intorno allo stesso tempo, Pratt & Whitney ha condotto uno studio di data mining sui progetti di controller per motori a reazione, esaminando i dati di timecard e bug tracker. Hanno scoperto che Ada ha raddoppiato la produttività del programmatore e 1/4 la densità di difetti di qualsiasi altra lingua che stavano utilizzando.

Atari usava FORTH per sviluppare videogames e il fatto che stessero usando FORTH era considerato estremamente riservato.

I commenti di Paul Graham sull'utilizzo di LISP sono ben noti. I commenti di Erann Gat su LISP al JPL sono altrettanto convincenti, anche se non altrettanto noti.

Il software avionico Boeing 777 è praticamente tutto Ada. La loro esperienza è stata molto buona, anche se un subappaltatore importante ha dovuto ricominciare da capo a metà strada.

La lingua è importante.

    
risposta data 25.04.2013 - 19:46
fonte
7

Alcuni punti:

  • Le prime posizioni tendono ad essere C ++ / C / Java, indipendentemente da quante righe di codice la differenza è tra quella e un'altra lingua. Questo potrebbe essere più che altro i programmatori principali tendono a scegliere queste lingue su altre, probabilmente a causa della loro velocità non elaborata.
    Sfortunatamente non riesci a vedere facilmente il linguaggio di programmazione su Google Code Jam, ma ne ho scaricato alcuni di quelli migliori e, per quanto ricordo, questi sono per lo più C / C ++. TopCoder (un popolare sito di hosting del concorso di programmazione online) ha per lo più risultati simili.

  • Dato che sono di livello piuttosto basso, sono abbastanza sicuro che non riuscirai a battere facilmente C / C ++ in termini di tempo di esecuzione non elaborato (e anche Java non traccia troppo molto indietro). Dalla mia esperienza, le lingue digitate dinamicamente tendono ad essere significativamente più lente delle lingue tipizzate in modo statico. La soluzione ottimale potrebbe non essere abbastanza veloce in alcune lingue, ma questa non dovrebbe essere una regola generale.

  • L'algoritmo giusto è vitale. Se sapessi come risolvere tutti i problemi (in dettaglio) fin dall'inizio, e sei un buon programmatore veloce, molto probabilmente vincerai, indipendentemente dalla lingua che codifichi (assumendo la soluzione ottimale in quella lingua è abbastanza veloce).

  • Il numero di linee diritte non è un grosso problema. Una volta acquisita sufficiente esperienza di programmazione, saprai che puoi dedicare 10 minuti alla programmazione di 10 linee o 200 linee, tutto dipende dalla complessità delle linee. Inoltre, se hai codificato codice simile centinaia di volte, sarai in grado di farlo abbastanza rapidamente. Non menzionare troppo tutte le macro che i top coder C / C ++ usano spesso per ottimizzare i tempi di codifica.

  • Frank è un buon punto: (al di fuori delle competizioni di programmazione) non puoi fare il codice in Python per la tua azienda se l'intero codice base è in C o altro, devi conformarti alla loro lingua.

  • È abbastanza facile passare da una lingua all'altra, non è facile accumulare anni di conoscenza del pensiero algoritmico. Sono disposto a scommettere che quasi tutti i programmatori eccellenti possono passare a un'altra (vagamente simile) lingua, diciamo, una settimana. Forse non sarà abbastanza bravo da vincere le gare di programmazione in quella lingua (dargli altre 2 settimane), ma avrà le basi giù.

risposta data 25.04.2013 - 11:05
fonte
5

La stessa logica può essere implementata meglio in C ++? Certo che può, se meglio intendi più veloce e più efficiente in termini di memoria. Il problema è che la quantità di sforzo richiesta per farlo è significativamente più alta. Inoltre, teoricamente potresti ancora andare al livello più basso e implementarlo in puro C o anche in ASM, il che richiederebbe ancora più tempo, ma potresti avere un codice ancora più ottimizzato.

Naturalmente, in caso di competizioni come Code Jam o TopCoder non è una grossa delusione, perché è solo 40 linee contro 200 linee. D'altra parte in questo tipo di competizione ciò che conta di più è la complessità tempo / spazio dell'algoritmo. Mentre nella vita reale l'applicazione, YMMV, in questi tipi di algoritmi O (n) scritti in lingue più lente battere sempre O (n²) scritto nel più veloce dei linguaggi. Soprattutto che ci saranno test multipli che sono lo scenario peggiore.

Ma a parte le competizioni, se stiamo parlando di grandi progetti di vita reale, allora non saranno più 40 linee contro 200 linee. Nei grandi progetti l'enorme base di codice inizia ad essere un problema. A quel punto si arriva a:

C ++ vs Python?

PurePythonèlento.Eccoperchél'interpretestandardPython(CPython)èscrittoinC.Praticamentetuttoconfunzioniintegratescrittecomealtamenteottimizzate.C.PythonpuòancheesserefacilmenteusatoincombinazioneconlelibrerieC(tramitectypes o come moduli nativi di cpython ) e con le librerie C ++ tramite Boost :: Python . In questo modo puoi scrivere la tua logica di alto livello in Python, un linguaggio flessibile, che consente la prototipazione e l'adattamento rapidi (il che significa che puoi dedicare più tempo alla messa a punto e al miglioramento dell'algoritmo). OTOH, puoi scrivere le tue funzioni di libreria di livello inferiore nel modulo C o C ++. Un grande esempio di tale approccio è SciPy, che è la libreria Python, ma sotto la cappa utilizza librerie numeriche altamente ottimizzate come ATLAS, LAPACK, Intels MKL o AMD ACML.

    
risposta data 25.04.2013 - 12:27
fonte
4

Secondo me, ciò che le persone considerano colloquialmente un "linguaggio di programmazione" sono in realtà tre cose separate:

  1. Tipo di lingua e sintassi
  2. IDE lingua
  3. Librerie disponibili per una lingua

Ad esempio, quando qualcuno fa apparire C # in una discussione, potresti pensare che stia parlando della sintassi del linguaggio (1), ma è sicuro al 95% che la discussione coinvolgerà .Net framework (3). Se non stai progettando una nuova lingua, è difficile e di solito inutile isolare (1) e ignorare (2) e (3). Questo perché IDE e la libreria standard sono "fattori di comfort", cose che influiscono direttamente sull'esperienza nell'uso di un determinato strumento.

Anche alcuni anni ho partecipato a Google Code Jam. La prima volta ho optato per C ++ perché ha un buon supporto per la lettura dell'input. Ad esempio, la lettura di tre numeri interi da un input standard in C ++ ha il seguente aspetto:

int n, h, w;
cin >> n >> h >> w;

Mentre in C # lo stesso sarebbe simile a questo:

int n, h, w;
string[] tokens = Console.ReadLine().Split(' ');
n = int.Parse(tokens[0]);
h = int.Parse(tokens[1]);
w = int.Parse(tokens[2]);

Questo è un sovraccarico mentale per una semplice funzionalità. Le cose diventano ancora più complicate in C # con input multilinea. Forse non ho ancora capito un modo migliore allora. Ad ogni modo, non sono riuscito a superare il primo turno perché avevo un bug che non potevo correggere prima della fine del round. Ironia della sorte, il metodo di lettura degli input ha offuscato il bug. Il problema era semplice, l'input conteneva un numero troppo grande per l'intero a 32 bit. In C #%,int.Parse(string) genererebbe un'eccezione, ma in C ++ il flusso di input del file imposterà un certo flag di errore e fallirà nel rendere silenzioso lo sviluppatore ignaro di un problema.

Entrambi gli esempi dimostrano come è stata usata la libreria piuttosto che la sintassi del linguaggio. Il primo mostra la verbosità e l'altro dimostra l'affidabilità. Molte librerie sono portate a più lingue e alcune lingue possono usare librerie che non sono specificamente create per loro (vedi la risposta di @ vartec su Python con le librerie C).

Per concludere, conoscere l'algoritmo giusto aiuta. Nelle competizioni di codifica è fondamentale, specialmente quando risorse come il tempo di esecuzione e la memoria sono volutamente limitate. Nello sviluppo di applicazioni è gradito ma generalmente non cruciale. La manutenibilità è più importante lì. È possibile ottenerlo applicando modelli di progettazione corretti, con una buona architettura, codice leggibile e documentazione pertinente e tutti questi metodi dipendono in gran parte dalle librerie interne e di terze parti. Quindi, trovo più importante sapere che tipo di ruote sono già state inventate e come si adattano poi a come crearne una mia.

    
risposta data 26.04.2013 - 15:05
fonte
2

Se vuoi competere in gare a programmazione a tempo, dovresti imparare il linguaggio più espressivo consentito nella competizione. Perl sarebbe probabilmente il migliore, seguito da Ruby o Python. Avrai ancora bisogno di una buona struttura con algoritmi, ma almeno non ti impantanerai scrivendo qualcosa come

Integer prev = b.get(k)
if (prev == null) prev = 0
Integer v = a.get(k);
if (v == null) v = 0;
b.put(prev + v);

invece di

b[k] += a[k]

Non preoccuparti di imparare diverse librerie. Sono tutti molto simili e la documentazione è online. Diventare fluenti nei linguaggi più espressivi ti renderà un programmatore migliore (ma possibilmente frustrato) in linguaggi meno espressivi. L'opposto non è vero.

NB.

La differenza tra 200 linee di codice e 40 righe di codice è enorme, ed è ancora più grande quando è la differenza tra un programma di 200.000 linee e un programma di 40.000 linee. Quindi è la differenza tra una squadra di cinque più un manager e una squadra di uno o due.

    
risposta data 25.04.2013 - 09:51
fonte
2

Qualsiasi algoritmo può essere implementato in qualsiasi linguaggio di programmazione. Dopo tutto, non è la sintassi che conta. Ma usare un linguaggio di alto livello come Python ha i suoi vantaggi. Meno lavoro e meno quantità di codice. Quindi per implementare un algoritmo in Python, avrai bisogno di meno linee di quelle richieste in un linguaggio di basso livello come C.

Python ha la maggior parte delle strutture dati integrate nella sua libreria. Ma in C, dobbiamo iniziare da zero e utilizzare una struttura per crearlo. Certamente ci sono differenze tra il linguaggio di alto livello e quello di basso livello, ma il linguaggio non dovrebbe impedirti di implementare alcun algoritmo.

    
risposta data 13.05.2013 - 13:37
fonte
2

Mentre estrapolando l'esempio "40 LoC vs 200 LoC", dicendo "beh, solo un quinto del LoC totale è ovviamente più veloce da scrivere, quindi deve essere migliore" può sembrare allettante, penso davvero che ci sia poca verità da trovato lì.

L'ottimizzazione per il minor numero di LoC non è quasi mai una buona idea secondo me. Sì, ogni LoC scritto è un potenziale bug e non è necessario eseguire il debug di ciò che non hai mai scritto eccetc. Il punto è, ottimizzare la leggibilità e il disaccoppiamento. Non importa se risolvi un problema usando una regex di 20 righe, invece di scrivere un modulo di 1k LoC. La regex sarà una parete opaca, estremamente incline a bug, difficile da capire, da incubare da alterare senza cambiare il comportamento in modi non ortopedici ecc.

Sbarazzarsi di boilerplate e verbosity che non aggiungono alcun valore va tutto bene, ma d'altra parte, usando qualcosa come Java o C #, avere una conoscenza dei modelli di progettazione e degli strumenti come il resharper ti consente tanta flessibilità in rifattorizzare il codice, ripulirlo nel tempo, rompere le cose, ecc., sarebbe semplicemente MOLTO più difficile se lo avessi scritto come script python o rubino molto più piccolo.

Un paragone molto interessante: Preferirei avere 100k LoC di codice C # disaccoppiato coperto da test, pieno di cose "overkill" come il modello strategico, le fabbriche ecc., Piuttosto che un'applicazione python 20k che "fa solo il lavoro fatto". 5 volte più codice o meno, l'architettura vince ogni giorno.

Sono pienamente d'accordo che alcuni tipi di lavoro sono più facili e più convenienti in alcune lingue, ma credo più nella scelta della lingua in base a quali strumenti sono necessari e quali sono i requisiti (e potrebbe essere nel prossimo futuro).

    
risposta data 26.01.2016 - 08:44
fonte

Leggi altre domande sui tag