per la ricerca rapida dei nomi

Question

Voglio memorizzare le stringhe e rilasciare ciascuna un numero ID univoco (un indice andrebbe bene). Avrei solo bisogno di una copia di ogni stringa e ho bisogno di una rapida ricerca. Controllo se la stringa esiste nella tabella abbastanza spesso da notare un impatto sulle prestazioni. Qual è il miglior contenitore da usare per questo e come posso cercare se la stringa esiste?

Answer 1

Vorrei suggerire tr1 :: unordered_map. È implementato come hashmap, quindi ha una complessità prevista di O (1) per le ricerche e un caso peggiore di O (n). C'è anche un'implementazione boost se il tuo compilatore non supporta tr1.

#include <string> 
#include <iostream> 
#include <tr1/unordered_map> 

using namespace std; 

int main() 
{ 
    tr1::unordered_map<string, int> table; 

    table["One"] = 1; 
    table["Two"] = 2; 

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0; 
} 

Answer 2

suona come un array funzionerebbe perfettamente dove l'indice è l'indice nell'array. Per verificare se esiste, assicurati solo che l'indice sia nei limiti dell'array e che la sua voce non sia NULL.

MODIFICA: se si ordina l'elenco, è sempre possibile utilizzare una ricerca binaria che dovrebbe avere una ricerca rapida.

MODIFICA: Inoltre, se si desidera cercare una stringa, è sempre possibile utilizzare anche std::map<std::string, int>. Questo dovrebbe avere delle discrete velocità di ricerca.

Answer 3

Provare std :: map.

Answer 4

Le stringhe da cercare sono disponibili staticamente? Potresti voler dare un'occhiata a perfect hashing function

Answer 5

Il modo più semplice è usare std :: map.

funziona così:

#include <map> 
using namespace std; 

... 

    map<string, int> myContainer; 
    myContainer["foo"] = 5; // map string "foo" to id 5 
    // Now check if "foo" has been added to the container: 
    if (myContainer.find("foo") != myContainer.end()) 
    { 
     // Yes! 
     cout << "The ID of foo is " << myContainer["foo"]; 
    } 
    // Let's get "foo" out of it 
    myContainer.erase("foo") 

Answer 6

In primo luogo è necessario essere in grado di quantificare i le opzioni. Ci hai anche detto che il modello di utilizzo principale che ti interessa è la ricerca , non l'inserimento.

Sia N sia il numero di stringhe che si prevede di essere avere nella tabella, e lasciare che C essere il numero medio di caratteri in un dato di stringa presenti in detta tabella (o nelle stringhe che vengono controllati contro il tavolo).

1. Nel caso di un approcciohash-based, per ogni ricerca si paga i seguenti costi:

   • O(C) - calcolare l'hash per la stringa che si sta per guardare in alto
   • tra O(1 x C) e O(N x C), dove 1..N è il costo che ci si aspetta dall'attraversare il bucket in base alla chiave hash, qui moltiplicato per C per ricontrollare i caratteri in ogni stringa contro la ricerca della chiave
   • tempo totale: tra il O(2 x C) e O((N + 1) x C)

2. Nel caso di un approccio basata su std::map (che utilizza alberi rosso-nero), per ogni ricerca si paga il costi seguenti:

   • tempo totale: tra O(1 x C) e O(log(N) x C) - dove O(log(N)) è il costo massimo attraversamento di alberi, e O(C) è il tempo che 0 generic less<> implementaziones' prende di ricontrollare la vostra chiave di ricerca durante l'attraversamento di alberi

Nel caso di valori di grandi dimensioni per N e in assenza di una funzione di hash che garantisce meno di registro collisioni (N), o se vuoi semplicemente giocare sul sicuro, , è meglio usare un approccio basato su albero (std::map). Se N è piccolo, con tutti i mezzi, utilizzare un approccio basato su hash (., Pur facendo in modo che hash collisione è basso)

Prima di prendere qualsiasi decisione, però, si dovrebbe anche controllare:

• http://meshula.net/wordpress/?p=183
• http://wyw.dcweb.cn/mstring.htm

Answer 7

Google sparse hash forse

Answer 8

provare questo:

alt text http://adrinael.net/containerchoice.png