push_back per vettore, deque e liste

Question

Sto cercando di ottimizzare una routine C++. Il collo di bottiglia principale in questa routine è il push_back() di un vettore di oggetti. Ho provato ad usare un deque e ho anche provato una lista. Ma stranamente (e contrariamente alla teoria) la deque e l'implementazione delle liste funzionano molto più lentamente della controparte vettoriale.

Infatti anche clear() è molto più lento per la deque e elenca le implementazioni rispetto alla controparte vettoriale. Anche in questo caso, l'implementazione vettoriale sembra essere la più veloce mentre l'implementazione delle liste è la più lenta.

Eventuali suggerimenti?

Nota: vector reserve() potrebbe avere accelerato l'implementazione ma non può essere eseguito in quanto non è noto nelle dimensioni.

Grazie.

Answer 1

Stai respingendo gli oggetti stessi o un puntatore a loro? I puntatori di solito saranno molto più veloci dato che sono solo 4-8 byte da copiare, rispetto a qualunque sia la dimensione degli oggetti.

Answer 2

È necessario fornire ulteriori informazioni sul comportamento della routine.

In un punto sei preoccupato per la velocità di push_back() in un altro sei preoccupato per clear(). Stai costruendo il contenitore, facendo qualcosa e poi scaricandolo?

I risultati si vedono per clear() sono perché vector<> Basta rilasciare un blocco singl della memoria, deque<> deve rilasciare diversi, e list<> deve rilasciare una per ogni elemento.

Answer 3

Deque ha una struttura più complessa del vettore e le differenze di velocità tra i due dipenderanno pesantemente dall'implementazione specifica e dal numero effettivo di elementi respinti, ma per grandi quantità di dati dovrebbe essere più veloce. clear() può essere più lento perché può scegliere di sbarazzarsi delle strutture sottostanti più complesse. Lo stesso vale per la lista.

Answer 4

vettore essere più veloce da compilare o cancellare rispetto a deque o lista è da aspettarsi; è una struttura dati più semplice.

Per quanto riguarda la vector::push_back, si ha a che fare due cose:

1. controllo del vettore è abbastanza grande per detengono il nuovo elemento.
2. inserire il nuovo elemento.

Generalmente è possibile velocizzare le operazioni eliminando il passaggio 1 semplicemente ridimensionando il vettore e utilizzando operator[] per impostare gli elementi.

UPDATE: Il poster originale ha richiesto un esempio. Il seguente codice volte 128 mega inserimenti e uscite

push_back   : 2.04s 
reserve & push_back : 1.73s 
resize & place  : 0.48s 

quando compilato ed eseguito con g ++ -O3 su Debian/Lenny su una vecchia macchina P4.

#include <iostream> 
#include <time.h> 
#include <vector> 

int main(int,char**) 
{ 
    const size_t n=(128<<20); 

    const clock_t t0=clock(); 
    { 
    std::vector<unsigned char> a; 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t1=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.reserve(n); 
    for (size_t i=0;i<n;i++) a.push_back(i); 
    } 
    const clock_t t2=clock(); 
    { 
    std::vector<unsigned char> a; 
    a.resize(n); 
    for (size_t i=0;i<n;i++) a[i]=i; 
    } 
    const clock_t t3=clock(); 

    std::cout << "push_back   : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 
    std::cout << "resize & place  : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl; 

    return 0; 
} 

Answer 5

Per quanto riguarda push_back() è lento e riserva di essere di alcun aiuto, la realizzazione di STL utilizzato in MSVC funziona in questo modo: Quando si crea un vettore si riserva spazio per credo 10 elementi. Da quel momento in poi, quando si riempie, riserva spazio per 1,5 volte il numero di elementi nel vettore. Quindi, qualcosa come 10, 15, 22, 33, 49, 73, 105, 157 ... Le ridistribuzioni sono costose.

Anche se non si conosce la dimensione esatta, reserve() può essere utile. reserve() non impedisce al vettore di crescere se necessario. Se prenoti() e il vettore cresce oltre quella dimensione, hai comunque migliorato le cose a causa della riserva. Se il vettore risulta essere molto più piccolo, beh, forse va bene perché le prestazioni in generale funzionano meglio con dimensioni più piccole.

È necessario il profilo in modalità RELEASE per sapere con certezza quale strategia funziona meglio.

Answer 6

Se non si conosce il numero di oggetti da aggiungere, è molto difficile trovare una soluzione ottimale. Tutto quello che puoi fare è cercare di minimizzare il costo che sai che sta accadendo - che in questo caso è che il tuo vettore viene costantemente ridimensionato.

Si potrebbe fare in due modi;

1) Dividere l'operazione in costruzione e finalizzazione. Qui è dove si costruisce la lista in un vettore che è garantito essere abbastanza grande e una volta fatto copiarlo su un altro vettore.

E.g.

std::vector<Foo> hugeVec; 
hugeVec.reserve(1000); // enough for 1000 foo's 

// add stuff 

std::vector<Foo> finalVec; 
finalVec = hugeVec; 

2) In alternativa, quando il vettore è riserva integrale chiamata con sufficiente per un altro set di oggetti;

if (vec.capacity() == vec.size()) 
    vec.reserve(vec.size() + 16); // alloc space for 16 more objects 

Si poteva scegliere un contenitore diverso che non ha provocato in tutti gli elementi che vengono copiati su un ridimensionamento, ma il collo di bottiglia può quindi diventare le singole allocazioni di memoria per i nuovi elementi.

Answer 7

Se si desidera che il vettore sia veloce, è necessario riservare() spazio sufficiente. Fa un'enorme differenza, perché ogni crescita è terribilmente costosa. Se non lo sai, fai una buona ipotesi.

Answer 8

"push_back()" può essere lento se la copia di un oggetto è lenta. Se il costruttore predefinito è veloce e hai un modo di usare swap per evitare la copia, potresti avere un programma molto più veloce.

void test_vector1() 
{ 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi); // copy of a large object 
    } 
} 

void test_vector2() 
{ 
    vector<int> vi0; 
    vector<vector<int> > vvi; 
    for(size_t i=0; i<100; i++) 
    { 
     vector<int> vi(100000, 5); 
     vvi.push_back(vi0); // copy of a small object 
     vvi.back().swap(vi); // swap is fast 
    } 
} 

Risultati:

VS2005-debug 
* test_vector1 -> 297 
* test_vector2 -> 172 

VS2005-release 
* test_vector1 -> 203 
* test_vector2 -> 94 

gcc 
* test_vector1 -> 343 
* test_vector2 -> 188 

gcc -O2 
* test_vector1 -> 250 
* test_vector2 -> 156 

Answer 9

Devi scegliere il vostro contenitore in base a ciò che si sta andando a che fare con esso.

Le azioni rilevanti sono: estensione (con push), inserimento (potrebbe non essere necessario affatto), estrazione, cancellazione.

A cplusplus.com, c'è una panoramica molto buona delle operazioni per tipo di contenitore.

Se l'operazione è push -bound, ha senso che il vettore batte tutti gli altri. La cosa buona di deque è che assegna blocchi fissi, quindi farà un uso più efficiente della memoria frammentata.