In un libro di programmazione C++ ho visto quanto segue per un std::list iteratore:Non sta chiamando `lista <T> :: end()` inefficiente?
for (iterator = list.start(); iterator != list.end(); iterator++)
Non è inefficiente per chiamare list.end() tutto il tempo? Sarebbe meglio salvare la fine in un'altra variabile o il compilatore C++ (cioè g ++) si occuperà automaticamente di questo?
È improbabile che la chiamata a std::list<T>::end() rappresenti un grosso problema di efficienza e probabilmente legge solo un singolo valore. Tuttavia, si darebbe al compilatore un suggerimento che non è destinato a cambiare memorizzandolo come variabile. Per altri contenitori può essere coinvolto un calcolo oltre alla lettura di un indirizzo di base che è un po 'più coinvolto. Ancora niente di drammatico, ma forse vale la pena di essere evitato.
Nota, tuttavia, che può anche cambiare la semantica del ciclo: se il corpo del ciclo può aggiungere elementi, l'estremità precedente può spostarsi. È interessante notare che non trovo alcun requisito specifico nella norma che affermi se std::list<T>::end() può cambiare quando si inseriscono elementi nel contenitore (posso immaginare implementazioni in cui cambia e altre in cui non lo fa, molto probabilmente non cambia , anche se). Se si desidera ottenere un comportamento garantito quando si modifica anche l'elenco, è possibile chiamare lo list.end() in ogni iterazione.
BTW, c'è un problema di prestazioni più grande che avrei sull'utilizzo di iterator++ anziché ++iterator, in particolare questo è davvero ciò che l'autore ha utilizzato nel libro. Tuttavia, questa è una micro ottimizzazione come la memorizzazione del risultato di list.end() ma uno da fare a poco prezzo.
"Non trovo requisiti specifici nello standard che dichiarino se' std :: list
Ciò che impedisce all'implementazione di avere 'end()' puntare su un oggetto mezzo cotto che viene inizializzato con il nuovo valore all'inserimento di un elemento alla fine? L'iteratore rimane valido ma non punta più alla fine e non c'era alcun oggetto in questa posizione prima, quindi nessun riferimento o puntatore non è più valido. Come succede, questo è il modo in cui 'std :: vector
Punto giusto. Fuori interesse, se ho un iteratore che * non è * un iteratore finale, e lo inserisco prima, cosa dice che in seguito non punta all'oggetto appena inserito? Anche con una capacità sufficiente, 'vector :: insert' invalida gli iteratori e i riferimenti dopo il punto di inserimento, quindi il non-requisito per il vecchio iteratore finale di essere ancora un iteratore finale è ovvio. –
list::end() dovrebbe avere una complessità di tempo costante e in particolare per gli elenchi collegati significa che è probabilmente molto efficiente.
Potrebbe essere leggermente più efficiente archiviare il valore se il proprio algoritmo lo consente (anche in questo caso è improbabile che la differenza sia grande per le liste specialmente collegate).
Oh, e leggete la risposta di Steve Jessop sul testare l'efficienza da soli!
http://www.cplusplus.com/reference/stl/list/end/ - Controllo le cose lì, vedi "Complessità". – Shi
@Shi, si noti che la complessità "costante" non significa una non operazione. In particolare i vettori probabilmente aggiungono puntatore all'interno del loro rispettivo 'end()'; gli elenchi probabilmente non lo sono (come ho detto) –
La complessità costante richiede ancora del tempo e, a seconda del proprio STL, dell'implementazione, del contenitore scelto, ecc. (in particolare dei contenitori non STL), potrebbe essere una quantità significativa di tempo. – ssube
In pratica, per i contenitori STL, container::end() è estremamente economico. In effetti, lo standard C++ impone la complessità algoritmica per diversi metodi di più classi (se non per tutti) e container::end() è sempre costante.
Inoltre, il compilatore è libero di incorporare tali metodi, rimuovendo essenzialmente qualsiasi sovraccarico che potrebbe avere. Non riesco a pensare a nessun altro modo per ottenere la fine di un elenco in tempo costante rispetto alla memorizzazione, quindi la tua chiamata list.end() probabilmente finisce per essere un accesso al campo, che non è più costoso su piattaforme x86 che memorizzarlo nello stack.
Il tuo chilometraggio può variare con altre raccolte, ma è una scommessa sicura che list.end() non finirà per essere il collo di bottiglia.
È improbabile che faccia alcuna differenza.
Le funzioni del contenitore standard vengono allineate, pertanto non è necessario richiamare la funzione in questione. Ciò che rimane è se l'ottimizzatore è abbastanza intelligente da evitare un sovraccarico non necessario che non è strettamente necessario per eseguire il confronto. Ad esempio: crea effettivamente un oggetto temporaneo list::iterator, compila il suo campo di posizione corrente e quindi legge di nuovo il campo, oppure il confronto finisce come un confronto tra un valore di un valore da iterator e un valore nella testa del elenco?
Anche se vi è un sovraccarico non necessario, potrebbe essere trascurabile rispetto all'incremento dell'iteratore e ancora più trascurabile rispetto al corpo del loop.
Si potrebbe testarlo, che è più affidabile di indovinare. Ricorda di abilitare l'ottimizzazione: testare le prestazioni senza ottimizzazione è come dire che Blake deve essere più veloce di Bolt se Blake cammina più velocemente dalla pista di riscaldamento al bus.
Generalmente, no, non è inefficiente. end() sarà in genere una funzione inline e il compilatore genererà un buon codice per fare qualsiasi cosa. Più precisamente, inefficiente rispetto a cosa? Sì, è possibile aggiungere codice per creare una variabile per contenere il risultato, e questo potrebbe o non potrebbe essere un po 'più veloce del semplice chiamare end(). Sembra molto improbabile che un tale cambiamento possa fare una grande differenza di velocità per trasformare un programma troppo lento in uno che soddisfa i requisiti.
Se è necessario ottimizzare il micro, sì.
In generale, chiamare list.end() non avrà una penalizzazione delle prestazioni significativa e probabilmente non sarà un problema. Può restituire lo stesso valore per ogni chiamata, può essere in linea e così via. Mentre non è lento, ci vuole un po 'di tempo.
Se è assolutamente necessaria la velocità, si desidera utilizzare for (iterator = list.start(), end = list.end; iteration != end; ++iterator). Questo memorizza l'iteratore finale (e fa un pre-inc), e non dovrebbe avere chiamate ripetute.
Il secondo tipo non è in genere necessario, ma se .end() è costoso o se il loop è molto grande, può essere utile.
Mentre l'ottimizzazione prematura è malvagia, le buone abitudini non lo sono. Se non vi aspettate il vostro stato di terminazione del ciclo di cambiare, vale a dire che non stai cambiando il contenitore, allora questo modello può essere utilizzato:
for (mylist::iterator it = alist.begin(), finish = alist.end(); it != finish; ++it)
Il compilatore è improbabile che questa ottimizzazione per voi se si può' t determinare che il contenitore non stia cambiando.
Si noti che è improbabile che ciò comporti una differenza temporanea misurabile, ma non può danneggiare.
Se il codice è in esecuzione su un sistema che è stretto per i registri o ha uno stack limitato, la creazione di variabili aggiuntive può far male. –
@PeteBecker, poiché la variabile sta sostituendo il risultato di una chiamata di funzione, penso che sia più probabile che aiutare piuttosto che far male. Potresti avere comunque ragione, è impossibile sapere senza guardare il codice generato. –
Tranne che il valore deve essere mantenuto intorno attraverso il corpo del loop; con una chiamata di funzione il risultato può essere scartato dopo essere stato utilizzato. –
Una buona ragione per non memorizzare nella cache end() su std::list è che ti impedisce di fare il seguente errore:
for (iterator = list.rstart(), end = list.rend(); iterator != end; iterator++) {
// modify list
Nessun iteratori saranno invalidate quando si apportano modifiche nel std::list, ma rend NON è una sentinella (punta al primo elemento della lista underying), il che significa che smetterà di essere la fine della lista se si aggiunge alla fine della lista inversa (aka anteporre all'inizio della lista non revocata).
' std :: list :: end' è la fine di una lista collegata doppiamente, quindi è s dovrebbe essere un'operazione a tempo costante. Dato che non stai aggiungendo il ciclo, un compilatore ottimizzante dovrebbe essere in grado di memorizzarlo nella cache. – oldrinb
Questo sarebbe nel regno di "ottimizzazione prematura". Preoccuparsi troppo presto può causare problemi, specialmente perché se aggiungi o rimuovi elementi all'interno del tuo loop, la fine è in grado di cambiare. Se hai isolato una parte specifica del tuo codice (che si basa su questo) come un maiale della CPU, allora con tutti i mezzi ottimizzare, ma altrimenti ci sono pesci più grandi in mare. – Wug
@Wug Se sai che '.end()' è un tempo costante, sì (e sì, so che è richiesto che sia in C++, per questo specifico contenitore). Ma per le liste che possono essere molto lunghe e il cui '.end()' è O (n), tale ottimizzazione non è affatto prematura. – delnan