In quali settori della programmazione il tempo di esecuzione dell'algoritmo è in realtà un problema importante?

15

A volte sento dire che a causa della velocità dei processori e della quantità di memoria disponibile, l'efficienza dell'algoritmo e il tempo di esecuzione non sono, in pratica, di grande preoccupazione.

Ma immagino ci siano ancora aree in cui tali considerazioni rimangono di fondamentale importanza. Due che vengono in mente sono nel trading algoritmico, dove migliaia di transazioni devono essere condotte in frazioni di secondo, e programmazione di sistemi embedded, dove la memoria e il potere sono spesso scarsi. Ho ragione su questi esempi? e quali altre aree sarebbero anche esempi?

    
posta cocojambles 11.02.2012 - 04:59
fonte

13 risposte

14

La velocità è sempre richiesta. Immagino tu abbia ragione. Ecco alcuni esempi in cui sono richiesti algoritmi accurati:

  1. Crittografia

  2. Ricerca in database di grandi dimensioni

  3. Ordinamento e unione

  4. Ricerca di testo (non indicizzata), compresi i caratteri jolly

  5. Problemi di matematica con calcoli intensivi

  6. Simulazione

  7. Applicazioni di data mining

  8. Animazione

  9. AI

  10. Computer vision

risposta data 11.02.2012 - 05:06
fonte
7

Ci sono alcuni casi in cui il tempo di esecuzione dell'algoritmo potrebbe non essere un grosso problema, perché siamo arrivati al punto che si può semplicemente dare un pugno attraverso un algoritmo più a lungo con hardware più potente. Ma ci sono sicuramente alcuni posti in cui gli speed-up sono essenziali.

In generale, qualsiasi cosa usi enormi dataset sarà un problema. Quando hai qualcosa che non va bene con n, e poi fai un numero davvero enorme, hai un problema. Ho il sospetto che se si sia passati al sito della beta di Computational Science e si sia spiata un po ', si potrebbero trovare molti problemi che necessitano di algoritmi migliori e più veloci. Alcune aree in cui mi sono imbattuto:

  • Analisi statistiche particolarmente complesse. Una combinazione di algoritmi inefficienti e set di dati di grandi dimensioni può significare massicci rallentamenti. Per alcuni studi, questo potrebbe non avere importanza, ma cosa succede se si sta tentando di fare qualcosa con una rapida svolta? "Uscirà dal server tra un mese" è probabilmente una brutta cosa quando si esegue un sistema di sorveglianza delle minacce chimico / nucleare / biologico.
  • Data mining su set di dati di grandi dimensioni.
  • Simulazioni che coinvolgono molte variabili.

In generale, il calcolo scientifico in generale sembra essere un'area in cui la complessità di ciò che viene programmato genera opportunità per gravi rallentamenti se il tuo algoritmo è lento (molti di loro soffrono di n molto grandi). E, come hai detto, ci sono applicazioni finanziarie. Quando i millisecondi possono determinare se fai o perdi denaro in un trade, gli algoritmi "abbastanza buoni" non lo taglieranno se c'è qualcosa di meglio che puoi fare.

    
risposta data 11.02.2012 - 05:24
fonte
4

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern.

Prendilo con un granello di sale. Più potenza di calcolo in pratica significa semplicemente che il tuo n può diventare molto più grande prima che rallenti significativamente. Per la maggior parte dei problemi quotidiani, questo n è ora abbastanza grande da non doverlo preoccupare. Tuttavia, dovresti comunque conoscere la complessità dei tuoi algoritmi.

Con più risorse disponibili, potrebbe essere necessario crimpare più dati in un secondo momento. Oggi è necessario analizzare un file di log da 10 MB con 100.000 righe. In un anno potresti avere un file di registro da 100 GB con 1.000.000.000 di righe. Se la quantità di dati aumenta più rapidamente delle risorse disponibili, ti imbatti in problemi più tardi.

Con più risorse disponibili, più livelli sono impilati uno sull'altro. OS, framework OS, framework di terze parti, interprete di lingua e infine il tuo strumento. Tutte le inutili inefficienze in tutti i diversi livelli si moltiplicano. Domani il tuo strumento può girare su un nuovo sistema operativo con più campane e fischietti, che a sua volta mangia più cicli e più memoria, lasciando meno per te.

Quindi, per rispondere alla tua domanda, devi ancora preoccuparti di dove devono essere crunchati sempre più dati (sufficienti esempi forniti nelle altre risposte) e dove non si fornisce lo strumento finale, ma un altro livello di astrazione per altri strumenti .

    
risposta data 11.02.2012 - 09:08
fonte
4

Alcuni anni fa dovevo scrivere un algoritmo che ordinava provette disposte su n rack in due partizioni distinte: cioè un sottoinsieme di tubi era "scelto" e il resto erano "Non scelto" e il risultato finale sarebbe che nessun rack avrebbe sia una "scelta" che una "non scelta" su di essa (c'erano alcuni requisiti extra come la compressione). Ogni rack conteneva un massimo di 100 tubi.

L'algoritmo doveva essere utilizzato per pilotare un robot di smistamento di provette in un laboratorio farmaceutico.

Quando mi sono state fornite le specifiche originali, mi è stato assegnato un tempo di calcolo di 1 minuto per ordinare circa 2000 tubi, poiché pensavamo che l'usabilità non fosse troppo dolorosa. Era necessario che il numero di mosse fosse minimo su tutte le possibili combinazioni poiché il robot stesso era lento .

L'assunto implicito era che la complessità sarebbe stata esponenziale con il numero di tubi. Tuttavia, mentre lavoravo al progetto dell'algoritmo, ho scoperto che esiste un algoritmo di O(n) veloce in cui n è il numero di rack che hanno eseguito un partizionamento ottimale dei tubi. Il risultato è stato che il tempo di ordinamento dell'algoritmo era istantaneo, quindi la visualizzazione di ordinamento sarebbe stata aggiornata in tempo reale mentre l'utente ha configurato la loro operazione di ordinamento.

Per me la differenza tra l'utente seduto per un minuto dopo ogni cambiamento e avere una GUI istantaneamente reattiva era la differenza tra un software che era funzionalmente sufficiente e un software che era piacevole da usare.

    
risposta data 11.02.2012 - 12:02
fonte
3

Altre aree includono molti tipi di elaborazione del segnale in tempo reale, sistemi di controllo della retroazione, deconvoluzione dell'esplorazione dell'olio, compressione video, ray tracing e rendering dei fotogrammi, sistemi di realtà virtuale, giochi dove un frame rate elevato potrebbe rappresentare un vantaggio competitivo significativo, e smartphone e altre app per dispositivi mobili, in cui un numero elevato di cicli della CPU consuma più rapidamente la durata della batteria degli utenti.

Sono abbastanza sorpreso che questa domanda venga anche chiesta, dato che per qualsiasi supercomputer Top-500 mai costruito, c'è probabilmente una lista d'attesa di ricercatori che possono massimizzare e desiderare per magnitudini potenza o magnitudini più elevate algoritmi migliori per risolvi qualche problema (piega alcune proteine per decifrare il cancro, ecc.) prima che si ritirino.

    
risposta data 11.02.2012 - 07:25
fonte
1

Penso che motori di ricerca come Google e Bing è una delle aree più grandi in cui vengono utilizzati algoritmi complessi e svolgono un ruolo chiave nell'accelerazione dei risultati con rilevanza (ranking della pagina) che porta più utilità per gli utenti.

    
risposta data 11.02.2012 - 05:38
fonte
1

L'efficienza dell'algoritmo non è una preoccupazione importante al giorno d'oggi perché stiamo usando algoritmi efficienti. Se hai usato un algoritmo O (n!), Sarebbe lento su qualsiasi tipo di hardware.

    
risposta data 11.02.2012 - 09:12
fonte
1

La complessità dell'algoritmo sta diventando sempre più importante con l'aumentare della quantità di dati. Fortunatamente, soluzioni generiche efficienti per problemi di programmazione comuni (ricerca e ordinamento, principalmente) sono incluse in quasi tutte le librerie standard del linguaggio di programmazione moderno, quindi normalmente un programmatore non deve preoccuparsi molto di queste cose. Il rovescio della medaglia è che molti programmatori non sanno affatto cosa sta succedendo sotto il cofano e quali sono le caratteristiche degli algoritmi che usano.

Questo diventa particolarmente problematico dal momento che molte applicazioni non sono sottoposte a stress test: le persone scrivono codice che funziona bene per piccoli set di dati di test, ma quando si confronta con qualche migliaio di volte più dati, il codice si ferma. Qualcosa che funziona bene per dieci dischi esplode rapidamente quando il set di dati cresce. Esempio del mondo reale: un pezzo di codice che doveva eliminare elementi non collegati a nessuna categoria utilizzava un ciclo annidato a tre livelli, che è O (n ^ 3). Con solo 10 record nel database di test, ciò significava 1000 controlli - perfettamente fattibili, e non introduce un ritardo notevole. Tuttavia, il database di produzione si è riempito rapidamente di circa 1000 righe, e improvvisamente il codice fa un miliardo di controlli ogni volta.

Quindi: No, non è necessario conoscere i dettagli per implementare tutti i tipi di algoritmi accurati e non è necessario essere in grado di inventare il proprio, ma è necessaria una conoscenza di base degli algoritmi comuni , quali sono i loro punti di forza e di debolezza, quando e quando non usarli, e devi essere consapevole del possibile impatto della complessità algoritmica, in modo che tu possa decidere quale livello di complessità sia accettabile.

    
risposta data 11.02.2012 - 10:54
fonte
0

Non si tratta di quali domini applicativi sono sensibili al runtime. Qualsiasi programma, ovunque, ha una prestazione minima al di sotto della quale è effettivamente inutile. Il punto della complessità dell'algoritmo è il modo in cui varia con l'aumentare delle dimensioni dell'input. In altre parole, le aree in cui la velocità è particolarmente importante sono quelle in cui ci si aspetta di dover scalare oltre non solo la dimensione del problema corrente, ma l'ordine di grandezza della dimensione del problema corrente. Se si elaborano le domande di imposta dei cittadini di un dipartimento della Francia, l'attività potrebbe essere ampia, ma non è probabile che né la dimensione della popolazione né la complessità dell'elaborazione di un record aumenteranno di dieci o cento volte, quindi qualsiasi cosa funzioni per probabilmente continuerai a lavorare. Ma se si tenta di creare qualcosa che decollerà dai volumi di Internet, la complessità dell'algoritmo è la chiave: tutto ciò che dipende più linearmente o log-linearmente dalla dimensione di input sarà molto più costoso molto velocemente, e alla fine la velocità del processore non riesce a tenere il passo con la crescita.

    
risposta data 11.02.2012 - 09:10
fonte
0

Nel mio campo (VFX, che copre cose come la tracciatura dei percorsi, l'animazione del computer, la simulazione delle particelle, la fluidodinamica, l'elaborazione delle immagini, ecc.), la complessità algoritmica è fondamentale. Non c'è assolutamente nulla che funzioni in modo peggiore del tempo linearithmic può sperare di completare in qualsiasi momento ragionevole input che comunemente raggiungono milioni di vertici, poligoni, voxel, particelle, texel, specialmente quando molte di queste cose devono essere completate molte volte al secondo per fornire feedback interattivo in tempo reale.

Detto questo, non c'è quella strong enfasi sulla complessità algoritmica nella discussione tipicamente tra colleghi, forse perché è in qualche modo data per scontata e piuttosto "rudimentale". Generalmente si presume che si stia scrivendo un tracciatore di percorso che funzionerà in tempo logaritmico o migliore e che le strutture di dati come le gerarchie del volume di delimitazione sono familiari e relativamente banali da implementare per il lettore. Ho persino avuto un collega esperto che ha continuato a dire che il multithreading e il SIMD sono più importanti degli algoritmi, e non credo che intendesse questo nel senso che si potrebbe aspettarsi di ottenere molto dal parallelizzare un bubble sort. Penso che abbia detto questo perché ha dato per scontato che avremmo applicato algoritmi sensibili, e il resto della sfida è spesso la parallelizzazione e la scelta e l'adattamento di algoritmi e la progettazione della rappresentazione dei dati per operare in parallelo.

Spesso in questi giorni molta attenzione è prendere molti di questi algoritmi familiari e farli sfruttare meglio le caratteristiche di base dell'hardware come la cache della CPU, i registri SIMD e le istruzioni, le GPU e i core multipli. Ad esempio, Intel ha escogitato un nuovo modo di prendere il vecchio BVH e di inventare il concetto di "pacchetti di raggi", testando in pratica più raggi coerenti in una sola volta con un tipo di attraversamento dell'albero ricorsivo (che potrebbe sembrare come veniamo con la sua parte di complessità e sovraccarico, eccetto che è più che compensato dal fatto che quei raggi possono ora essere testati simultaneamente per le intersezioni raggio / AABB e raggio / triangolo attraverso istruzioni e registri SIMD). Altri traccianti di tracciati all'avanguardia sono riusciti a implementare tali indici spaziali e ad eseguire effettivamente le intersezioni di raggio direttamente su GPU.

Una cosa simile con la suddivisione di catmull-clark, che è roba molto rudimentale nella computer grafica. Ma oggigiorno ciò che è competitivo e caldo e super efficiente sono le implementazioni di GPU che approssimano la suddivisione CC usando Gregory Patches, come reso popolare da Charles Loop e successivamente adottato dalla Pixar. L'implementazione della CPU più diretta ora è piuttosto obsoleta, non necessariamente perché è stata sostituita in termini di complessità algoritmica, ma perché è stata sostituita da qualcosa che funziona bene con la GPU.

Di solito, in questi giorni la maggior parte della sfida non è la definizione del miglior algoritmo in un modo relativamente indipendente dalle caratteristiche di base dell'hardware. In realtà ho trovato il piede nel settore presentando una nuova struttura di accelerazione che ha accelerato significativamente il rilevamento delle collisioni per l'animazione di personaggi e altri corpi morbidi negli anni '90 utilizzando un approccio di segmentazione gerarchico rispetto a un indice spaziale, che mi ha dato un sacco di offerte di lavoro, ma di questi tempi non è più così impressionante da quando l'ho pubblicato molto prima che avessimo cache di CPU e core multipli e GPU programmabili e cosa no, e oggigiorno uso un approccio completamente diverso a seguito delle modifiche significative apportate al hardware sottostante. Quindi l'attenzione si è spostata maggiormente verso ciò che potrebbe essere nel campo delle "micro-ottimizzazioni" nel mio caso rispetto ai nuovi concetti algoritmici perché ora abbiamo più core, registri AVX, shader GPU, ecc. È un gioco di palla diverso per io ora dove non posso solo sperare di competere inventando un algoritmo interessante a meno che non giochi davvero bene con la natura peculiare dell'hardware di oggi che richiede molta attenzione e attenzione in questi giorni per sfruttare appieno.

    
risposta data 25.12.2018 - 13:42
fonte
0

Una volta mi imbattevo in un problema in cui un algoritmo di solito scorreva in O (n), ma in circostanze rare ed estremamente improbabili avrebbe bisogno del tempo O (n ^ 3) - le circostanze "rare" erano una directory contenente file con nomi che erano validi in un sistema operativo ma non in un altro.

Nessuno ha mai avuto problemi. Poi un cliente ha usato una strategia per denominare i file che sarebbero stati sistematicamente inseriti nel caso O (n ^ 3) e con alcuni 100 file il sistema è arrivato a un punto morto virtuale. Il risultato era che l'algoritmo doveva essere cambiato.

    
risposta data 25.12.2018 - 21:20
fonte
0

Altri tre che non sono stati menzionati:

1) Molti giochi di strategia in tempo reale. Guarda quelli che hanno unità che non possono condividere una posizione. Osserva cosa succede al pathfinding quando un grande gruppo di unità si muove attraverso un terreno limitato. Devo ancora incontrare un gioco senza una sorta di problema sostanziale con questo perché semplicemente non c'è abbastanza potenza della CPU disponibile.

2) Molti problemi di ottimizzazione. (Edit: Da quando ho scritto questa risposta ne ho trovata una: il mio obbiettivo era quello di eliminare i percorsi ridondanti in modo da lasciare tutti i nodi connessi con il peso minimo dei percorsi di connessione.Il mio approccio originale funzionava abbastanza bene fino a quando non ho spostato più della potatura a quella routine, poi ho capito che era 2 ^ n. Ora è n ^ 2 anche se a volte può produrre un risultato leggermente non ottimale.)

3) Cose che devono operare su grandi quantità di dati in tempo reale. Considera un DVD: di solito ricevi 2 ore di video in 4.7 gb. Considera un tipico file video con la stessa risoluzione: quelle 2 ore di video arriveranno generalmente in meno di 1 GB. La ragione di questo è quando le specifiche del DVD sono state stabilite non è possibile creare un lettore DVD a prezzi ragionevoli in grado di decodificare i formati più moderni in modo sufficientemente veloce.

    
risposta data 12.02.2012 - 04:09
fonte
0

Bene, qualsiasi applicazione in genere viene eseguita su un supercomputer ( elenco delle macchine più grandi ) si qualifica. Questi sono diversi, ma una grande sottoclasse di loro è la simulazione fisica:

  • Simulazioni fisiche:
    • Previsioni del tempo
    • Simulazioni climatiche
    • Simulazioni di stelle esplosive ecc.
    • Simulazioni di esplosioni di armi nucleari
    • Simulazioni aerodinamiche di auto / aerei / treni ecc.
    • ...
  • Calcolo di immagini dai dati del radiotelescopio
  • Applicazioni biologiche:
    • Roba con sequenze di DNA (non mi piacciono molto)
    • roba biochimica come il ripiegamento delle proteine
    • Simulazioni di come le cellule nervose lavorano insieme per elaborare le informazioni
    • Simulazioni di altre interazioni complesse come gli ecosistemi
    • ...
  • ...

Questi sono solo gli argomenti principali, ma basta leggere l'elenco dei diversi supercomputer e rendersi conto che ognuno di questi è costruito per abilitare alcuni tipi di calcoli che non sarebbero possibili senza tale gigantesco macchine.

E, una volta visto che abbiamo effettivamente bisogno di queste macchine, rendi conto dei costi che possono essere salvati, aumentando semplicemente l'applicazione del 10% . Qualsiasi ottimizzazione di questi codici aumenta direttamente la quantità di risultati che siamo in grado di ottenere da queste macchine.

    
risposta data 26.12.2018 - 00:55
fonte

Leggi altre domande sui tag