PDA

Visualizza la versione completa : [C++] Migliorare prestazioni Tabella Hash


AyFrank
18-01-2013, 12:46
Salve a tutti, per necessitÓ, dato il tipo di input, ho un grafo derivato da una tabella hash. La tabella Ŕ implementata mediante liste di collisione, gli oggetti memorizzati nella tabella sono i Vertici del grafo i quali contengono i campi string nome (usato come chiave) ed una lista di Vertici* contenente i vertici adiacenti (implementata mediante un vettore).

Al crescere dell'input (circa sul milione di vertici) il tempo di esecuzione raggiunge i decimi di secondo, cosa che vorrei proprio evitare per il fine del programma. In particolare ho notato che la popolazione della tabella mi richiede veramente troppo tempo, vi posto di seguito i metodi usati:



TABELLA HASH
void inserisci (const string& s1, const string& s2, unsigned int distanza)
{
Vertice* v1 = searchAndInsert (s1);
Vertice* v2 = searchAndInsert (s2);

v1->inserisciAdiacente (*v2, distanza);
v2->inserisciAdiacente (*v1, distanza);
}

Vertice* searchAndInsert (const string& s) //Se Ŕ giÓ presente lo ritorna, altrimenti lo inserisce alla fine e ritorna l'ultimo elemento inserito
{
unsigned int i = FunzioneHash (s) % dim;

for (list<Vertice>::iterator it = tabella[i].begin(); it != tabella[i].end (); it++)
if (it->getNome () == s)
return &(*it);

tabella[i].push_back (Vertice (s));
++numElementi;
return &tabella[i].back ();
}

VERTICE
void inserisciAdiacente (const Vertice& v)
{
lista[i] = &v; //dove lista Ŕ un vettore dinamico implementato da me
}


Mi rivolgo a voi per qualche consiglio su come poter migliorare il tutto.. :D

Loading