Il costo dell'utilizzo di std :: map con std :: string keys vs int keys?

Question

So che le singole mappa query prendere un massimo di log (N) tempo. Comunque mi stavo chiedendo, ho visto molti esempi che usano le stringhe come chiavi della mappa. Qual è il costo delle prestazioni di associare uno std :: string come chiave ad una mappa invece di un int, ad esempio?

std::map<std::string, aClass*> someMap; vs std::map<int, aClass*> someMap;

Grazie!

Answer 1

Oltre alla complessità tempo dal confronto stringhe già citate, una chiave stringa sarà anche causare una dotazione di memoria aggiuntiva ogni volta che un elemento viene aggiunto al contenitore. In alcuni casi, ad es. sistemi altamente paralleli, un mutex allocatore globale può essere una fonte di problemi di prestazioni.

In generale, si dovrebbe scegliere l'alternativa che rende più senso nella vostra situazione, e ottimizzare solo a seguito di prestazioni effettive. È notoriamente difficile giudicare quale sarà un collo di bottiglia.

Answer 2

La differenza di costo saranno collegati alla differenza di costo tra il confronto di due interi contro il confronto di due stringhe.

Quando si confrontano due stringhe, è necessario dereference un puntatore per raggiungere i primi caratteri, e confrontarli. Se sono identici, devi confrontare i secondi caratteri e così via. Se le tue stringhe hanno un prefisso comune lungo, questo può rallentare un po 'il processo. È molto improbabile che sia veloce come confrontare gli interi.

Answer 3

Il costo è naturalmente che gli interi possono essere confrontati in tempo reale O (1) mentre le stringhe vengono confrontate in tempo O (n) (n è il prefisso condiviso massimo). Inoltre, la memorizzazione delle stringhe occupa più spazio di quella degli interi. Oltre a queste apparenti differenze, non ci sono grandi costi di performance.

Answer 4

L'analisi degli algoritmi per le prestazioni asintotiche sta lavorando sulle operazioni da eseguire e sul costo aggiunto all'equazione. Per questo è necessario prima sapere quali sono le operazioni eseguite e quindi valutarne i costi.

La ricerca di una chiave in un albero binario bilanciato (quali mappe sono) richiede operazioni complesse O(log N). Ognuna di queste operazioni implica il confronto tra la chiave per una corrispondenza e il puntatore appropriato (figlio) se la chiave non corrisponde. Ciò significa che il costo complessivo è proporzionale a log N volte il costo di queste due operazioni. Seguendo puntatori è un'operazione costante di tempo O(1), e tasti confrontando dipendono dalla chiave. Per una chiave intera, i confronti sono veloci O(1). Confronto di due stringhe è un'altra storia, ci vuole tempo proporzionale alle dimensioni delle stringhe coinvolte O(L) (dove ho usato intenzionalmente L come lunghezza della stringa parametro al posto del più comune N.

Quando si somma tutto il costa fino ad ottenere che l'utilizzo di numeri interi come chiavi il costo totale è di O(log N)*(O(1) + O(1)) che è equivalente a O(log N). (O(1) viene nascosto nella costante che la notazione O nasconde in silenzio.

Se si utilizza stringhe come chiavi, il costo totale è O(log N)*(O(L) + O(1)) dove l'operazione a tempo costante ottiene hidde n dall'operazione lineare più costosa O(L) e può essere convertita in O(L * log N). Cioè, il costo di localizzare un elemento in una mappa digitato da stringhe è proporzionale al logaritmo del numero di elementi memorizzati nella mappa moltiplicato per la lunghezza media delle stringhe utilizzate come chiavi.

Si noti che la notazione O grande è più appropriata da utilizzare come strumento di analisi per determinare come si comporta l'algoritmo quando la dimensione del problema aumenta, ma nasconde molti fatti sottostanti che sono importanti per le prestazioni non elaborate.

Come esempio più semplice, se si modifica la chiave da una stringa generica a una matrice di 1000 caratteri è possibile nascondere tale costo all'interno della costante scartata dalla notazione. Confrontare gli array di 1000 caratteri è un'operazione costante che richiede solo un po 'di tempo. Con la notazione asintotica che sarebbe solo una operazione O(log N), come con numeri interi.

Lo stesso accade con molti altri costi nascosti, come il costo di creazione degli elementi che viene solitamente considerato come un'operazione a tempo costante, solo perché non dipende dai parametri del problema (il costo di localizzazione del blocco di memoria in ciascuna assegnazione non dipende set di dati, ma piuttosto sulla frammentazione memoria che è al di fuori della portata dell'analisi algoritmo, il costo di acquisizione serratura interna malloc da garantire che non due processi cercano di restituire stesso blocco di memoria dipende dalla tesi della serratura che si dipende numero di processori, processi e la quantità di memoria richieste eseguono ..., di nuovo fuori della portata dell'analisi algoritmo). Quando leggi i costi nella notazione O grande devi essere consapevole di cosa significhi veramente.

Answer 5

Prima di tutto, dubito che in un'applicazione reale, se si dispone di chiavi di stringa o chiavi int fa alcuna differenza notevole. La profilazione della tua applicazione ti dirà se è importante.

Se lo fa materia, si potrebbe cambiare la vostra chiave per essere qualcosa di simile (non testata):

class Key { 
public: 
    unsigned hash; 
    std::string s; 

    int cmp(const Key& other) { 
     int diff = hash - other.hash; 
     if (diff == 0) 
      diff = strcmp(s, other.s); 
     return diff; 
} 

Ora si sta facendo un confronto int sulle hash di due stringhe. Se gli hash sono diversi, le stringhe sono sicuramente diverse. Se gli hash sono uguali, devi comunque confrontare le stringhe a causa dello Pigeonhole Principle.

Answer 6

esempio semplice con solo l'accesso ai valori in due mappe con uguale numero di tasti - tasti di un int altre stringhe degli stessi valori int prende 8 volte più a lungo con le stringhe.