Quali sono alcuni buoni metodi per sostituire i nomi di stringa con hash di interi

Question

Di solito, entità e componenti o altre parti del codice di gioco in progettazione basata sui dati avranno nomi controllati se si desidera scoprire quale oggetto si sta trattando con esattamente.

void Player::Interact(Entity *myEntity) 
{ 
    if(myEntity->isNearEnough(this) && myEntity->GetFamilyName() == "guard") 
    { 
     static_cast<Guard*>(myEntity)->Say("No mention of arrows and knees here"); 
    } 
} 

Se si ignora la possibilità che questo potrebbe essere l'ottimizzazione prematura, è abbastanza chiaro che la ricerca entità sarebbe molto più veloce se il loro "nome" è stato un valore a 32 bit semplice invece di uno stringa effettiva.

L'hashing di calcolo dei nomi di stringa è una possibile opzione. Non l'ho ancora provato, ma con una gamma di 32 bit e una buona funzione di hashing il rischio di collisione dovrebbe essere minimo.

La domanda è questa: ovviamente abbiamo bisogno di un modo per convertire in-code (o in un qualche tipo di file esterno) nomi di stringhe a quei numeri interi, poiché la persona che lavora su questi oggetti nominati vorrà comunque fare riferimento al oggetto come "guardia" invece di "0x2315f21a".

Supponendo che stiamo usando C++ e vogliamo sostituire tutte le stringhe che appaiono nel codice, questo può anche essere ottenuto con funzionalità incorporate in linguaggio o dobbiamo costruire uno strumento esterno che controlli manualmente tutti i file e gli scambi i valori?

Answer 1

Jason Gregory scritto questo his book:

A Naughty Dog, abbiamo utilizzato una variante l'algoritmo CRC-32 per cancellare le nostre stringhe e non abbiamo incontrato una singola collisione in oltre due anni di sviluppo su Uncharted: Drake's Fortune.

Quindi potresti volerlo esaminare.

E a proposito del passo di costruzione che hai citato, ne ha anche parlato. In sostanza incapsulano le stringhe che hanno bisogno di essere hash in qualcosa di simile:

_ID("string literal") 

e utilizzare un tool esterno in fase di compilazione di hash tutte le occorrenze. In questo modo si evitano i costi di runtime.

Answer 2

Questo è quello per cui sono le enumerazioni. Non avrei il coraggio di decidere quale risorsa è meglio per il tema, ma ci sono un sacco da scegliere: https://www.google.com/search?q=c%2B%2B+enum

Answer 3

Direi di andare con l'enumerazione!

Ma se avete già un sacco di codice già utilizzando le stringhe, beh, o semplicemente mantenere in questo modo (semplice e di solito abbastanza veloce su un PC in ogni caso) o hash utilizzando un qualche tipo di CRC o MD5 in un numero intero.

Answer 4

Questo è fondamentalmente risolto aggiungendo un riferimento indiretto in cima a una mappa di hash.

dire che si desidera convertire le stringhe di numeri interi:

• scrivere una classe avvolge sia un array e un HashMap. Io chiamo questi dizionari di classi.
• L'array contiene le stringhe.
• chiave del hash_map è la stringa (puntatori condivisi o matrici stabili dove puntatori prime sono lavoro sicuro e)
• valore della mappa hash è l'indice nella matrice stringa si trova, che è anche il manico opaca essa ritorna al codice chiamante.
• Quando si aggiunge una nuova stringa al sistema, viene cercata già presente nella hashmap, restituisce l'handle se presente.
• Se l'handle non è presente, aggiungere la stringa all'array, l'indice è l'handle.
• Impostare la stringa e l'handle nella mappa e restituire l'handle.

Note/Avvertenze:

• Questa strategia rende sempre la corda dalla pista manico in tempo costante (si tratta semplicemente di una deferenza array).
• gli identificatori di handle sono i primi arrivati, ma la serializzazione delle stringhe anziché i valori non avrà importanza.
• I sovraccarichi dell'operatore [] per la chiave e il valore sono abbastanza semplici (registrazione di nuove stringhe o ritorno della stringa), ma il wrapping dell'handle con una classe definita dall'utente (il wrapping di un intero) aggiunge un sacco di molto necessario digita sicurezza ed evita l'ambiguità se vuoi che la chiave e i valori siano gli stessi tipi (sovraccarico [] non compilare ed ecc.)
• Devi memorizzare le stringhe nella RAM, che può essere un problema.