std :: map e performance, insiemi intersecanti

StackOverflow https://stackoverflow.com/questions/1056244

  •  20-08-2019
  •  | 
  •  

Domanda

Sto intersecando alcune serie di numeri e lo sto facendo memorizzando un conteggio ogni volta che vedo un numero in una mappa.

Trovo che le prestazioni siano molto lente.

Dettagli: - Uno dei set contiene 150.000 numeri - L'intersezione di quel set e un altro set richiede circa 300 ms la prima volta e circa 5000 ms la seconda volta - Non ho ancora creato alcun profilo, ma ogni volta che interrompo il debugger mentre faccio l'intersezione è in malloc.c!

Quindi, come posso migliorare questa prestazione? Passare a una struttura dati diversa? Alcuni come migliorare le prestazioni di allocazione della memoria della mappa?

Aggiornamento:

  1. Esiste un modo per chiedere std :: map o boost :: unordered_map da pre-allocare un po 'di spazio?
  2. Oppure, ci sono dei consigli per usarli in modo efficiente?

Update2:

Vedi Contenitore C ++ veloce come C # HashSet < !> lt; T <> gt!; e Dizionario < K, V > ;?

Aggiornamento3:

Ho confrontato set_intersection e ho ottenuto risultati orribili: 

(set_intersection) Found 313 values in the intersection, in 11345ms
(set_intersection) Found 309 values in the intersection, in 12332ms

Codice: 

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}
È stato utile?

Soluzione 9

Ho capito qualcosa: se allego il debugger a build RELEASE o DEBUG (ad esempio, premi F5 nell'IDE), ottengo momenti orribili.

Altri suggerimenti

Dovresti assolutamente usare vettori preallocati che sono molto più veloci. Il problema con l'intersezione di set con set di stl è che ogni volta che passi all'elemento successivo stai inseguendo un puntatore allocato dinamicamente, che potrebbe facilmente non essere nella cache della CPU. Con un vettore l'elemento successivo sarà spesso nella cache perché è fisicamente vicino all'elemento precedente.

Il trucco con i vettori è che se non preallocate la memoria per un'attività come questa, eseguirà ANCORA PEGGIORE perché continuerà a riallocare la memoria mentre si ridimensiona durante la fase di inizializzazione.

Prova qualcosa del genere instabile: sarà MODO più veloce. 

int runIntersectionTestAlgo() { 

vector<char> vector1; vector1.reserve(100000);
vector<char> vector2; vector2.reserve(1000);

// Create 100,000 values for set1
for ( int i = 0; i < 100000; i++ )    {
    int value = 1000000000 + i;
    set1.push_back(value);
}

sort(vector1.begin(), vector1.end());

// Create 1,000 values for set2
for ( int i = 0; i < 1000; i++ )    {
    int random = rand() % 200000 + 1;
    random *= 10;
    int value = 1000000000 + random;
    set2.push_back(value);
}

sort(vector2.begin(), vector2.end());

// Reserve at most 1,000 spots for the intersection
vector<char> intersection; intersection.reserve(min(vector1.size(),vector2.size()));
set_intersection(vector1.begin(), vector1.end(),vector2.begin(), vector2.end(),back_inserter(intersection));

return intersection.size(); 
}

Senza saperne di più sul tuo problema, " verifica con un buon profiler " è il miglior consiglio generale che posso dare. Oltre quello ...

Se l'allocazione di memoria è il tuo problema, passa a una sorta di allocatore in pool che riduce le chiamate a malloc. Boost ha un numero di allocatori personalizzati che dovrebbero essere compatibili con std::allocator<T>. In effetti, potresti anche provare questo prima di creare un profilo, se hai già notato che i campioni di debug-break finiscono sempre in vector.

Se lo spazio dei numeri è noto per essere denso, è possibile passare a un'implementazione basata su bitset - o <=>, utilizzando i numeri come indici nel vettore.

Se il tuo spazio numerico è per lo più scarso ma ha un certo raggruppamento naturale (questo è un grande se ), puoi passare a una mappa di vettori. Utilizzare bit di ordine superiore per l'indicizzazione della mappa e bit di ordine inferiore per l'indicizzazione vettoriale. Funzionalmente è molto simile al semplice utilizzo di un allocatore in pool, ma è probabile che ti dia un migliore comportamento di memorizzazione nella cache. Questo ha senso, dal momento che stai fornendo più informazioni alla macchina (il clustering è esplicito e compatibile con la cache, piuttosto che una distribuzione casuale che ti aspetteresti dall'allocazione del pool).

Seguirei il suggerimento di ordinarli. Esistono già algoritmi di set STL che operano su intervalli ordinati (come set_intersection, set_union, ecc.):

set_intersection

Non capisco perché devi usare una mappa per fare l'intersezione. Come hanno detto le persone, potresti mettere i set in std::set e quindi usare std::set_intersection().

Oppure puoi inserirli in hash_set. Ma poi dovresti implementare l'intersezione manualmente: tecnicamente devi solo mettere uno degli insiemi in <=>, quindi scorrere l'altro e testare se ogni elemento è contenuto in <=>.

L'intersezione con le mappe è lenta, prova un hash_map . (tuttavia, ciò non è previsto in tutte le implementazioni STL.

In alternativa, ordina entrambe le mappe e fallo in modo simile all'unione.

Qual è il tuo algoritmo di intersezione? Forse ci sono alcuni miglioramenti da apportare?

Ecco un metodo alternativo

Non so che sia più veloce o più lento, ma potrebbe essere qualcosa da provare. Prima di farlo, raccomando anche di utilizzare un profiler per assicurarti di lavorare davvero sull'hotspot. Modifica invece le serie di numeri che stai intersecando per utilizzare std::set<int>. Quindi scorrere il più piccolo guardando ogni valore che trovi. Per ogni valore nel set più piccolo, usa il metodo find per vedere se il numero è presente in ciascuno degli altri set (per prestazioni, cerca dal più piccolo al più grande).

Questo è ottimizzato nel caso in cui il numero non venga trovato in tutti i set, quindi se l'intersezione è relativamente piccola, potrebbe essere veloce.

Quindi, memorizza l'intersezione in std::vector<int> invece - anche l'inserimento usando push_back è molto veloce.

Ecco un altro metodo alternativo

Cambia le serie di numeri in std::sort e usa std::binary_search per ordinare dal più piccolo al più grande. Quindi usa std::set per trovare i valori, usando approssimativamente lo stesso metodo di cui sopra. Questo potrebbe essere più veloce della ricerca di <=> poiché l'array è più stretto nella memoria. In realtà, non importa, puoi semplicemente scorrere i valori in blocco, osservando quelli con lo stesso valore. Incrementa solo gli iteratori che sono inferiori al valore minimo visualizzato nel passaggio precedente (se i valori erano diversi).

Potrebbe essere il tuo algoritmo. A quanto ho capito, stai girando su ogni set (che spero sia un set standard) e li lanci in un'altra mappa. Questo sta facendo un sacco di lavoro che non devi fare, poiché le chiavi di un set standard sono già in ordine. Invece, prendi un & Quot; merge-sort & Quot; come approccio. Gira su ogni iter, dereferenziando per trovare il min. Contare il numero che ha quel minimo e incrementare quelli. Se il conteggio era N, aggiungilo all'intersezione. Ripeti fino alla fine della prima mappa (se confronti le dimensioni prima di iniziare, non dovrai controllare ogni fine di ogni mappa ogni volta).

Risposta all'aggiornamento : esistono facoltà di accelerare l'allocazione della memoria prenotando anticipatamente lo spazio, come boost :: pool_alloc . Qualcosa del tipo: 

std::map<int, int, std::less<int>, boost::pool_allocator< std::pair<int const, int> > > m;

Ma onestamente, malloc è abbastanza bravo in quello che fa; Farei un profilo prima di fare qualcosa di troppo estremo.

Guarda i tuoi algoritmi, quindi scegli il tipo di dati corretto. Se hai un comportamento simile a un set e vuoi fare intersezioni e simili, std::set è il contenitore da usare.

Poiché i suoi elementi sono memorizzati in modo ordinato, l'inserimento può costare O (log N), ma l'intersezione con un altro (ordinato!) <=> può essere fatta in tempo lineare.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top