DOMANDA Profilatura push_back di list e vector in C++

Pubblicità
P

Peri

Nuovo Utente
Messaggi
82
Reazioni
3
Punteggio
29
Salve
Usando la libreria chrono ho eseguito questa profilatura della funzione membro push_back di list e vector
C++: 
#include <vector>
#include <list>
#include <chrono>

#define NMAX 10000

int main()
{
    std::cout << "Questo programma mostra le differenze computazionali tra list e vector" << std::endl;
    std::chrono::duration<double> diffL, diffV;
    std::chrono::system_clock::time_point start, end;
    for (volatile int i = 0; i < NMAX; i++)
    {
        {
            std::list<unsigned> myList;
            start = std::chrono::system_clock::now();
            for (volatile int j = 0; j < i; j++)
                myList.push_back(0);
            end = std::chrono::system_clock::now();
            diffL = end - start;
        }
        {
            std::vector<unsigned> myVec;
            start = std::chrono::system_clock::now();
            for (volatile int j = 0; j < i; j++)
                myVec.push_back(0);
            end = std::chrono::system_clock::now();
            diffV = end - start;
        }
        std::cout << "Rapporto tempo trascorso per aggiungere " << i << " dati: " << diffL.count() / diffV.count() << std::endl;
    }
    return 0;
}
Quello che noto è che le liste sono più lente dei vettori nell'aggiungere dati (almeno nel mio pc, sono più veloci quando si aggiungono tra i 2 e i 18 dati).
Ma quindi quando conviene usare le liste?
Grazie mille in anticipo!
 
Le liste sono strutture dati differenti rispetto ai vettori. I vettori sono degli array dinamici, vengono espansi quando viene raggiunto il cap di elementi.

Le liste sono liste collegate, sono unite da puntatori: ogni elemento della lista è raggiungibile solo attraverso il puntatore dell'elemento precedente (se sono double linked list, hanno un puntatore al figlio e uno al padre).

Ai pro e contro con entrambi. Un grande vantaggio degli array sono sicuramente le al locazioni. Hai il vantaggio della data locality, la memoria allocate è contigua e ne guadagni in quanto gli elementi adiacenti sono già in cache.

Nel caso di C++ le liste sono double linked list. Un altro lato negativo è che non puoi accedere a una posizione casuale, in quanto la lista deve essere attraversata elemento per elemento.

Sono da telefono, ho risposto un po' di fretta, spero sia chiaro. ;)
 
DispatchCode ha detto:
Le liste sono strutture dati differenti rispetto ai vettori. I vettori sono degli array dinamici, vengono espansi quando viene raggiunto il cap di elementi.

Le liste sono liste collegate, sono unite da puntatori: ogni elemento della lista è raggiungibile solo attraverso il puntatore dell'elemento precedente (se sono double linked list, hanno un puntatore al figlio e uno al padre).

Ai pro e contro con entrambi. Un grande vantaggio degli array sono sicuramente le al locazioni. Hai il vantaggio della data locality, la memoria allocate è contigua e ne guadagni in quanto gli elementi adiacenti sono già in cache.

Nel caso di C++ le liste sono double linked list. Un altro lato negativo è che non puoi accedere a una posizione casuale, in quanto la lista deve essere attraversata elemento per elemento.

Sono da telefono, ho risposto un po' di fretta, spero sia chiaro. ;)
Clicca per espandere...
Da un punto di vista teorico noi abbiamo:
oggetto:inserimento:ricerca:accesso:
lista con n componentiO(1)O(n)O(n)
vettore di grandezza nO(1) (costo costante ammortizzato)O(log(n))O(1)
A priori direi "Ok le liste quindi le usi solo per fare degli elenchi visto che inserire elementi potrebbe costare di meno"
Infatti il costo di inserimento per i vettori è costante ma ammortizzato, quindi mi aspetto che l'efficienza migliore ce l'abbia una lista.
Invece no, sul mio pc almeno, la profilatura dice che il vettore è almeno 3 volte più veloce nell'inserimento di nuovi dati per n sufficientemente grande.

Pensandoci bene... Forse per le liste eccellono di più operazioni sul container come la rimozione oppure l'inserimento in una posizione specifica... può essere?
 
BAT ha detto:
...i costi che hai elencato su un vettore sono giusti solo se assumi che il vettore sia totalmente ordinato, altrimenti un vettore è solo un modo di implementare una lista!
Clicca per espandere...
considera che stavo per tornare qui per correggerlo ?, ho avuto un lapsus. Per la ricerca è O(n) per entrambi
 
Peri ha detto:
Infatti il costo di inserimento per i vettori è costante ma ammortizzato, quindi mi aspetto che l'efficienza migliore ce l'abbia una lista.
Invece no, sul mio pc almeno, la profilatura dice che il vettore è almeno 3 volte più veloce nell'inserimento di nuovi dati per n sufficientemente grande.
Clicca per espandere...
Ogni elemento che inserisci in una lista è un oggetto che viene creato e aggiunto. Ci sono costi dovuti alla singola allocazione.

Il vettore avrà già allocato N elementi, per questo motivo l'inserimento è più rapido. Mi avrebbe stupito il contrario.

Quello che valuti tu con Big-O è il limite superiore comunque, e non tieni ovviamente conto del tipo di implementazione, quindi O(1) su un vettore è diverso in termini di tempo da O(1) su una lista.

O(1) significa solo che ha un tempo di accesso costante, non che il tempo deve essere lo stesso sulla medesima operazione fatta su diverse strutture dati.
 
Il tuo benchmark va bene solo per il metodo push_back (inserimento alla fine) che è costante per le liste, ma nel caso del vector cambia enormemente quando non c’è più memoria quindi occorre allocare una nuova memoria, spostarne il contenuto, e liberare la vecchia memoria. Il tempo impiegato dalle altre operazioni cambia molto, a seconda del tipo di operazione, e quanta memoria sia allocata. Nel tuo caso non occupi molta memoria, una decina di migliaia di interi sono bazzecole.
Come regola aurea, i vector si usano quando occorre modificare solo il valore degli elementi del vettore, non la loro posizione, cancellazione e inserimento, e gli elementi devono essere letti velocemente usando il loro indirizzo. Altro grosso vantaggio dei vector è che sono thread-safe (per quello ci sono liste specializzate).
 
Pubblicità
Pubblicità
Indietro
Top