come mappare una stringa specializzata nel numero intero specificato

Question

Sto facendo un po 'di lavoro di trading finanziario. Ho un set di simboli di borsa ma hanno uno schema molto chiaro: è composto da due caratteri AB, ACAD e il mese corrente è un numero di quattro cifre: 1503, 1504, 1505. Alcuni esempi sono:

AB1504 
AB1505 
AC1504 
AC1505 
AD1504 
AD1505 
.... 

Dal momento che queste stringhe sono così ben progettati fantasia, voglio mappare (hash) ciascuno della stringa in un numero intero univoco in modo che possa utilizzare il numero intero come indice di matrice per l'accesso veloce, dal momento che ho un sacco di recuperi all'interno del mio sistema e std::unordered_map o qualsiasi altra mappa hash non sono abbastanza veloci. Ho dei test che dimostrano che la mappa hash generale ha un livello di latenza di cento nanosecondi mentre l'indicizzazione dell'array è sempre inferiore a 100 nanos. il mio caso ideale sarebbe, ad esempio, AB1504 mappe a numero intero 1, AB1505 mappe a 2 ...., quindi posso creare una matrice all'interno per accedere alle informazioni relative a questi simboli molto più velocemente. Sto cercando di capire alcuni algoritmi di hash o altri metodi che possono raggiungere il mio obiettivo ma non sono riuscito a scoprirlo. Ragazzi, avete qualche suggerimento su questo problema?

Answer 1

Se si analizza la stringa come un numero di base misto, le prime 2 cifre in base-26 e poi le 4 basi 10, si otterrà rapidamente un indice univoco per ogni stringa. L'unico problema è che se si ottiene un array scarsamente popolato.

È sempre possibile riordinare le cifre quando si calcola l'indice per ridurre al minimo il problema menzionato sopra.

Poiché i numeri sono in realtà mesi, calcolare il numero di mesi dalla prima voce e moltiplicare quello con il numero di base 26 a 2 cifre dal prefisso.

Spero che tu possa avere un senso da questo, digitando sul mio tablet al momento. : D

Answer 2

I seguenti valori dovrebbero essere rappresentabile da un numero intero di 32 bit:

XYnnnn => (26 * X + Y) * 10000 + nnnn 

Qui X e Y valori take nell'intervallo [0, 26), e n assume valori nell'intervallo [0 10).

Hai un totale di 6.760.000 valori rappresentabili, quindi se si desidera associare solo una piccola quantità di dati (ad esempio un conteggio o un puntatore), è sufficiente creare un array piatto, in cui ogni simbolo occupa una matrice iscrizione.

Answer 3

È possibile considerare la stringa come una rappresentazione del numero di base variabile e convertirla in un numero intero. Ad esempio:

AC1504: 
A (range: A-Z) 
C (range: A-Z) 
15 (range: 0-99) 
04 (range: 1-12) 

Estrarre le parti; poi una funzione di hash potrebbe essere

int part1, part2, part3, part4; 
... 
part1 -= 'A'; 
part2 -= 'A'; 
part4 -= 1; 
return (((part1 * 26 + part2) * 100 + part3) * 12 + part4; 

Answer 4

Suppongo che il formato è 'AAyymm', dove A è un carattere maiuscolo aa un anno e mm a due cifre del mese a due cifre.

Quindi è possibile mapparlo su 10 (AA) + Y (yy) + 4 (mm) bit. dove Y = 32 - 10 - 4 = 18 bit per una rappresentazione a 32 bit (o 262144 anni). Avendo ciò, è possibile rappresentare il formato come numero intero spostando i caratteri in quella posizione e spostando le coppie di anni e mesi in tali posizioni dopo averli convertiti in un numero intero.

Nota: Ci saranno sempre lacune nella rappresentazione binaria, Qui la rappresentazione 5 + 5 bit per i caratteri (6 + 6 valori) e nella rappresentazione mese a 4 bit (4 valori)

Per evitare la gli spazi vuoti cambiano la rappresentazione in ABmmmm, dove la coppia AB è rappresentata da un numero 26 * A + B e mmmm è il mese relativo a qualche mese zero in qualche anno (che copre 2^32/1024/12 = 349525 anni - avendo 32 bit).

Tuttavia, è possibile prendere in considerazione una suddivisione di simboli e tempi. La combinazione di due valori in un campo è di solito fastidiosa (potrebbe essere un buon formato di archiviazione, ma non un buon "formato dati del programma").