Supponiamo di avere una matrice di stringhe ordinate ad es. std::vector<std::string> o alcuni altri elementi con stringa come chiave - ad esempio std::vector<std::pair<std::string,data_type> .
Normalmente per trovare elementi lì, dobbiamo fare la ricerca binaria.
Funzionerà velocemente, ma ogni confronto avrà il puntatore indiretto più un confronto di stringhe relativamente costoso.
Per accelerare le cose, possiamo fare qualcosa di simile:
struct small_string{
char data[8];
};
std::vector<small_string> line;
Quando popoliamo il vettore normale, possiamo popolare i primi 8 caratteri nell'array line.
Quindi eseguiamo la normale ricerca binaria, ma prima controlliamo line array. Se otteniamo "uguale" controlliamo nella matrice normale. Altrimenti procediamo con la ricerca binaria.
L'ho già fatto. L'accelerazione è tra il 30 e il 50%.
Tuttavia, poiché molti valori in line array potrebbero essere uguali, possiamo fare hash-table o array e memorizzare il primo e l'ultimo indice dalla matrice.
Potrebbe assomigliare a questo:
struct small_string_range{
char data[8];
size_t begin_range;
size_t end_range;
};
std::vector<small_string_range> range_line;
// for non C++ programmers, size_t is unsigned integer
La struttura ora assomiglia a trie , per cercare dentro prima si individuano i primi 8 byte della chiave all'interno di range_line . Lo fai usando la tabella hash della ricerca binaria.
Secondo, controlli gli intervalli e fai la ricerca binaria sulla matrice normale. Per le chiavi inferiori a 8 byte, ottieni l'indice direttamente.
Domanda:
Questo algoritmo esiste?
Questo algoritmo è valido?