I vettori in C++ sono così lenti?

Question

Sto creando un programma che risolve questo problema qui: http://opc.iarcs.org.in/index.php/problems/BOOKLIST

e gli unici posti che sto usando vettori sono:

for(int i =0;i < total_books; i++){ 
    int temp; 
    cin >> temp; 
    books_order.push_back(temp); 
} 

e

for(int i = 0;i < total_entries; i++){ 
    int index; 
    cin >> index; 
    index--; 
    cout << books_order[index] << endl; 
    books_order.erase(books_order.begin()+index); 
} 

(qui è il mio codice completo: http://cpaste.org/1377/)

Le uniche funzioni che utilizzo dai vettori sono vector :: erase, vector :: push_ba ck e vector :: begin. Per i grandi input il mio codice impiega più tempo di 3 secondi (che è il limite di tempo per quel problema), ma quando rimuovo la funzione vettoriale, viene eseguito molto più velocemente (ma dà una risposta errata)

Ho capito che è sbagliato usare i vettori in questo problema e il mio algoritmo è molto lento, ma non ho capito perché è lento.

Se sai perché le funzioni che sto usando sono lente, spiegamele. Grazie.

Answer 1

Le uniche funzioni sto usando da vettori sono vector :: erase, vector :: push_back e vector :: comincio

direi che questo è il vostro problema. vector::erase è O(n), gli altri sono costanti e non dovrebbero causare problemi di efficienza nei problemi di giudice online. Evitare il metodo di cancellazione.

Tuttavia, in generale, se si conoscono le dimensioni dell'array in anticipo, utilizzare semplicemente un array semplice. Non aggiungere sovraccarichi inutili se puoi aiutarlo.

Per risolvere il problema a cui ci si è collegati, prendere in considerazione l'utilizzo di set: il suo metodo di cancellazione è O(log n), come i suoi metodi di inserimento. Questo è quello che dovresti usare in generale se hai bisogno di rimozioni casuali.

Modifica: Ho dimenticato che anche C++ aveva priority queues, quindi guarda anche quelli. Dato che ti interessa solo il massimo qui, potrebbe essere più veloce di un set, anche se entrambi hanno le stesse complessità teoriche (un heap può recuperare il minimo/massimo in O(1), ma rimuoverlo, cosa che devi fare per questo problema , è O(log n)) in questo caso, e uno dovrebbe funzionare bene.

Answer 2

A meno che non abbiate chiamato reserve per dimensionare il vettore sul numero di elementi che avete, le chiamate a push_back riassegneranno la memoria ogni volta che la nuova dimensione supererà la capacità vettoriale. Prendi in considerazione l'utilizzo di reserve per allocare memoria sufficiente per i tuoi elementi e dovresti vedere un aumento delle prestazioni, in particolare se il vettore è di grandi dimensioni. Presta attenzione anche alle altre risposte riguardanti l'uso di erase.

Answer 3

La rimozione di elementi dal centro di un vettore (con vector::erase) è lenta. Questo perché tutti gli elementi superiori del vettore devono essere spostati verso il basso per riempire lo spazio lasciato dall'elemento che hai rimosso.

Quindi, questo non è un caso in cui i vettori sono lenti, ma l'algoritmo è lento perché hai scelto una struttura di dati inappropriata.

Answer 4

Se si sa che il vettore ha un certo numero di elementi in in anticipo è possibile prenotare uno spazio sufficiente per contenere tutto per salvare se stessi riallocazioni di spazio all'interno del vettore:

books_order.reserve(total_books) 
for(int i=0 ;i < total_books; ++i){ 
    int temp; 
    cin >> temp; 
    books_order.push_back(temp); 
} 

Tuttavia non è questo il problema qui, sono sicuro che se hai profilato il tuo codice vedresti un grande overhead dall'utilizzo dello .erase(). La rimozione di elementi dal centro di un vettore è lenta a causa di come viene implementato un vettore che dovrà spostare tutti gli elementi in parte quello rimosso. Considera invece l'utilizzo di una struttura dati diversa, ad esempio std::array.

Answer 5

IMO il colpevole è vector::erase poiché sposterà tutti gli elementi dopo quello rimosso. Quindi, a meno che non rimuovi sempre l'ultimo elemento, può essere piuttosto lento.

Answer 6

Hai davvero bisogno di un vettore per ottenere ciò che stai facendo?

Devi tenere a mente come funzionano i vettori: sono essenzialmente matrici dinamiche che si ridimensionano man mano che aggiungi più elementi al loro interno. Il ridimensionamento di un vettore è un'operazione O (n) (dove n è il numero di elementi nel tuo vettore) poiché assegna nuova memoria e copia gli elementi sul nuovo vettore.

È possibile leggere quali sono i vettori validi su here.

Ti consiglio di utilizzare una matrice standard invece - che sembra del tutto plausibile dal momento che già sapete quanti elementi totale ci sono (che è total_books)

Answer 7

il vostro problema è la chiamata a "cancellare". Se si controlla la documentazione here, noterete che:

Perché vettori mantenere un formato di array, cancellando su posizioni diverse da fine vettore si sposta anche tutti gli elementi dopo il segmento cancellati nelle loro nuove posizioni, che può non essere un metodo efficiente quanto cancellare in altri tipi di contenitori di sequenza (deque, list).

o eseguire il ciclo dalla fine o cancellare dopo il ciclo.