PDA

Visualizza la versione completa : [C]Problema Doppio Hashing


markg
25-08-2008, 20:43
Salve,
ho due problemi con il doppio hashing:

1) Quando effettuo l'inserimento (Funzione Hash_Insert) mi restituisce l'errore di "Hash Table Overflow" anche quando la tabella non piena.

2) Il tempo di esecuzione dell'Insert molto diverso da quello della Search nel caso in cui l'elemento non presente (Ricerca senza successo).

Gli input utilizzati sono:

Dimensione tabella = 60001 (numero primo)
Slot utilizzati in partenza = 20000
Incremento slot utilizzati = 1000


Il codice il seguente:



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
* Doppio HASHING . Nel main la dimensione massima da inserire deve essere un numero primo.
*/

int m;

struct table{
int used_slot;
float alpha;
double Insert_time;
double Search_time;
double Search_WS_time;
};

//
int Hash_Insert(int T[], int k) {
int i = 0;
do {
int j = Hash_Function_Double(k,i);
if (T[j] == 0){
T[j] = k;
return j;
}
else {
i++;
}
}
while (i != m);
printf ("Hash Table Overflow");
}

//
int Hash_Search(int T[], int k) {
int i = 0;
int j = 0;
do{
j = Hash_Function_Double(k,i);
if (T[j] == k)
return j;
i++;
}
while(T[j] != 0 && i != m);
return 0;
}

//
int Auxiliary_Hash_Function (int k) {
int h;
h = k % m;
return h;
}

//
int Auxiliary_Hash_Function2 (int k) {
int h;
h = 1 + (k % (m-1));
return h;
}



//
int Hash_Function_Double(int k, int i){
int h, x, y;
x = Auxiliary_Hash_Function(k);
y = Auxiliary_Hash_Function2(k);
h = (x + i*y) % m;
return h;
}

int main(int argc, char *argv[]) {

int MAX, i, j, k, l, n, N, random, ran;
clock_t start,end;
double Time,diff;
FILE *result;


//INSERTION INPUT DATA
printf("Insert maximum array dimension: ");
scanf("%d", &MAX);
printf("Insert array start dimension: ");
scanf("%d", &n);
printf("Insert array increase step dimension: ");
scanf("%d", &N);
m = MAX;

//CREATE DIMENSION ARRAY AND OUTPUT ARRAY(with results)
int dim_input=((MAX-n)/N);
int DIM[dim_input];
struct table output[dim_input];
DIM[0]=n;

//FILLING DIMENSION ARRAY
for(j=1;j<dim_input;j++){
DIM[j]=DIM[j-1]+N;
}

//CREATE INPUT ARRAY RANDOMLY
int *T;
srand (time(NULL));
for (i=0; i<dim_input; i++){
int dimension=DIM[i];
T = malloc(MAX*sizeof(int));
for (k=0;k<MAX;k++){
T[k] = 0;
}

for(k=0;k<dimension;k++){
random = rand();
Hash_Insert(T,random);
}

output[i].used_slot=dimension;
output[i].alpha = ((float)(dimension) /(float)(MAX));
//ran = rand();

diff=0;
ran=rand();
for(l=0;l<100000;l++){
while (Hash_Search(T,ran) != 0) {
ran = rand();
}
start = clock();
Hash_Search(T,ran);
end = clock();
diff = diff + difftime(end,start);
}
printf("\nRicerca Senza Successo x 100000: %lf",diff);
Time = ((double)(diff/100000)/CLK_TCK)*1000000000;
output[i].Search_WS_time = Time;

diff=0;
for(l=0;l<1000000;l++){
int index=rand()%dimension;
int x=T[index];
while (x == 0){
index = rand()%dimension;
x=T[index];
}
start = clock();
Hash_Search(T,x);
end = clock();
diff = diff+difftime(end,start);
}
printf("\nRicerca Con Successo x 1000000: %lf",diff);
Time = ((double)(diff/1000000)/CLK_TCK)*1000000000;
output[i].Search_time = Time;

diff=0;
for(l=0;l<1000;l++){
start = clock();
Hash_Insert(T,ran);
end = clock();
diff = diff+difftime(end,start);
}
//printf("\nInsert x 1000: %lf",diff);
Time = ((double)(diff/1000)/CLK_TCK)*1000000000;
output[i].Insert_time = Time;


free(T);
}
//SAVE RESULTS ON FILE
result=fopen("D:\\ResultHASHdoublePROVA.txt","w+");
fprintf(result,"Used Slot\tTotal Slot\tAlpha\t\tScan Insert\tScan Search\tScan Search Without Success\n");
for(j=0;j<dim_input;j++){
fprintf(result,"%d\t\t%d\t\t%lf\t%.0f\t\t%.0f\t\t\t%.0f\n",output[j].used_slot,m,output[j].alpha,output[j].Insert_time,output[j].Search_time,output[j].Search_WS_time);
}
printf("\n");
printf("Results saved in: D:\\ResultHASHdouble.txt \n");
system ("PAUSE");
return 0;
}


Non riesco a trovare il problema.... Vi prego aiutatemi

Grazie

Andrea Simonassi
26-08-2008, 10:57
Ciao, fare il debug di un programma un lavoro piuttosto oneroso, potresti limitare il posting alle parti di codice che pensi che possano creare problemi?

se ci limitiamo alla funzione seguente:


int Hash_Insert(int T[], int k) {
int i = 0;
do {
int j = Hash_Function_Double(k,i);
if (T[j] == 0){
T[j] = k;
return j;
}
else {
i++;
}
}
while (i != m); /* Questo loop potrebbe non terminare mai. E' un errore piuttosto grave */



printf ("Hash Table Overflow"); /*Questa printf viene eseguita sempre, non condizionata.*/

/*manca il return.*/
}



Rivedi un po questa funzione perch ha tanti errori, probabilmente dovuti a fretta.

Questi non sono nemmeno bug sono proprio errori che dovrebbero essere rilevati da warning del compilatore. Ma che razza di compilatore usi? :D

Ciao

Andrea Simonassi
26-08-2008, 11:01
Un ultima cosa, solo per cultura generale, non un errore o che, solo questione di potere poi riutilizzare il tuo codice... : quando scrivi un programma separa l'interfaccia utente dal resto del programma, non mettere printf in funzioni, caso mai scrivi sullo standard error o su un file di log, oppure fai che la tua funzione restituisca un codice di errore e demanda alla funzione chiamante l'onere di scrivere sul log o di avvisare l'utente..

Ciao a presto.

Loading