Tabela Hash

Happening · May 24, 2012 at 12:45 PM

Boas, estou a implementar um programa que lê de um ficheiro um distrito, um concelho, e uma freguesia e respectivo número de habitantes. O objectivo é o programa devolver o menor freguesia do maior concelho. Para isso decidi implementar uma tabela hash e um apontador para o maior concelho. O que está a acontecer é que o programa está-me a devolver o conselho da maior freguesia.

Penso que não está a funcionar bem na função adiciona... mas já a vi umas 20 vezes e não vejo o erro...

Agradeço imenso se alguem me puder ajudar.

O meu código é o seguinte: (Desculpem o tamanho do posto mas era para ficar tudo bem claro)

#ifndef TABDISPERSAO_H
#define TABDISPERSAO_H
#define TABDISPERSAO_EXISTE	 (1)
#define TABDISPERSAO_OK	 (0)
#define TABDISPERSAO_INVALIDA   (-1)
#define TABDISPERSAO_ERRO	   (-2)
#define TABDISPERSAO_NAOEXISTE  (-3)
typedef unsigned long hash_func(const char *, int);
/* tabela de dispersão baseada em encadeamento */
typedef struct freg
{
char *nome;
int nHabitantes;
} freguesia;
typedef struct conc
{
char *nomeConc;
int nHabitantes;
freguesia *menorFreguesia;
struct conc * proximo;
} concelho;
/*
* \brief A estrutura tabela_dispersao para armazenar dados relativos a uma tabela de dispersao
*/
typedef struct
{
hash_func *hfunc; /* apontador para a funcao a ser usada (hash_djb, hash_kr, ...) */
concelho *maiorConcelho;
concelho **concelhos; /* vector de listas de concelhos */
int tamanho;   /* tamanho do vector de listas de concelhos */
} tabela_dispersao;
/**
* \brief cria uma tabela de dispersao
* \param tamanho tamanho da tabela de dispersao
* \param hash_func apontador para funcao de dispersao a ser usada nesta tabela
* \return uma tabela de dispersao vazia que usa a funcao de dispersao escolhida
*/
tabela_dispersao* tabela_cria(int tamanho, hash_func *hfunc);
/**
* \brief elimina uma lista, libertando toda a memoria ocupada
* \param td tabela de dispersao a ser apagada da memoria
* \remark apagar _todos_ os concelhos anteriormente alocados na memoria
*/
void tabela_apaga(tabela_dispersao *td);
/**
* \brief adiciona um novo valor 'a tabela
* \param td tabela onde adicionar o concelho
* \param valor valor a ser adicionado
* \return se o valor for adicionado correctamente, a funcao retorna TABDISPERSAO_OK
* \remark a tabela nao deve ficar com valores repetidos.
* \remark valor deve ser copiado para outro local em memoria.
*/
int tabela_adiciona(tabela_dispersao *td, const char *nomeC, const freguesia *freg);
/**
* \brief apaga todos os valores correntemente na tabela, ficando a tabela vazia
* \param td tabela a ser esvaziada
* \return TABDISPERSAO_OK ou TABDISPERSAO_INVALIDA de acordo com o resultado
*/
int tabela_esvazia(tabela_dispersao * td);
/**
* \brief calcula hash com base na seguinte formula:
*			hash(i) = hash(i-1) + valor[i]
*	em que hash(0) = 0
*
* \param valor nomeConc para a qual se pretende calcular o valor de hash
* \param tamanho da tabela de dispersão
* \remark valor[i] e' o caracter no indice de i da nomeConc valor
*/
unsigned long hash_kr(const char *valor, int tamanho);
/*
* \brief calcula hash com base na seguinte formula:
*			hash(i) = hash(i-1)* 33 (+) valor[i]
*		em que hash(0) = 5381
*
* \param valor nomeConc para a qual se pretende calcular o valor de hash
* \param tamanho da tabela de dispersão
* \remark valor[i] e' o caracter no indice de i da nomeConc valor
* \remark (+) representa "ou exclusivo" que em C e' indicado por ^
*/
unsigned long hash_djb(const char *valor, int tamanho);
#endif

que é o header da tabela.

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "tabdispersao.h"
tabela_dispersao* tabela_cria(int tamanho, hash_func *hfunc)
{
tabela_dispersao *tab;
tab = (tabela_dispersao*) malloc (sizeof(tabela_dispersao)); //cria espaço para a tabela
if(tab==NULL) return NULL;
tab->concelhos = (concelho**) calloc (tamanho, sizeof(concelho*)); //cria espaço para concelhos da tabela e inicia os apontadores a null
if(tab->concelhos==NULL) return NULL;
tab->hfunc=hfunc;
tab->tamanho=tamanho;
tab->maiorConcelho = NULL;
return tab;
}
void tabela_apaga(tabela_dispersao *td)
{
if(td!=NULL){
 tabela_esvazia(td);
 free(td->concelhos);
 free(td);
}
}
int tabela_adiciona(tabela_dispersao *td, const char *nomeC, const freguesia *freg)
{
int x;
concelho *pointer;
if(td==NULL) return TABDISPERSAO_INVALIDA;
x = td->hfunc( nomeC, td->tamanho);
pointer=td->concelhos[x];
if (pointer == NULL)
{
 pointer = (concelho*) malloc (sizeof(concelho));
 if(pointer==NULL) return TABDISPERSAO_ERRO;
 pointer->nomeConc = (char*) malloc((strlen(nomeC)+1)*sizeof(char));
 if(pointer->nomeConc==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->nomeConc, nomeC);
 pointer->nHabitantes = freg->nHabitantes;
 pointer->menorFreguesia = (freguesia*) malloc (sizeof(freguesia));
 if(pointer->menorFreguesia==NULL) return TABDISPERSAO_ERRO;
 pointer->menorFreguesia->nome = (char*) malloc((strlen(freg->nome)+1)*sizeof(char));
 if(pointer->menorFreguesia->nome==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->menorFreguesia->nome, freg->nome);
 pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
 pointer->proximo=NULL;
 td->concelhos[x] = pointer;
 if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
  td->maiorConcelho = pointer;
 return TABDISPERSAO_OK;
}
else
{
 while(pointer->proximo != NULL){
  if(strcmp(pointer->nomeConc, nomeC) == 0)
  {
pointer->nHabitantes = pointer->nHabitantes + freg->nHabitantes;
if (freg->nHabitantes < pointer->menorFreguesia->nHabitantes)
{
 realloc(pointer->menorFreguesia->nome,(strlen(freg->nome)+1)*sizeof(char));
 strcpy(pointer->menorFreguesia->nome, freg->nome);
 pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
}
if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
 td->maiorConcelho = pointer;
return TABDISPERSAO_OK;
  }
  else
pointer = pointer->proximo;
 }

  pointer = (concelho*) malloc (sizeof(concelho));
  if(pointer==NULL) return TABDISPERSAO_ERRO;
  pointer->nomeConc = (char*) malloc((strlen(nomeC)+1)*sizeof(char));
  if(pointer->nomeConc==NULL) return TABDISPERSAO_ERRO;
  strcpy_s(pointer->nomeConc,(strlen(nomeC)+1)*sizeof(char), nomeC);
  pointer->nHabitantes = freg->nHabitantes;
  pointer->menorFreguesia = (freguesia*) malloc (sizeof(freguesia));
  pointer->menorFreguesia->nome = (char*) malloc((strlen(freg->nome)+1)*sizeof(char));
  strcpy_s(pointer->menorFreguesia->nome,(strlen(freg->nome)+1)*sizeof(char), freg->nome);
  pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
  pointer->proximo = NULL;
  if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
td->maiorConcelho = pointer;
  return TABDISPERSAO_OK;

}
}
int tabela_esvazia(tabela_dispersao * td)
{
int i;
concelho *temp;
if(td==NULL) return TABDISPERSAO_INVALIDA;
for(i=0;i<td->tamanho;i++)
{
 while(td->concelhos[i]!=NULL)
 {

  temp=td->concelhos[i]->proximo;
  free(td->concelhos[i]->nomeConc);
  free(td->concelhos[i]->menorFreguesia->nome);
  free(td->concelhos[i]->menorFreguesia);
  free(td->concelhos[i]);
  td->concelhos[i]=temp;
 }
 td->concelhos[i]=NULL;
}

return TABDISPERSAO_OK;
}
unsigned long hash_kr(const char *valor, int tamanho)
{
int len, i;
unsigned long soma=0;
len=strlen(valor);
for(i=0;i<len;i++){
 soma += valor[i]; // = a ter soma=soma+valor[i]
}
return soma=soma%tamanho; // retorna hash=soma%tamanho;
}
unsigned long hash_djb(const char *valor, int tamanho)
{
int len, i;
unsigned long soma = 5381;
len=strlen(valor);
for(i=0;i<len;i++){
 soma=soma*33^valor[i];
}
return soma%tamanho;
}

Funções da tabela.

e por fim o código do main():

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "tabdispersao.h"

int main(int argc, char *argv[]){
double tmp = clock() / (CLOCKS_PER_SEC/1000);
char buffer[100], *distritoNome, *concelhoNome, *freguesiaNome, *habitantesStr;
int HabitantesNum;
tabela_dispersao* tabela;
int valida = -1;
freguesia freg;
FILE *fp;
fp = fopen("shuffle.csv","r");
if(fp==NULL) {
 perror("O ficheiro não abriu.\n");
 exit(1);
}
tabela = tabela_cria(100, &hash_djb);
while(fp!=feof){
 fgets(buffer, 100, fp);
 distritoNome = strtok(buffer, ",\n");
 if (distritoNome == NULL) break;
 concelhoNome = strtok(NULL, ",\n");
 if (concelhoNome == NULL) break;
 freguesiaNome = strtok(NULL, ",\n");
 if (freguesiaNome == NULL) break;
 habitantesStr = strtok(NULL, ",\n");
 if (habitantesStr != NULL)
 {
  HabitantesNum = atoi(habitantesStr);
  freg.nome = freguesiaNome;
  freg.nHabitantes = HabitantesNum;
  if (tabela_adiciona(tabela, concelhoNome, &freg) != TABDISPERSAO_OK) break;
 }
 else
  continue;

}
printf("%s - %s - %d, %f", tabela->maiorConcelho->nomeConc, tabela->maiorConcelho->menorFreguesia->nome, tabela->maiorConcelho->menorFreguesia->nHabitantes, clock() / (CLOCKS_PER_SEC/1000)- tmp);

system("pause");
return 0;
}

pmg · May 24, 2012 at 01:15 PM

Sugestão: se o teu objectivo é apenas imprimir a menor freguesia do concelho maior sem outro processamento, não precisas de tabela de dispersão. Guarda, numa variavel temporária, o resultado corrente; que vais actualizando à medida que lês o ficheiro.

Quando chegares ao fim do ficheiro, o resultado é o que está na variável temporária 🙂

O teu código

while(fp!=feof){

faz um ciclo infinito (e o compilador deve ter-te avisado que estás a comparar ponteiros de tipos diferentes, que não são comparaveis!) Liga todos os warnings do teu compilador e não deixes que uma compilação com warnings seja válida.

O que se passa é que fp é um ponteiro (para um objecto de tipo FILE) e feof é outro ponteiro (para uma função). Estses dois ponteiros (ignorando o facto de apontarem para tipos diferentes) nunca são iguais!

Happening · May 24, 2012 at 03:19 PM

Bem, o que se passa é o seguinte, os concelhos no ficheiro estão todos misturados. Ou seja eu posso ter um no início com uma dada freguesia e o mesmo concelho no fim com outra freguesia. O objectivo é somar o número de habitantes de todas as freguesias de cada concelho, ver qual o maior concelho e devolver a freguesia com menor população do concelho com maior população.

Então estou a fazer mal a leitura do ficheiro???

Obrigado 🙂

Mas agora dá-me 5 warnings a dizer que a função strcpy pode não ser segura.... DAFUQ? 😕

Edited May 24, 2012 at 03:23 PM by Happening

pmg · May 24, 2012 at 03:33 PM

Bem, o que se passa é o seguinte, os concelhos no ficheiro estão todos misturados. Ou seja eu posso ter um no início com uma dada freguesia e o mesmo concelho no fim com outra freguesia. O objectivo é somar o número de habitantes de todas as freguesias de cada concelho ...

Ah! Ok! A hash table é uma boa solução 🙂

Quando chegar a casa vou olhar para a tua implementação com mais atenção.

Mas agora dá-me 5 warnings a dizer que a função strcpy pode não ser segura.... DAFUQ? 😕

Experimenta adicionar no principio do teu codigo o seguinte

#define _CRT_SECURE_NO_DEPRECATE

Lê mais aqui ==> http://www.codeguru.com/cpp/security/article.php/c18495/Microsoft-Visual-Studio-Secure-CRT-Functions.htm

Happening · May 24, 2012 at 03:42 PM

A parte de usar strcpy_s já tinha procurado e implementado ontem mas depois dava isto "Unhandled exception at 0x00371785 in trabalho3.c.exe: 0xC0000005: Access violation reading location 0x00000000."

E agora que modifiquei umas coisas dá o mesmo.

Vou postar o meu código com as alterações:

#ifndef TABDISPERSAO_H
#define TABDISPERSAO_H
#define TABDISPERSAO_EXISTE	 (1)
#define TABDISPERSAO_OK	 (0)
#define TABDISPERSAO_INVALIDA   (-1)
#define TABDISPERSAO_ERRO	   (-2)
#define TABDISPERSAO_NAOEXISTE  (-3)
typedef unsigned long hash_func(const char *, int);
/* tabela de dispersão baseada em encadeamento */
typedef struct freg
{
char *nome;
int nHabitantes;
} freguesia;
typedef struct conc
{
char *nomeConc;
int nHabitantes;
freguesia *menorFreguesia;
struct conc * proximo;
} concelho;
/*
* \brief A estrutura tabela_dispersao para armazenar dados relativos a uma tabela de dispersao
*/
typedef struct
{
hash_func *hfunc; /* apontador para a funcao a ser usada (hash_djb, hash_kr, ...) */
concelho *maiorConcelho;
concelho **concelhos; /* vector de listas de concelhos */
int tamanho;   /* tamanho do vector de listas de concelhos */
} tabela_dispersao;
/**
* \brief cria uma tabela de dispersao
* \param tamanho tamanho da tabela de dispersao
* \param hash_func apontador para funcao de dispersao a ser usada nesta tabela
* \return uma tabela de dispersao vazia que usa a funcao de dispersao escolhida
*/
tabela_dispersao* tabela_cria(int tamanho, hash_func *hfunc);
/**
* \brief elimina uma lista, libertando toda a memoria ocupada
* \param td tabela de dispersao a ser apagada da memoria
* \remark apagar _todos_ os concelhos anteriormente alocados na memoria
*/
void tabela_apaga(tabela_dispersao *td);
/**
* \brief adiciona um novo valor 'a tabela
* \param td tabela onde adicionar o concelho
* \param valor valor a ser adicionado
* \return se o valor for adicionado correctamente, a funcao retorna TABDISPERSAO_OK
* \remark a tabela nao deve ficar com valores repetidos.
* \remark valor deve ser copiado para outro local em memoria.
*/
int tabela_adiciona(tabela_dispersao *td, const char *nomeC, const freguesia *freg);
/**
* \brief apaga todos os valores correntemente na tabela, ficando a tabela vazia
* \param td tabela a ser esvaziada
* \return TABDISPERSAO_OK ou TABDISPERSAO_INVALIDA de acordo com o resultado
*/
int tabela_esvazia(tabela_dispersao * td);
/**
* \brief calcula hash com base na seguinte formula:
*		    hash(i) = hash(i-1) + valor[i]
*    em que hash(0) = 0
*
* \param valor nomeConc para a qual se pretende calcular o valor de hash
* \param tamanho da tabela de dispersão
* \remark valor[i] e' o caracter no indice de i da nomeConc valor
*/
unsigned long hash_kr(const char *valor, int tamanho);
/*
* \brief calcula hash com base na seguinte formula:
*		    hash(i) = hash(i-1)* 33 (+) valor[i]
*	    em que hash(0) = 5381
*
* \param valor nomeConc para a qual se pretende calcular o valor de hash
* \param tamanho da tabela de dispersão
* \remark valor[i] e' o caracter no indice de i da nomeConc valor
* \remark (+) representa "ou exclusivo" que em C e' indicado por ^
*/
unsigned long hash_djb(const char *valor, int tamanho);
#endif

HEADER

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "tabdispersao.h"
tabela_dispersao* tabela_cria(int tamanho, hash_func *hfunc)
{
tabela_dispersao *tab;
tab = (tabela_dispersao*) malloc (sizeof(tabela_dispersao)); //cria espaço para a tabela
if(tab==NULL) return NULL;
tab->concelhos = (concelho**) calloc (tamanho, sizeof(concelho*)); //cria espaço para concelhos da tabela e inicia os apontadores a null
if(tab->concelhos==NULL) return NULL;
tab->hfunc=hfunc;
tab->tamanho=tamanho;
tab->maiorConcelho = NULL;
return tab;
}
void tabela_apaga(tabela_dispersao *td)
{
if(td!=NULL){
 tabela_esvazia(td);
 free(td->concelhos);
 free(td);
}
}
int tabela_adiciona(tabela_dispersao *td, const char *nomeC, const freguesia *freg)
{
int x;
concelho *pointer;
if(td==NULL) return TABDISPERSAO_INVALIDA;
x = td->hfunc( nomeC, td->tamanho);
pointer=td->concelhos[x];
if (pointer == NULL)
{
 pointer = (concelho*) malloc (sizeof(concelho));
 if(pointer==NULL) return TABDISPERSAO_ERRO;
 pointer->nomeConc = (char*) malloc((strlen(nomeC)+1)*sizeof(char));
 if(pointer->nomeConc==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->nomeConc, nomeC);
 pointer->nHabitantes = freg->nHabitantes;
 pointer->menorFreguesia = (freguesia*) malloc (sizeof(freguesia));
 if(pointer->menorFreguesia==NULL) return TABDISPERSAO_ERRO;
 pointer->menorFreguesia->nome = (char*) malloc((strlen(freg->nome)+1)*sizeof(char));
 if(pointer->menorFreguesia->nome==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->menorFreguesia->nome, freg->nome);
 pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
 pointer->proximo=NULL;
 td->concelhos[x] = pointer;
 if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
 {
  realloc(td->maiorConcelho->nomeConc, (strlen(pointer->nomeConc)+1)*sizeof(char));

  strcpy(td->maiorConcelho->nomeConc, pointer->nomeConc);
  td->maiorConcelho->nHabitantes = pointer->nHabitantes;
 }
 return TABDISPERSAO_OK;
}
else
{
 while(pointer->proximo != NULL){
  if(strcmp(pointer->nomeConc, nomeC) == 0)
  {
   pointer->nHabitantes = pointer->nHabitantes + freg->nHabitantes;
   if (freg->nHabitantes < pointer->menorFreguesia->nHabitantes)
   {
 realloc(pointer->menorFreguesia->nome,(strlen(freg->nome)+1)*sizeof(char));
 strcpy(pointer->menorFreguesia->nome, freg->nome);
 pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
   }
   if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
 {
  td->maiorConcelho->nomeConc = pointer->nomeConc;
  td->maiorConcelho->nHabitantes = pointer->nHabitantes;
   }
   return TABDISPERSAO_OK;
  }
  else
   pointer = pointer->proximo;
 }

  pointer = (concelho*) malloc (sizeof(concelho));
  if(pointer==NULL) return TABDISPERSAO_ERRO;
  pointer->nomeConc = (char*) malloc((strlen(nomeC)+1)*sizeof(char));
  if(pointer->nomeConc==NULL) return TABDISPERSAO_ERRO;
  strcpy(pointer->nomeConc, nomeC);
  pointer->nHabitantes = freg->nHabitantes;
  pointer->menorFreguesia = (freguesia*) malloc (sizeof(freguesia));
  if(pointer->menorFreguesia == NULL) return TABDISPERSAO_ERRO;
  pointer->menorFreguesia->nome = (char*) malloc((strlen(freg->nome)+1)*sizeof(char));
  if(pointer->menorFreguesia->nome == NULL) return TABDISPERSAO_ERRO;
  if(freg->nHabitantes < pointer->menorFreguesia->nHabitantes)
  {
  realloc(pointer->menorFreguesia->nome,(strlen(freg->nome)+1)*sizeof(char));
  strcpy(pointer->menorFreguesia->nome, freg->nome);
  pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
  }
  pointer->proximo = NULL;

  if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
  {
   td->maiorConcelho->nomeConc = pointer->nomeConc;
   td->maiorConcelho->nHabitantes = pointer->nHabitantes;
  }
  return TABDISPERSAO_OK;

}
}
int tabela_esvazia(tabela_dispersao * td)
{
int i;
concelho *temp;
if(td==NULL) return TABDISPERSAO_INVALIDA;
for(i=0;i<td->tamanho;i++)
{
 while(td->concelhos[i]!=NULL)
 {

  temp=td->concelhos[i]->proximo;
  free(td->concelhos[i]->nomeConc);
  free(td->concelhos[i]->menorFreguesia->nome);
  free(td->concelhos[i]->menorFreguesia);
  free(td->concelhos[i]);
  td->concelhos[i]=temp;
 }
 td->concelhos[i]=NULL;
}

return TABDISPERSAO_OK;
}
unsigned long hash_kr(const char *valor, int tamanho)
{
int len, i;
unsigned long soma=0;
len=strlen(valor);
for(i=0;i<len;i++){
 soma += valor[i]; // = a ter soma=soma+valor[i]
}
return soma=soma%tamanho; // retorna hash=soma%tamanho;
}
unsigned long hash_djb(const char *valor, int tamanho)
{
int len, i;
unsigned long soma = 5381;
len=strlen(valor);
for(i=0;i<len;i++){
 soma=soma*33^valor[i];
}
return soma%tamanho;
}

FUNÇOES DA HASH

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "tabdispersao.h"
#define _CRT_SECURE_NO_DEPRECATE
int main(int argc, char *argv[]){
int tmp = clock() / (CLOCKS_PER_SEC/1000);
char buffer[100], *distritoNome, *concelhoNome, *freguesiaNome, *habitantesStr;
int HabitantesNum;
tabela_dispersao* tabela;
int valida = -1;
freguesia freg;
FILE *fp;
fp = fopen("shuffle.csv","r");
if(fp==NULL) {
 perror("O ficheiro não abriu.\n");
 exit(1);
}
tabela = tabela_cria(100, &hash_djb);
while(!feof(fp)){
 fgets(buffer, 100, fp);
 distritoNome = strtok(buffer, ",\n");
 if (distritoNome == NULL) break;
 concelhoNome = strtok(NULL, ",\n");
 if (concelhoNome == NULL) break;
 freguesiaNome = strtok(NULL, ",\n");
 if (freguesiaNome == NULL) break;
 habitantesStr = strtok(NULL, ",\n");
 if (habitantesStr != NULL)
 {
  HabitantesNum = atoi(habitantesStr);
  freg.nome = freguesiaNome;
  freg.nHabitantes = HabitantesNum;
  if (tabela_adiciona(tabela, concelhoNome, &freg) != TABDISPERSAO_OK) break;
 }
 else
  continue;
}
printf("%s - %s - %d, %d", tabela->maiorConcelho->nomeConc, tabela->maiorConcelho->menorFreguesia->nome, tabela->maiorConcelho->menorFreguesia->nHabitantes, clock() / (CLOCKS_PER_SEC/1000)- tmp);

system("pause");
return 0;
}

MAIN()

Está assim. O objectivo é que ele devolve-se o mais rapidamente possivel. Noutra versão do código apesar de dar mal o tempo de resposta era de 40 milissegundos. Há alguma forma de por nitro nisto?

pmg · May 24, 2012 at 04:02 PM

Isto

realloc(ponteiro, novotamanho);

não faz o que tu pensas que faz.

Para fazeres o que queres, e evitar "memory leaks" quando o realloc falha, faz assim

tmp = realloc(ponteiro, novotamanho);
if (tmp == NULL) {
 /* o realloc falhou;
    a variavel ponteiro contem o endereco do bloco antigo
    podes usar para, por exemplo, gravar dados */
 /* ou acaba o processo */
 free(ponteiro);
 abort();
} else {
 ponteiro = tmp;
}

Happening · May 24, 2012 at 04:17 PM

Então no caso do meu programa ponho pointer=realloc?

pmg · May 24, 2012 at 05:26 PM

Se nao te importares em haver erros estranhos caso o realloc falhe

ponteiro = realloc(ponteiro, novotamanho); /* UGH! nao usar!! */

Se o realloc() falhar, o ponteiro fica com NULL e o valor antigo do ponteiro (que aponta para um bloco de memoria valido) perde-se. Se nao tiveres uma copia desse valor o teu programa desperdica a memoria antiga (memory leak).

Happening · May 24, 2012 at 07:44 PM

Boas, corrigi como disseste mas continua com o mesmo erro de memória...

Fiz isto:

if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
 {
  td->maiorConcelho->nomeConc = realloc(td->maiorConcelho->nomeConc, (strlen(pointer->nomeConc)+1)*sizeof(char));
  if(td->maiorConcelho->nomeConc == NULL)
   free(td->maiorConcelho->nomeConc);
  else

  strcpy(td->maiorConcelho->nomeConc, pointer->nomeConc);

pmg · May 24, 2012 at 09:45 PM

  if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
  ...
  strcpy(td->maiorConcelho->nomeConc, pointer->nomeConc);

Esta aqui a razao do crash.

Da primeira vez que a funcao corre, o td->maiorConcelho esta a NULL e o strcpy vai querer copiar para NULL.

Para descobrires o proximo erro, executa o teu programa instrucao a instrucao no debugger ou mete uns printfs espalhados pelo codigo ate descobrires onde (e porque!) o programa falha.

Happening · May 25, 2012 at 10:01 AM

Programa corrigido e a funcionar.

HEADER:

#ifndef TABDISPERSAO_H
#define TABDISPERSAO_H
#define TABDISPERSAO_EXISTE	 (1)
#define TABDISPERSAO_OK	 (0)
#define TABDISPERSAO_INVALIDA   (-1)
#define TABDISPERSAO_ERRO	   (-2)
#define TABDISPERSAO_NAOEXISTE  (-3)
typedef unsigned long hash_func(const char *, int);
/* tabela de dispersão baseada em encadeamento */
typedef struct freg
{
char *nome;
int nHabitantes;
} freguesia;
typedef struct conc
{
char *distrito;
char *nomeConc;
int nHabitantes;
freguesia *menorFreguesia;
struct conc * proximo;
} concelho;
/*
* \brief A estrutura tabela_dispersao para armazenar dados relativos a uma tabela de dispersao
*/
typedef struct
{
hash_func *hfunc; /* apontador para a funcao a ser usada (hash_djb, hash_kr, ...) */
concelho *maiorConcelho;
concelho **concelhos; /* vector de listas de concelhos */
int tamanho;   /* tamanho do vector de listas de concelhos */
} tabela_dispersao;
/**
* \brief cria uma tabela de dispersao
* \param tamanho tamanho da tabela de dispersao
* \param hash_func apontador para funcao de dispersao a ser usada nesta tabela
* \return uma tabela de dispersao vazia que usa a funcao de dispersao escolhida
*/
tabela_dispersao* tabela_cria(int tamanho, hash_func *hfunc);
/**
* \brief elimina uma lista, libertando toda a memoria ocupada
* \param td tabela de dispersao a ser apagada da memoria
* \remark apagar _todos_ os concelhos anteriormente alocados na memoria
*/
void tabela_apaga(tabela_dispersao *td);
/**
* \brief adiciona um novo valor 'a tabela
* \param td tabela onde adicionar o concelho
* \param valor valor a ser adicionado
* \return se o valor for adicionado correctamente, a funcao retorna TABDISPERSAO_OK
* \remark a tabela nao deve ficar com valores repetidos.
* \remark valor deve ser copiado para outro local em memoria.
*/
int tabela_adiciona(tabela_dispersao *td, const char *distritoNome, const char *nomeC, const freguesia *freg);
/**
* \brief apaga todos os valores correntemente na tabela, ficando a tabela vazia
* \param td tabela a ser esvaziada
* \return TABDISPERSAO_OK ou TABDISPERSAO_INVALIDA de acordo com o resultado
*/
int tabela_esvazia(tabela_dispersao * td);
/**
* \brief calcula hash com base na seguinte formula:
*		    hash(i) = hash(i-1) + valor[i]
*    em que hash(0) = 0
*
* \param valor nomeConc para a qual se pretende calcular o valor de hash
* \param tamanho da tabela de dispersão
* \remark valor[i] e' o caracter no indice de i da nomeConc valor
*/
unsigned long hash_kr(const char *valor, int tamanho);
/*
* \brief calcula hash com base na seguinte formula:
*		    hash(i) = hash(i-1)* 33 (+) valor[i]
*	    em que hash(0) = 5381
*
* \param valor nomeConc para a qual se pretende calcular o valor de hash
* \param tamanho da tabela de dispersão
* \remark valor[i] e' o caracter no indice de i da nomeConc valor
* \remark (+) representa "ou exclusivo" que em C e' indicado por ^
*/
unsigned long hash_djb(const char *valor, int tamanho);
#endif

FUNÇÕES:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "tabdispersao.h"
tabela_dispersao* tabela_cria(int tamanho, hash_func *hfunc)
{
tabela_dispersao *tab;
tab = (tabela_dispersao*) malloc (sizeof(tabela_dispersao)); //cria espaço para a tabela
if(tab==NULL) return NULL;
tab->concelhos = (concelho**) calloc (tamanho, sizeof(concelho*)); //cria espaço para concelhos da tabela e inicia os apontadores a null
if(tab->concelhos==NULL) return NULL;
tab->hfunc=hfunc;
tab->tamanho=tamanho;
tab->maiorConcelho = NULL;
return tab;
}
void tabela_apaga(tabela_dispersao *td)
{
if(td!=NULL){
 tabela_esvazia(td);
 free(td->concelhos);
 free(td);
}
}
int tabela_adiciona(tabela_dispersao *td, const char *distritoNome, const char *nomeC, const freguesia *freg)
{
int x;
int first = 0;
concelho *pointer;
if(td==NULL) return TABDISPERSAO_INVALIDA;
x = td->hfunc( nomeC, td->tamanho);
pointer=td->concelhos[x];
first = (pointer == NULL);
while(!first && pointer->proximo != NULL){
 if(strcmp(pointer->nomeConc, nomeC) == 0)
  break;
 else
  pointer = pointer->proximo;
}
if (!first && strcmp(pointer->nomeConc, nomeC) == 0)
{
 pointer->nHabitantes = pointer->nHabitantes + freg->nHabitantes;
 if (freg->nHabitantes < pointer->menorFreguesia->nHabitantes)
 {
  pointer->menorFreguesia->nome = (char*)realloc(pointer->menorFreguesia->nome,(strlen(freg->nome)+1)*sizeof(char));
  strcpy(pointer->menorFreguesia->nome, freg->nome);
  pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
 }
}
else
{
 pointer = (concelho*) malloc (sizeof(concelho));
 if(pointer==NULL) return TABDISPERSAO_ERRO;
 pointer->distrito = (char*) malloc((strlen(distritoNome)+1)*sizeof(char));
 if(pointer->distrito==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->distrito, distritoNome);

 pointer->nomeConc = (char*) malloc((strlen(nomeC)+1)*sizeof(char));
 if(pointer->nomeConc==NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->nomeConc, nomeC);

 pointer->nHabitantes = freg->nHabitantes;

 pointer->menorFreguesia = (freguesia*) malloc (sizeof(freguesia));
 if(pointer->menorFreguesia == NULL) return TABDISPERSAO_ERRO;
 pointer->menorFreguesia->nome = (char*) malloc((strlen(freg->nome)+1)*sizeof(char));
 if(pointer->menorFreguesia->nome == NULL) return TABDISPERSAO_ERRO;
 strcpy(pointer->menorFreguesia->nome, freg->nome);
 pointer->menorFreguesia->nHabitantes = freg->nHabitantes;
 pointer->proximo = NULL;
}
if (first) td->concelhos[x] = pointer;
if (td->maiorConcelho == NULL || pointer->nHabitantes > td->maiorConcelho->nHabitantes)
 td->maiorConcelho = pointer;

return TABDISPERSAO_OK;
}
int tabela_esvazia(tabela_dispersao * td)
{
int i;
concelho *temp;
if(td==NULL) return TABDISPERSAO_INVALIDA;
for(i=0;i<td->tamanho;i++)
{
 while(td->concelhos[i]!=NULL)
 {

  temp=td->concelhos[i]->proximo;
  free(td->concelhos[i]->distrito);
  free(td->concelhos[i]->nomeConc);
  free(td->concelhos[i]->menorFreguesia->nome);
  free(td->concelhos[i]->menorFreguesia);
  free(td->concelhos[i]);
  td->concelhos[i]=temp;
 }
 td->concelhos[i]=NULL;
}

return TABDISPERSAO_OK;
}
unsigned long hash_kr(const char *valor, int tamanho)
{
int len, i;
unsigned long soma=0;
len=strlen(valor);
for(i=0;i<len;i++){
 soma += valor[i]; // = a ter soma=soma+valor[i]
}
return soma=soma%tamanho; // retorna hash=soma%tamanho;
}
unsigned long hash_djb(const char *valor, int tamanho)
{
int len, i;
unsigned long soma = 5381;
len=strlen(valor);
for(i=0;i<len;i++){
 soma=soma*33^valor[i];
}
return soma%tamanho;
}

MAIN():

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "tabdispersao.h"
#define _CRT_SECURE_NO_DEPRECATE
int main(int argc, char *argv[]){
char buffer[250], *distritoNome, *concelhoNome, *freguesiaNome, *habitantesStr;
int HabitantesNum;
tabela_dispersao* tabela;
int valida = -1;
float tmp = clock();
freguesia freg;
char* nomeFicheiro = argv[1];
FILE *fp;
FILE *fo;
fp = fopen(nomeFicheiro,"r");
if(fp==NULL) {
 perror("O ficheiro não abriu.\n");
 exit(1);
}
fo = fopen("output.csv","w");
tabela = tabela_cria(100, &hash_djb);
while(!feof(fp)){
 fgets(buffer, 1000, fp);
 distritoNome = strtok(buffer, ",\n");
 if (distritoNome == NULL) break;
 concelhoNome = strtok(NULL, ",\n");
 if (concelhoNome == NULL) break;



Como posso por nitro nisto?
Para o programa correr mais rápido?
 freguesiaNome = strtok(NULL, ",\n");
 if (freguesiaNome == NULL) break;
 habitantesStr = strtok(NULL, ",\n");
 if (habitantesStr != NULL)
 {
  HabitantesNum = atoi(habitantesStr);
  freg.nome = freguesiaNome;
  freg.nHabitantes = HabitantesNum;
  if (tabela_adiciona(tabela, distritoNome, concelhoNome, &freg) != TABDISPERSAO_OK)break;
 }
 else
  continue;
 fprintf(fo, "%s, %s, %d\n", tabela->maiorConcelho->menorFreguesia->nome, tabela->maiorConcelho->distrito, tabela->maiorConcelho->menorFreguesia->nHabitantes);
}
tabela_apaga(tabela);
fclose (fp);
fclose (fo);
printf("FINISH!!!");
system("pause");
return 0;
}

pmg · May 25, 2012 at 10:17 AM

Como posso por nitro nisto?
Para o programa correr mais rápido?

Primeiro identificas a parte do programa em que precisas de meter nitro.

Depois, se possível, alteras essa parte.

Repete até o gasto (tempo / dinheiro / recursos/ ...) não compensar o ganho.

Por exemplo, se identificares o problema com a velocidade do disco: compra um disco mais rápido. Não adianta melhorar um programa que demora 15 segundos a ler do disco e 0.5 segundo no resto para outro que demora 15 segundos a ler do disco e 0.1 (5 vezes mais rápido!) no resto.

Happening · May 25, 2012 at 10:24 AM

É assim o tempo de resposta do programa também faz parte da avaliação neste momento depois de criar uma tabela com 100 de tamanho ele respondia com 40-45 mili. Altereia para 10000 e ele responde de 20-25 mili.

Também apaguei a função hash_kr que não utilizava e agr faz entre 10-20 mili.

Há alguma maneira de o por a correr mais rápido melhorando o código?

Edited May 25, 2012 at 10:40 AM by Happening

pmg · May 25, 2012 at 10:40 AM

Haver, deve haver ... mas aconselho-te a não ires por aí.

Já estás a usar uma estrutura de dados correcta para o problema. A tua hash-table e função de hashing parecem estar bem implementadas. O facto de demorar menos tempo com uma tabela maior significa que teve menos colisões.

Compila com o máximo de optimização e não te preocupes com picuinhices.

Qualquer optimização feita no código para este correr mais rápido irá, sem dúvida, tornar o código mais dificil de perceber ... e fazer perder tempo ao próximo programador que tenha de o alterar. O tempo de computador é mais barato que o tempo de programador --- e a diferença só tende a aumentar.

Happening · May 25, 2012 at 10:51 AM

Lá isso é verdade, vou então deixar assim. Considero que está um bom tempo de execução entre 10 mili e 20 mili.

Obrigado pela ajuda.

Agradeço imenso. Abraço 🙂

Surgiu um novo dado. A avaliação disto consiste em o programa ser robusto, sem memory leaks e só os 10% mais rápidos é que ficam entre o 19 e o 20. Mesmo que fique menos inteligivel...

Sabes de alguma forma de eu por isto mais rápido?

Sign In

Tabela Hash

Recommended Posts

Happening

pmg

Happening

pmg

Happening

pmg

Happening

pmg

Happening

pmg

Happening

pmg

Happening

pmg

Happening

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information