Ho eseguito alcune misurazioni da quando mi sono imbattuto recentemente in questo problema.
Ho una grande mappa, con molti dati, i dati sono raramente inseriti, il 99% delle volte è solo accessibile e modificato sul posto usando i riferimenti. Tuttavia, questi dati devono essere salvati su disco e caricati di nuovo. Soluzioni come "usa una mappa non ordinata", sembrano un modo economico e poco costoso di sbagliare, la mappa ordinata era il modo giusto per me, dato che i dati sono ordinati. Unico problema stava caricando dal file.
volevo sapere qual è il vero costo di questa operazione e come accelerarlo, quindi, ho misurato:
// Example program
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <time.h>
std::vector<int> amount = {100, 1000, 10000, 100000, 1000000, 5000000};
int main()
{
for(int j=0; j<amount.size(); j++)
{
clock_t tStart = clock();
std::map<int,int> mymap;
for(int i=0; i<amount[j]; i++){
mymap[i] = i;
}
printf("Time taken []: %.2fs\n", (double)(clock() - tStart));
}
for(int j=0; j<amount.size(); j++)
{
clock_t tStart = clock();
std::map<int,int> mymap;
mymap[0] = 0;
auto it = mymap.begin();
for(int i=1; i<amount[j]; i++){
it = mymap.insert(it, std::pair<int,int>(i,i));
}
printf("Time taken insert end()-1: %.2fns\n", (double)(clock() - tStart));
}
for(int j=0; j<amount.size(); j++)
{
clock_t tStart = clock();
std::map<int,int> mymap;
for(int i=1; i<amount[j]; i++){
mymap.insert(mymap.end(), std::pair<int,int>(i,i));
}
printf("Time taken insert end(): %.2fns\n", (double)(clock() - tStart));
}
for(int j=0; j<amount.size(); j++)
{
clock_t tStart = clock();
std::map<int,int> mymap;
for(int i=0; i<amount[j]; i++){
mymap.insert(mymap.begin(), std::pair<int,int>(i,i));
}
printf("Time taken insert begin(): %.2fs\n", (double)(clock() - tStart));
}
return 0;
}
Risultati:
Time in ns
N end()-1 end() begin() []
100 12 8 22 12
1000 77 54 188 97
10000 763 532 2550 1174
100000 7609 6042 23612 17164
1000000 75561 62048 270476 272099
5000000 362463 306412 1827807 1687904
Sommario:
SI c'è guadagno, guadagno enorme, senza alcun vero inconveniente. Estremamente migliore di una mappa non ordinata quando i dati sono ordinati, estremamente utile per il caso di salvare su un file una mappa e ricrearla.
L'ora di inserimento se il suggerimento è corretto è la stessa indipendentemente dal numero di elementi. Quindi non è necessario ricorrere a una mappa non truccata per avere un tempo costante.
Nel peggiore dei casi si potrebbe perdere alcuni se il suggerimento è il suggerimento peggiore possibile. Non vedo più niente da fare con gli inserti senza un suggerimento, specialmente se si hanno conoscenze su dove verranno inseriti i dati. E la maggior parte delle volte lo fai.
Esattamente. Nel caso in cui la chiave sia 'uint64_t' e sempre crescente, è il" suggerimento migliore "dare a' :: end() 'come suggerimento? – ritter
Scommetto che 'insert' richiede un iteratore dereferenziabile (che' end() 'non lo è), ma non ne sono assolutamente certo. –
@ eq-: No, l'iteratore di posizione deve essere solo un iteratore valido, non uno dereferenziabile. E poiché l'idea è che è una posizione che il tuo nuovo elemento molto probabilmente precede, sarebbe una specie di inutile se non consentisse end(). – abarnert