Hai applicato la teoria della complessità computazionale nella vita reale?

Question

Sto seguendo un corso sulla complessità computazionale e finora ho avuto l'impressione che non sarebbe di grande aiuto per uno sviluppatore.

Potrei sbagliarmi, ma se hai già seguito questa strada, potresti per favore fornire un esempio di come la teoria della complessità ti ha aiutato nel tuo lavoro? Tante grazie.

Answer 1

O (1): codice semplice senza loop. Scorre solo attraverso. Anche le ricerche in una tabella di ricerca sono O (1).

O (log (n)): algoritmi ottimizzati in modo efficiente. Esempio: algoritmi ad albero binario e ricerca binaria. Di solito non fa male. Sei fortunato se hai un simile algoritmo a portata di mano.

O (n): un singolo loop su dati. Fa male per molto grande n.

O (n * log (n)): un algoritmo che fa una sorta di strategia di divisione e conquista. Fa male per grandi n. Esempio tipico: unisci ordinamento

O (n * n): un ciclo nidificato di qualche tipo. Fa male anche con piccoli n. Comune con calcoli con matrice ingenua. Se vuoi, evita questo tipo di algoritmo.

O (n ^ x per x > 2): una costruzione malvagia con più cicli annidati. Fa male per molto piccolo n.

O (x ^ n, n! e peggio): algoritmi bizzarri (e spesso ricorsivi) che non vuoi avere nel codice di produzione se non in casi molto controllati, per n molto piccoli e se davvero non c'è alternativa migliore . Il tempo di calcolo può esplodere con n = n + 1.

Spostare l'algoritmo da una classe di complessità superiore può far volare l'algoritmo. Pensa alla trasformazione di Fourier che ha un algoritmo O (n * n) che era inutilizzabile con l'hardware degli anni '60, tranne in rari casi. Quindi Cooley e Tukey hanno fatto alcune intelligenti riduzioni della complessità riutilizzando i valori già calcolati. Ciò ha portato alla diffusa introduzione di FFT nell'elaborazione del segnale. E alla fine è anche il motivo per cui Steve Jobs ha fatto fortuna con l'iPod.

Esempio semplice: i programmatori C naive scrivono questo tipo di loop:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

Questo è un algoritmo O (n * n) a causa dell'implementazione di strlen (). I cicli di nidificazione portano alla moltiplicazione delle complessità all'interno della big-O. O (n) all'interno di O (n) fornisce O (n * n). O (n ^ 3) all'interno di O (n) dà O (n ^ 4). Nell'esempio, il precalcolo della lunghezza della stringa trasformerà immediatamente il loop in O (n). Anche Joel ha scritto su questo.

Tuttavia la classe di complessità non è tutto. Devi tenere d'occhio la dimensione di n. Rielaborare un algoritmo O (n * log (n)) su O (n) non aiuterà se il numero di istruzioni (ora lineari) aumenta in modo massiccio a causa della rielaborazione. E se n è comunque piccolo, anche l'ottimizzazione non farà molto botto.

Answer 2

Sebbene sia vero che si può andare molto lontano nello sviluppo del software senza la minima comprensione della complessità algoritmica. Trovo che utilizzo sempre la mia conoscenza della complessità; tuttavia, a questo punto è spesso senza accorgersene. Le due cose che l'apprendimento della complessità ti offre come sviluppatore di software sono un modo per confrontare algoritmi non simili che fanno la stessa cosa (gli algoritmi di ordinamento sono l'esempio classico, ma la maggior parte delle persone in realtà non scrive il proprio genere). La cosa più utile che ti dà è un modo per descrivere rapidamente un algoritmo.

Ad esempio, considera SQL. SQL viene utilizzato ogni giorno da un numero molto elevato di programmatori. Se dovessi vedere la seguente query, la tua comprensione della query è molto diversa se hai studiato la complessità.

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Se hai studiato la complessità, allora capiresti se qualcuno dicesse che era O (n ^ 2) per un certo DBMS. Senza la teoria della complessità, la persona dovrebbe spiegare le scansioni di tabelle e simili. Se aggiungiamo un indice alla tabella degli ordini

CREATE INDEX ORDER_USERID ON Order(UserId)

Quindi la query sopra potrebbe essere O (n log n), il che farebbe un'enorme differenza per un DB di grandi dimensioni, ma per un DB piccolo, non è assolutamente nulla.

Si potrebbe sostenere che la teoria della complessità non è necessaria per capire come funzionano i database e che sarebbero corretti, ma la teoria della complessità fornisce un linguaggio per pensare e parlare di algoritmi che lavorano sui dati.

Answer 3

Per la maggior parte dei tipi di lavoro di programmazione la parte teorica e le prove potrebbero non essere utili in se stesse, ma quello che stanno facendo è cercare di darti l'intuizione di poter dire immediatamente "questo algoritmo è O (n ^ 2) quindi non possiamo eseguirlo su questi un milione di punti dati " ;. Anche nell'elaborazione più elementare di grandi quantità di dati ti imbatterai in questo.

Pensare rapidamente alla teoria della complessità è stato importante per me nell'elaborazione dei dati aziendali, nel GIS, nella programmazione grafica e nella comprensione degli algoritmi in generale. È una delle lezioni più utili che puoi ottenere dagli studi CS rispetto a ciò che in genere altrimenti studi autonomamente.

Answer 4

I computer non sono intelligenti, faranno qualunque cosa tu gli chieda di fare. I compilatori possono ottimizzare un po 'il codice per te, ma non possono ottimizzare gli algoritmi. Il cervello umano funziona in modo diverso ed è per questo che è necessario comprendere la Grande O. Considerare il calcolo dei numeri di Fibonacci. Sappiamo tutti F (n) = F (n-1) + F (n-2), e a partire da 1,1 puoi facilmente calcolare i seguenti numeri senza molto sforzo, in tempo lineare. Ma se dici al computer di calcolarlo con quella formula (ricorsivamente), non sarebbe lineare (almeno nei linguaggi imperativi). In qualche modo, il nostro algoritmo ottimizzato per il cervello, ma il compilatore non può farlo. Quindi, devi lavorare sull'algoritmo per renderlo migliore.

E poi, hai bisogno di formazione, per individuare le ottimizzazioni cerebrali che sembrano così ovvie, per vedere quando il codice potrebbe essere inefficace, per conoscere schemi per algoritmi cattivi e buoni (in termini di complessità computazionale) e così via. Fondamentalmente, quei corsi servono diverse cose:

• comprendere i modelli esecutivi e le strutture di dati e quale effetto hanno sul tempo necessario al completamento del programma;
• allena la tua mente a individuare potenziali problemi nell'algoritmo, quando potrebbe essere inefficiente su grandi set di dati. Oppure capisci i risultati della profilazione;
• apprendere modi ben noti per migliorare gli algoritmi riducendo la loro complessità computazionale;
• preparati a passare un'intervista nella bella compagnia :)

Answer 5

È estremamente importante. Se non capisci come stimare e capire quanto tempo impiegheranno i tuoi algoritmi, finirai per scrivere del codice piuttosto lento. Quando scrivo algoritmi, penso sempre alla complessità compuazionale. È qualcosa che dovrebbe essere sempre nella tua mente durante la programmazione.

Ciò è particolarmente vero in molti casi perché, sebbene l'app possa funzionare correttamente sul computer desktop con un set di dati di prova di piccole dimensioni, è importante capire la velocità con cui l'app risponderà una volta attivata e ci sono centinaia di migliaia di persone lo usano.

Answer 6

Sì, utilizzo spesso la notazione Big-O, o meglio, utilizzo i processi di pensiero che stanno dietro, non la notazione stessa. In gran parte perché così pochi sviluppatori nell'organizzazione (e) capisco spesso. Non intendo essere irrispettoso verso quelle persone, ma nella mia esperienza, la conoscenza di queste cose è una di quelle cose che "separano gli uomini dai ragazzi".

Mi chiedo se questa è una di quelle domande che possono solo ricevere " si " risposte? Mi colpisce che l'insieme di persone che comprende la complessità computazionale è approssimativamente equivalente all'insieme di persone che pensano che sia importante. Quindi, chiunque potrebbe rispondere no forse non capisce la domanda e quindi salta alla domanda successiva piuttosto che fare una pausa per rispondere. Solo un pensiero ;-)

Answer 7

Ci sono dei momenti in cui dovrai affrontare problemi che richiedono di pensarci. Ci sono molti problemi nel mondo reale che richiedono la manipolazione di un ampio set di dati ...

Esempi sono:

• Applicazione Maps ... come Google Maps - come tratteresti i dati della linea stradale in tutto il mondo e li disegneresti? e devi disegnarli velocemente!
• Applicazione logistica ... pensa all'agente di viaggio in viaggio con steroidi
• Data mining ... tutte le grandi aziende ne hanno bisogno, come si estrae un database contenente 100 tabelle e oltre 10m + righe e si ottengono risultati utili prima che le tendenze diventino obsolete?

Un corso sulla complessità computazionale ti aiuterà ad analizzare e scegliere / creare algoritmi efficienti per tali scenari.

Credetemi, qualcosa di semplice come ridurre un coefficiente, diciamo da T (3n) fino a T (2n) può fare una differenza ENORME quando la "n" viene misurato in giorni se non in mesi.

Answer 8

Ci sono molti buoni consigli qui, e sono sicuro che la maggior parte dei programmatori ha usato la loro conoscenza della complessità una volta ogni tanto.

Comunque dovrei dire che comprendere la complessità computazionale è di estrema importanza nel campo dei Giochi! Sì, l'hai sentito, questo "inutile" roba è il tipo di roba su cui vive la programmazione di gioco.

Scommetto che pochissimi professionisti probabilmente si preoccupano del Big-O tanto quanto i programmatori di giochi.

Answer 9

Uso regolarmente i calcoli della complessità, soprattutto perché lavoro nel dominio geospaziale con set di dati molto grandi, ad es. processi che coinvolgono milioni e occasionalmente miliardi di coordinate cartesiane. Una volta che inizi a colpire problemi multidimensionali, la complessità può essere un vero problema, poiché algoritmi avidi che sarebbero O (n) in una dimensione saltano improvvisamente a O (n ^ 3) in tre dimensioni e non ci vogliono molti dati per creare un serio collo di bottiglia. Come menzionato in un post simile , vedi anche che la grande notazione O diventa ingombrante quando inizi a trattare con gruppi di oggetti complessi di varie dimensioni. L'ordine della complessità può anche dipendere molto dai dati, con casi tipici che funzionano molto meglio dei casi generali per ben progettato algoritmi .

Vale anche la pena testare i tuoi algoritmi sotto un profiler per vedere se ciò che hai progettato è ciò che hai raggiunto. Trovo che la maggior parte dei colli di bottiglia si risolva molto meglio con la modifica dell'algoritmo rispetto alla maggiore velocità del processore per tutte le ovvie ragioni.

Per ulteriori informazioni sugli algoritmi generali e sulle loro complessità, ho trovato Sedgewicks lavoro entrambi informativi e accessibile. Per gli algoritmi spaziali, O'Rourkes il libro sulla geometria computazionale è eccellente.

Answer 10

Nella tua vita normale, non vicino a un computer, dovresti applicare concetti di complessità ed elaborazione parallela. Questo ti permetterà di essere più efficiente. Coerenza della cache. Questo genere di cose.

Answer 11

Sì, la mia conoscenza degli algoritmi di ordinamento mi è tornata utile un giorno quando ho dovuto ordinare una serie di esami per studenti. Ho usato l'ordinamento di tipo merge (ma non quicksort o heapsort). Durante la programmazione, utilizzo qualsiasi routine di ordinamento offerta dalla biblioteca. (non ho ancora dovuto ordinare una grande quantità di dati.)

Uso sempre la teoria della complessità nella programmazione, soprattutto nel decidere quali strutture di dati usare, ma anche quando decido se o quando ordinare le cose e per molte altre decisioni.

Answer 12

' sì ' e ' no '

sì ) Uso spesso notazione O grande quando sviluppare e implementare algoritmi. Per esempio. quando dovresti gestire 10 ^ 3 elementi e la complessità del primo algoritmo è O (n log (n)) e del secondo O (n ^ 3), puoi semplicemente dire che il primo algoritmo è quasi in tempo reale mentre il secondo richiede calcoli considerevoli.

Talvolta possono essere utili le conoscenze sulle Classi di complessità NP . Può aiutarti a capire che puoi smettere di pensare a inventare algoritmi efficienti quando alcuni problemi NP-completi possono essere ridotti al problema a cui stai pensando.

no ) Ciò che ho descritto sopra è una piccola parte della teoria delle complessità. Di conseguenza è difficile dire che lo uso, ne uso una parte minore-minore.

Devo ammettere che ci sono molti progetti di sviluppo software che non toccano lo sviluppo dell'algoritmo o il loro utilizzo in modo sofisticato. In tali casi la teoria della complessità è inutile. Gli utenti abituali di algoritmi operano spesso usando le parole "veloce" e "lento", "x secondi" ecc.

Answer 13

@Martin: Puoi per favore approfondire i processi di pensiero dietro di esso?

potrebbe non essere così esplicito come sedersi e elaborare la notazione Big-O per una soluzione, ma crea una consapevolezza del problema e questo ti guida verso la ricerca di una risposta più efficiente e lontano dai problemi negli approcci potresti prendere. per esempio. O (n * n) rispetto a qualcosa di più veloce, ad es. ricerca di parole memorizzate in un elenco anziché memorizzate in un trie (esempio inventato)

Trovo che faccia la differenza con quali strutture di dati sceglierò di usare e come lavorerò su un gran numero di record.

Answer 14

Un buon esempio potrebbe essere quando il tuo capo ti dice di fare qualche programma e puoi dimostrare usando la teoria della complessità computazionale che ciò che il tuo capo ti sta chiedendo di fare non è possibile.