Una domanda riguardante la lista collegata rispetto al vettore inserisce / rimuove il confronto dei risultati

Prima di tutto, congratulazioni per aver fatto la cosa giusta e misurare piuttosto che aver creduto nel consiglio sull'efficienza! Con la moderna architettura dei computer, è più difficile che mai prevedere in che modo un piccolo cambiamento nelle strutture di dati influirà sui tempi di esecuzione, a causa dei molti livelli della gerarchia di memoria, dell'esecuzione fuori ordine, degli ottimizzatori di codice aggressivi, ecc. è davvero quello che hai misurato, allora sì, starai meglio con una lista.

Detto questo, quel programma non fa molto; in pratica quasi certamente accederai agli elementi più spesso di quanto li aggiungi o li elimini, e probabilmente in modi non successivi. Sospetto che se si rieseguano i benchmark con molti accessi casuali, i risultati potrebbero cambiare, ma ... ricorda cosa ho appena detto? Mai presumo. Misura sempre. Buona profilazione!

Il titolo di quell'articolo è intenzionalmente falso. L'autore sta facendo tre punti: che gli attraversamenti di liste concatenate e le ricerche sono lenti, il che è vero, che molte persone non si rendono conto quanto più sono più lente delle ricerche di array lineari a causa di errori di cache, che è probabilmente vero e la maggior parte delle persone non prende in considerazione il tempo di ricerca quando seleziona un elenco collegato, che è probabilmente falso.

Il suo programma di riferimento include il tempo di ricerca insieme a aggiunte e cancellazioni, che è la parte non corretta. Quando seleziono una lista collegata, la prima cosa che mi chiedo è se il tempo di ricerca scarso può essere risolto o se si tratta di un compromesso accettabile. Penso che sia vero per molte persone.

Ad esempio, l'ultima volta che ho usato un elenco collegato è stato quando avevo bisogno di mantenere alcuni elementi ordinati in base al loro ultimo accesso. L'operazione più comune di gran lunga stava spostando un elemento dal centro della lista in primo piano, un'operazione O (1) per un elenco collegato. Tuttavia, c'è quel fastidioso tempo di ricerca. Risultò conveniente memorizzare un puntatore al nodo dell'elenco collegato in un'altra struttura di dati di cui avevo bisogno in ogni caso, quindi anche le ricerche sarebbero O (1).

Tuttavia, in altre circostanze, ho appena tenuto le ricerche O (n) perché la semantica di un elenco collegato ha semplificato il codice e il risultato della performance era trascurabile. Il tuo test mostra la differenza misurata in centesimi di secondo per aggiungere o eliminare 4000 nodi. Per la maggior parte delle applicazioni che è completamente impercettibile.

Il fatto che tu abbia ottenuto risultati diversi rispetto all'autore sul suo benchmark è anche molto interessante, e illustra bene perché dovresti fare le tue misurazioni. Il tuo compilatore, sistema operativo e implementazione della libreria standard, e anche gli altri processi in esecuzione sul tuo sistema, possono fare una differenza significativa in cose come il numero di mancate cache che il tuo codice genererà.

Prima un suggerimento: probabilmente vorresti aspettare più di un paio di minuti prima di accettare una risposta: probabilmente otterrai più risposte in questo modo.

Secondo: durante il benchmarking, dovresti sempre compilare con le ottimizzazioni attivate. Qualcosa come g++ -std=c++11 -O3 -march=native dovrebbe darti dei buoni risultati.

std::list è davvero una struttura di dati scadente e non ho ancora trovato una situazione in cui sia la migliore. Ad esempio, si consideri il caso in cui si desidera mantenere una struttura di dati ordinati. Potresti pensare che std::list , con O(1) di inserimento e tempo di cancellazione sarebbe l'ideale, ma in realtà è sub-ottimale!

Per questi test, il mio tipo contenuto è una classe banale che contiene una matrice di numeri interi a 4 byte. Provo un std::array delle dimensioni 1, 10 e 100 (dandomi una dimensione dell'elemento di 4, 40 e 400). Ho scelto un std::array perché una mossa e una copia sono la stessa cosa. L'elemento iniziale dell'array viene inizializzato su un numero casuale compreso tra 0 e std::numeric_limits<uint32_t>::max() . Creo un std::vector di un certo numero di questi (l'asse x), quindi avvio il timer. Eseguo il test di iterazione su quel std::vector per ogni elemento e inserendolo nell'ordine (come ordinato dal primo elemento nell'array, utilizzando operator<= ). Per evitare qualsiasi intelligente ottimizzazione del compilatore di rimuovere qualsiasi lavoro, ho quindi emesso il primo elemento del contenitore ordinato (che non può essere determinato fino alla fine) per alcuni file e interrompere il timer.

Questi sono i miei risultati per varie dimensioni di elementi:

Vediamocheperglielementia4e40byte,std::vectorèmiglioreancheaquestoinserimentonelmezzodistd::list,eperqualsiasidimensionedielementostaimegliousandounstd::vector<unique_ptr>distd::list.

Ingenerale,nonriescoatrovareunmotivoperusarestd::listsuunaclassecheavvolgestd::vector<std::unique_ptr>perfarlaapparirecomeseavessesemanticadelvalore,oltreallapossibilitàdicopiare(chesperodirisolvereconoinviandounaclassevalue_ptraBoostsenonnevieneaggiuntaunapresto,anchesec'èunadiscussioneariguardo).

Comenotaaggiuntiva,sesitrattassedicodicereale,nondiungiocodiconfronto/benchmark,avreiscrittolaversionestd::vectorinmodomoltopiùdiverso.Avreicopiatol'interocontenitoreoriginaledirettamente,quindihousatostd::sort.Intendoscrivereun'analisipiùcompletasullestrutturedeidati,conparticolareattenzioneall'importanzadellalocalizzazionedeidati,eincluderòitempisulmodo"corretto" di farlo. (la versione corretta fa saltare tutti gli altri metodi fuori dall'acqua, completando in meno di un secondo 400.000 elementi di dimensione 400, che è 10 volte più elementi di quelli testati nei miei grafici).

Spero di aver spiegato tutto bene; questi sono alcuni test che ho eseguito diversi mesi fa e non ho ancora finito i miei appunti sull'argomento.

I test sono stati eseguiti su una macchina Intel i5 con 4 GB di RAM. Credo che stavo usando Fedora 17 x64.