Mi sembra che, per l'uso quotidiano, strutture di dati più primitive come gli array ottengano il lavoro esattamente come farebbe un albero binario. La mia domanda è: quanto è comune usare queste strutture quando si scrive codice per progetti sul lavoro o progetti che si svolgono nel tempo libero?
Capisco il tempo migliore di inserimento / cancellazione / tempo di smistamento per alcune strutture, ma sarebbe davvero così importante se lavorassi con una quantità relativamente piccola di dati?
Uso letteralmente alberi / mappe e elenchi ogni giorno. In realtà raramente uso gli array, per la loro inflessibilità: gli array sono più difficili con cui lavorare!
Quale implementazione specifica di una lista (ArrayList, LinkedList, ..) o mappa (HashMap, TreeMap, ..) che utilizzo dipende esclusivamente dal compito a disposizione, e richiede un po 'di buon senso e una supposizione istruita.
Ogni lingua ha il proprio set di strutture dati "integrate" che gli sviluppatori utilizzano più di altri. In C i suoi array, ma in C #, Python e Ruby sono probabilmente elenchi e dizionari. Dipende da ciò che ottieni "gratis" con una lingua e la sua libreria di base.
Sto sviluppando principalmente in C # e uso l'Elenco generico (strongmente tipizzato) sempre insieme al dizionario generico. Ti libera dall'interesse per l'implementazione della struttura dati e puoi concentrarti solo sul tuo algoritmo. In C, credo che impiegheresti molto più tempo a implementare questo tipo di cose e quindi potresti essere felice di aderire a strutture di livello inferiore come gli array.
Ma anche l'implementazione delle tue strutture di dati personalizzate ha un ruolo: recentemente ho avuto bisogno di impostare un tipo QuadTree in C # per il partizionamento dello spazio 2D: quella era la soluzione migliore per ciò che era necessario.
L'efficace C ++ dice che std::vector (un array resizable) dovrebbe essere la scelta di default per un contenitore. Bjarne Stroustrup ha presentato un "grafico invisibile" [svanito dalle diapositive] della conferenza Going Native in cui ha confrontato la struttura dei dati teoricamente migliore (elenco collegato) con un vettore. Il vettore ha vinto per il suo range di dimensioni testate in quanto i messaggi di cache causati dai seguenti elementi dell'elenco hanno ucciso completamente le prestazioni.
Al lavoro sviluppiamo vari algoritmi di trasformazione dei dati in cui le prestazioni sono importanti e circa il 75% di tutte le strutture di dati sono vettori. Seguono in linea i vettori ordinati, che sono ricercabili in modo efficiente con la ricerca binaria ( std::lower_bound e std::upper_bound ). Poi vengono gli hash e gli alberi (quando l'algoritmo ha bisogno di online insert / update / delete [cioè, quando un vettore ordinato non può essere costruito da zero]), dopo di loro arriva std::dequeue (una combinazione di lista e assegnazione sequenziale) usato magro meno di una dozzina di volte. Elenco singlely / doppiamente collegato? < 5 (oserei dire zero) occorrenze in un grande progetto C ++.
Molto onestamente, non sono d'accordo. Trascorro molto del mio tempo libero scrivendo C. Ho fatto un numero di interpreti ultimamente. Sebbene utilizzi gli array in alcune circostanze, utilizzo quasi sempre elenchi collegati, alberi binari, tabelle hash o altre strutture.
Ho due ragioni:
Nessun limite di dimensione. Non importa quanto pensi di sapere all'inizio, otterrai sempre un limite di dimensioni.
Più algoritmi naturali cadono da cose come le liste collegate e alberi binari. Puoi recurse su di loro, o puoi iterare, ma loro funziona meglio.
Al giorno d'oggi molte strutture di dati utili sono in librerie convenienti da usare, a prescindere dalla migliore struttura dati per il lavoro, che molto spesso sono alberi, elenchi concatenati, tentativi o altro. Naturalmente, questo è previsto al lavoro. Ma perché dovrei voler rendere la mia vita più difficile solo perché è un progetto per hobby? Non faccio programmazione per hobby in modo che possa divertirmi a digitare a[x+1] = a[x] + a[x-1] un sacco di volte; Lo faccio per risolvere i problemi. L'uso appropriato delle strutture di dati è una parte importante di come farlo accadere.
Se ti stai chiedendo quanto spesso scrivo una struttura dati personalizzata ... beh..non molto spesso in qualsiasi contesto, dal momento che così tanti potenti sono disponibili nelle librerie. Ma la regola è la stessa: se una nuova struttura dati è "la migliore" (tenendo conto di quanto tempo mi ci vorrà per scrivere e debuggare il codice per essa), allora la userò.
Se sto usando Python, uso principalmente: dizionari (nessuna sorpresa), liste, tuple. Ammetto che considero gli elenchi come array a patto che possano essere indicizzati come uno solo.
Lavoravo con C ++ e C #. Uso elenchi, mappe, vettori quasi ogni giorno. La maggior parte delle persone non si preoccupa davvero di prenderla in una prospettiva della struttura dei dati, ma solo come un modo per raggiungere il proprio obiettivo.
Uso raramente gli array, principalmente quando lavoro con le API di Windows, ecc. dove è necessario fornire array a lunghezza fissa. Ma d'altra parte, non sono abituato a sostituire gli array con strutture di dati dinamicamente in crescita come il vettore. Sento che è complicato e oltre alla complessità rovina la leggibilità.
Dipende anche dal tipo di piattaforma su cui stai lavorando. Quando ho lavorato nel progetto Linux embedded, ero in gran parte bloccato con matrici di dimensioni fisse in cui nessuna di queste strutture dati o implementazioni C ++ può essere utilizzata.
Leggi altre domande sui tag data-structures