intero univoco/lungo hash la generazione di chiavi su stringhe per compairson più veloce

Question

sono curioso come gli altri hanno risolto questo problema, e quali problemi potrebbero nascondersi dietro la soluzione ingenua:

Ho un sistema che elabora dati del mercato azionario. Ci sono decine di migliaia di simboli, con prezzi/dimensioni associati, che fluiscono nel sistema alla velocità di diverse migliaia di millisecondi.

Una delle operazioni di base che devono verificarsi su ogni spunta è il confronto delle stringhe per verificare se l'entrata corrisponde al simbolo a cui siamo interessati. A tale frequenza elevata, l'ottimizzazione di questi confronti di stringhe può fare una differenza misurabile nelle prestazioni dell'intero sistema.

Sto pensando di generare un hash della stringa di simboli e di memorizzarlo con il record. Per il confronto successivo, il sistema dovrebbe usare questo hash (essendo un int o un long, il confronto dovrebbe essere una singola operazione, piuttosto che scorrere attraverso ogni carattere della stringa fino a quando non viene trovata una corrispondenza mancata).

Ignoriamo il costo di generare l'hash stesso (che, in realtà, potrebbe essere effettivamente proibitivo). L'unico problema che posso vedere è che con un gran numero di simboli unici, una collisione hash (due simboli separati generano lo stesso hash) sarebbe devastante. Esiste un algoritmo di hash che garantisce che le stringhe che corrispondono a determinati vincoli (come il limite sul numero di caratteri) sono uniche?

EDIT: Scriverò questo codice in Java. Non sono sicuro della qualità (di collisione) di hashCode o della velocità con cui viene calcolata.

Answer 1

Forse le funzioni di hash non sono l'approccio migliore qui. Se stai ricevendo un simbolo ticker (e non l'hash del simbolo ticker) dovrai calcolare l'hash per ogni singola volta che passa. Se è un algoritmo di hashing senza collisioni, dovrai comunque controllare ogni carattere del simbolo. Quindi potresti anche confrontare direttamente i personaggi.

Suggerisco di creare una struttura dati Trie di tutti i ticker che ti interessano. (Vedi http://en.wikipedia.org/wiki/Trie). Attraversa l'albero per ogni simbolo e se raggiungi la fine del ticker senza trovare una corrispondenza, non è un ticker interessante.

Con l'hashing, dovrai comunque eseguire questa traversata nel set di tutti i valori hash dei ticker interessanti.

Answer 2

Se si utilizza String.intern() o il proprio pooling di stringhe, è possibile utilizzare == piuttosto che .equals(): l'ho fatto in un codice critico simile alle prestazioni e ha fatto una grande differenza. La stringa predefinita ha già un hashCode() che funziona in modo abbastanza efficace.

Ho appena realizzato che non era una domanda Java, ma lo stesso vale. Sì, l'hashing e l'utilizzo del controllo dell'identità consentono di risparmiare tempo. L'algoritmo di hashing java utilizza:

 
    s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1] 

Answer 3

funzione crittografica di hash SHA-diffusa come 1 uscite 20 byte (160 bit). Quanto durano i tuoi simboli azionari? Se stiamo parlando di ticker symbols come "WMT" (Walmart), "KO" (Coca-Cola), ecc., Allora sembrano essere solo un paio di byte - quindi dovrebbe essere più veloce confrontarli direttamente anziché occuparsi di un hash da 20 byte. Si parla di collisioni di hash: non mi preoccuperei di loro, specialmente non quando gli input sono molto più piccoli dell'hash dell'output.

Potrebbe essere possibile eseguire il cast dei byte in un int o long a seconda del linguaggio di programmazione e della piattaforma e quindi eseguire il confronto tra questi "numeri" in un'istruzione CPU. (Non so se i compilatori moderni possono confrontare un gruppo di byte altrettanto veloce con una chiamata a memcmp?)

Answer 4

Si dovrebbe considerare l'utilizzo di un Perfect hash function, penso che si adatta alle vostre esigenze

Answer 5

si potrebbe generare l'hash trattando la stringa come numero Base-27 (supponendo che i simboli contengano solo lettere). Questo genererebbe l'unicità che stai cercando. Ad esempio:

(nessuna lettera) = 0, A = 1, B = 2, ...Z = 26

AA = (1 x 27) + (1 x 27) = 28

AAA = (1 x 27) + (1 x) + (1 x 27) = 757

BBB = (2 x 27) + (2 x) + (2 x 27) = 1514

GOOG = (7 x 27) + (15 x 27) + (15 x 27) + (7 x 27) = 149128

Funzionerà fino a 6 caratteri in un 32-bit int.

Answer 6

Qualsiasi funzione di hash decente gestisce bene le collisioni. Fondamentalmente, se l'hash produce un hit per il quale esistono più risposte, c'è un elenco collegato di potenziali soluzioni in quel bucket e, per necessità, le cose rallentano nel trovare la risposta corretta (se ne esiste una).

Ma non scrivere la propria funzione di hash, utilizzare quella che è là fuori.

Oh, e generare l'hash dovrebbe essere fatto solo una volta, penserei. Perché hai una tabella di ricerca di cose che stai monitorando e la tabella hash dovrebbe cambiare solo quando aggiungi una nuova cosa "interessante" da cercare.

Answer 7

Modifica: I commenti migliori dei miei sono stati attivati ​​(e precedenti), rendendo il mio ridondante al meglio.

Answer 8

Quello che vuoi è una funzione di hash veloce che ha un buon potere discriminatorio. Per ogni stringa, calcolare la funzione di hash associata e memorizzarla con la stringa. Poi per un confronto, il codice: se (Hash (S1) == Hash (s2) & & s1 == s2) poi {...} la stringa effettiva confrontare non si verificherà a meno che gli hash corrispondono, che in pratica è solo quando le stringhe corrispondono.

Alcune persone ti diranno di implementare un hash perfetto.Puoi fare solo che quando la serie di stringhe che desideri hash ha dimensioni limitate, di solito solo 10-1000. Non puoi farlo per un vocabolario arbitrariamente grande di archi. Poiché non è possibile farlo, è necessario confrontare le stringhe per determinare l'uguaglianza.

Gli hash crittografici hanno un grande potere discriminatorio ma non sono progettati per essere veloci. . Ciò che è generalmente molto veloce e ha una buona discriminazione potere sono funzioni CRC, e la maggior parte delle lingue ha trovato facilmente le librerie che le calcolano rapidamente (usando una tecnica di ricerca di tabelle su byte). Utilizziamo CRC-32 ed è molto efficace per questo (in pratica 1 possibilità in 2^32 che si verificherà una collisione hash, quando le stringhe non corrispondono). È possibile utilizzare CRC-64, ma la potenza aggiuntiva di discriminazione fornita non aggiungerà realmente alcuna funzionalità reale.

Answer 9

I secondo il suggerimento di cui sopra di una struttura Trie come l'approccio migliore per questo caso. Computazionalmente equivalente a un perfetto hash, ma concettualmente molto più bello. Questo è presumendo che i tuoi simboli siano limitati in lunghezza.

Answer 10

FWIW, sull'ultimo progetto di volume di dati elevato in cui mi trovavo, abbiamo trovato che il filtraggio, l'aggregazione e la preclassificazione dei dati utilizzando un codice C con molto sintonia era la chiave. Tutti i nostri feed sono stati inclusi in questo pre-processore e si sono occupati della semplice pulizia dei dati prima di passare la maggior parte dei dati al nostro sistema basato su Java per l'elaborazione. Fondamentalmente il pre-processore ha fatto esattamente quello che stai chiedendo: identificare i record di interesse, verificare che fossero completi e rimuovere duplicati e vuoti. Durante le ore di punta, il pre-processore potrebbe eliminare fino al 20% degli 8 milioni di registrazioni che otterremmo all'ora (probabilmente non proprio il volume che immagino venga ricavato dai feed del mercato azionario). La nostra versione originale di Java è stata fortunata a ottenerne la metà (ma era "elegante", almeno!)

Answer 11

Se si ricevono simboli a 4 lettere, quindi ogni lettera deve essere rappresentabile come un singolo byte. Confeziona tutti e 4 insieme in un int a 32 bit, e voilà, hai il tuo "hash". Ora puoi confrontarlo con il riferimento usando una singola istruzione macchina.

Se non si stesse utilizzando Java, lo è.

Non vorrei davvero suggerire di utilizzare Java per qualcosa di fondamentale per la velocità, in particolare non migliaia di confronti tra stringhe per millisecondo.

modifica: Se si desidera utilizzare il codice a 64 bit, è possibile comprimere fino a 8 lettere per int lungo e quindi confrontare in 1 istruzione.

Answer 12

Per quello che vale. Ho risolto questo problema specifico per la simbologia CMS (NYSE) e CQS (NASDAQ). Le radici dei simboli avranno una lunghezza massima di 6 caratteri e saranno maiuscole. I miei requisiti sono stati i seguenti:

• dati sarebbe arrivato per sconosciuto simbolo
• Alla ricezione di dati calcolare un valore hash da utilizzare per il confronto
• Calcolare il valore una volta, memorizzare il valore in una mappa per il confronto futuro
• I confronti di valore saranno l'uguaglianza
• I confronti di valori saranno contro un intervallo.

Ad esempio Se arrivano i dati per GOOG, sarà necessario elaborarli e distribuirli ai processi nell'intervallo di simboli [F-HAA]. (F < = GOOG < = HAA). Ho usato una classe di intervallo che ha un valore basso (F) e un valore elevato (HAA).Il mio concetto di funzione Hash è simile al fatto di impacchettare i caratteri in byte ma per scopi di logging, di rete e di endian ho scelto per lungo tempo il mio tipo di archiviazione non firmato. Prima di chiamare questa funzione, i simboli sono riempiti con un carattere '@'. (IBM @@@)

unsigned long long SymbolToVal(std::string& str) 
{ 
size_t maxlen = 6; // Symbology constraint 
if (str.length() != maxlen) return 0; 
unsigned long long val; 
unsigned long long retval=0; 
int expon = maxlen*2; // ASCII val range (65-90) 
double factor = std::pow(10.0,expon); 
expon-=2; 
for (size_t i = 0; i < maxlen; i++) 
{ 
    val = (unsigned long long)factor * str[i]; 
    retval += val; 
    factor = (unsigned long long) std::pow(10.0,expon); 
    expon-=2; 
    } 
    return retval; 
} 

Procedimento forza bruta sarebbe quello di calcolare tutti i simboli possibili ordinarli correttamente e assegnare loro un numero intero poi memorizzarli in una mappa. Può essere eccessivo se i dati in entrata consistono solo in una piccola porzione del dominio totale (che è il caso normale).