array vs vettore vs lista

Sto mantenendo una tabella di lunghezza fissa di 10 voci. Ogni object è una struttura di 4 campi uguali. Ci saranno operazioni di inserimento, aggiornamento ed eliminazione, specificate dalla posizione numerica. Mi chiedo quale sia la migliore struttura dati da utilizzare per mantenere questa tabella di informazioni:

  1. array – insert / delete richiede tempo lineare a causa dello spostamento; l’aggiornamento richiede tempo costante; nessuno spazio è usato per i puntatori; accedere a un object usando [] è più veloce.

  2. vettore stl: inserimento / cancellazione richiede tempo lineare a causa dello spostamento; l’aggiornamento richiede tempo costante; nessuno spazio è usato per i puntatori; l’accesso a un object è più lento di un array poiché è una chiamata all’operatore [] e un elenco collegato.

  3. stl list – insert and delete richiede tempo lineare poiché è necessario iterare su una posizione specifica prima di applicare l’insert / delete; è necessario spazio aggiuntivo per i puntatori; l’accesso a un object è più lento di un array poiché si tratta di un attraversamento lineare della lista collegata.

In questo momento, la mia scelta è usare un array. È giustificabile? O mi sono perso qualcosa?

Qual è più veloce: attraversare un elenco, quindi inserire un nodo o spostare elementi in un array per produrre una posizione vuota e quindi inserire l’object in quella posizione?

Qual è il modo migliore per misurare questa performance? Posso solo visualizzare il timestamp prima e dopo le operazioni?

Usa il vector STL . Fornisce un’interfaccia altrettanto ricca come list e rimuove il problema della gestione della memoria richiesta dagli array.

Dovrai sforzarti molto per esporre il costo delle prestazioni operator[] – di solito viene sottolineato.

Non ho alcun numero da darti, ma ricordo di aver letto l’analisi delle prestazioni che descriveva come il vector fosse più veloce della list anche per inserti ed eliminazioni (sotto una certa dimensione di corso). La verità è che questi processori che utilizziamo sono molto veloci e se il tuo vettore si adatta alla cache L2, allora andrà davvero molto velocemente. Gli elenchi d’altra parte devono gestire gli oggetti heap che uccideranno il tuo L2.

L’ottimizzazione prematura è la radice di tutto il male.

Basandomi sul tuo post, direi che non c’è motivo di rendere qui la tua scelta della struttura dei dati basata su prestazioni. Scegli ciò che è più conveniente e torna a cambiarlo se e solo se il test delle prestazioni dimostra che si tratta di un problema.

Vale veramente la pena investire un po ‘di tempo nel comprendere le differenze fondamentali tra elenchi e vettori. La differenza più significativa tra i due è il modo in cui memorizzano gli elementi e tengono traccia di essi.

– Elenchi –

Elenco contiene elementi che contengono l’indirizzo di un elemento precedente e successivo in essi memorizzato. Ciò significa che puoi INSERIRE o CANCELLARE un elemento in qualsiasi punto dell’elenco con velocità costante O (1) indipendentemente dalla dimensione dell’elenco. È anche ansible unire (inserire un altro elenco) nell’elenco esistente ovunque con velocità costante. Il motivo è che la lista deve solo cambiare due puntatori (il precedente e il successivo) per l’elemento che stiamo inserendo nella lista.

Le liste non sono buone se hai bisogno di un accesso casuale. Quindi se si prevede di accedere all’ennesimo elemento nella lista – si deve attraversare l’elenco uno alla volta – O (n) velocità

– Vettori –

Il vettore contiene elementi in sequenza, proprio come un array. Questo è molto conveniente per l’accesso casuale. L’accesso all’elemento “n” in un vettore è un semplice calcolo puntatore (velocità O (1)). L’aggiunta di elementi a un vettore è, tuttavia, diversa. Se si vuole aggiungere un elemento nel mezzo di un vettore, tutti gli elementi che verranno dopo tale elemento dovranno essere ridistribuiti per fare spazio alla nuova voce. La velocità dipenderà dalla dimensione del vettore e dalla posizione del nuovo elemento. Lo scenario peggiore è l’inserimento di un elemento nella posizione 2 di un vettore, il migliore è l’aggiunta di un nuovo elemento. Pertanto – insert funziona con velocità O (n), dove “n” è il numero di elementi che devono essere spostati – non necessariamente le dimensioni di un vettore.

Esistono altre differenze che implicano requisiti di memoria ecc., Ma la comprensione di questi principi di base su come funzionano effettivamente elenchi e vettori vale davvero la pena dedicare del tempo.

Come sempre … ” L’ottimizzazione prematura è la radice di tutti i mali ” quindi considera prima ciò che è più conveniente e fa funzionare le cose esattamente nel modo desiderato, quindi ottimizza. Per 10 voci che menzioni: non importa ciò che usi – non sarai mai in grado di vedere alcun tipo di differenza di prestazioni, qualunque sia il metodo che usi.

Preferisco uno std :: vector over e array. Alcuni vantaggi del vettore sono:

  • Allargano memoria dallo spazio libero quando aumentano di dimensioni.
  • NON sono un puntatore sotto mentite spoglie.
  • Possono aumentare / ridurre il tempo di esecuzione delle dimensioni.
  • Possono eseguire il controllo del range usando a () .
  • Un vettore conosce le sue dimensioni, quindi non devi contare gli elementi.

La ragione più convincente per usare un vettore è che ti libera dalla gestione esplicita della memoria e non perde memoria. Un vettore tiene traccia della memoria che utilizza per memorizzare i suoi elementi. Quando un vettore ha bisogno di più memoria per gli elementi, ne assegna di più; quando un vettore esce dal campo di applicazione, libera quella memoria. Pertanto, l’utente non deve preoccuparsi dell’allocazione e della deallocazione della memoria per gli elementi vettoriali.

Stai facendo ipotesi che non dovresti fare, ad esempio “l’accesso a un object è più lento di un array dato che è una chiamata all’operatore []”. Posso capire la logica che c’è dietro, ma tu e io non possiamo saperlo finché non lo elenchiamo.

Se lo fai, scoprirai che non vi è alcun sovraccarico, quando le ottimizzazioni sono attive. Il compilatore inline le chiamate di funzione. C’è una differenza nelle prestazioni della memoria. Un array viene assegnato staticamente, mentre un vettore si assegna dynamicmente. Una lista alloca per nodo, che può ridurre la cache se non stai attento.

Alcune soluzioni devono avere il vector allocare dallo stack e disporre di un allocatore di pool per un list , in modo che i nodes possano rientrare nella cache.

Quindi, piuttosto che preoccuparti delle affermazioni non supportate, dovresti preoccuparti di rendere il tuo progetto il più pulito ansible. Quindi, che ha più senso? Un array, vettore o lista? Non so cosa stai cercando di fare, quindi non posso risponderti.

Il contenitore “predefinito” tende ad essere un vector . A volte anche un array è perfettamente accettabile.

Innanzitutto un paio di note:

Una buona regola pratica sulla selezione delle strutture di dati: in genere, se hai esaminato tutte le possibilità e stabilito che un array è la scelta migliore, ricomincia. Hai fatto qualcosa di molto sbagliato.

Gli elenchi AWL non supportano l’ operator[] , e se hanno fatto la ragione per cui sarebbe più lento dell’indicizzazione, un array non ha nulla a che fare con il sovraccarico di una chiamata di funzione.

A proposito di ciò, il vettore è il chiaro vincitore qui. La chiamata operator[] è essenzialmente trascurabile poiché il contenuto di un vettore è garantito contiguo in memoria. Supporta le operazioni insert() e erase() che dovresti scrivere autonomamente se hai usato un array. Fondamentalmente si riduce al fatto che un vettore è essenzialmente un array aggiornato che supporta già tutte le operazioni necessarie.

Sto mantenendo una tabella di lunghezza fissa di 10 voci. Ogni object è una struttura di 4 campi uguali. Ci saranno operazioni di inserimento, aggiornamento ed eliminazione, specificate dalla posizione numerica. Mi chiedo quale sia la migliore struttura dati da utilizzare per mantenere questa tabella di informazioni:

Sulla base di questa descrizione sembra che la lista potrebbe essere la scelta migliore dal momento che è O (1) quando si inserisce e si elimina nel mezzo della struttura dati. Sfortunatamente non puoi usare posizioni numeriche quando usi elenchi per fare inserimenti ed eliminazioni come puoi per array / vettori. Questo dilemma porta a un gran numero di domande che possono essere utilizzate per prendere una decisione iniziale su quale struttura potrebbe essere la migliore da usare. Questa struttura può essere successivamente modificata se il test mostra chiaramente la sua scelta sbagliata.

Le domande che devi porre sono tre volte. Il primo è quanto spesso stai pianificando di fare delete / inserti nel mezzo rispetto alle letture casuali. Il secondo è l’importanza dell’uso di una posizione numerica rispetto a un iteratore. Infine, l’ordine nella tua struttura è importante.

Se la risposta alla prima domanda è la lettura casuale sarà più prevalente di un vettore / array probabilmente funzionerà bene. Notare che l’iterazione attraverso una struttura di dati non è considerata una lettura casuale anche se viene utilizzata la notazione dell’operatore []. Per la seconda domanda, se si richiede assolutamente una posizione numerica rispetto a un vettore / array, anche se ciò potrebbe comportare un impatto sulle prestazioni. Test successivi potrebbero mostrare che questo colpo di prestazioni è trascurabile rispetto alla codifica più semplice con posizioni numeriche. Infine, se l’ordine non è importante, è ansible inserire ed eliminare in un vettore / array con un algoritmo O (1). Di seguito viene mostrato un algoritmo di esempio.

 template  void erase(vector & vect, int index) //note: vector cannot be const since you are changing vector { vect[index]= vect.back();//move the item in the back to the index vect.pop_back(); //delete the item in the back } template  void insert(vector & vect, int index, T value) //note: vector cannot be const since you are changing vector { vect.push_back(vect[index]);//insert the item at index to the back of the vector vect[index] = value; //replace the item at index with value }