RE: Exemplo freq (hashing)

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Marcos Lemos writes:
 > Alguém já testou o programa freq que se encontra na página ?
 >      Eu o testei com a seguinte entrada:
 >       lemos
 >       yoshi
 >       lemos
 >       knuth
 >       yoshi
 >       knuth
 > 
 >      E obtive a seguinte saída :
 >          
 >      lemos 2 
 >    
 >      ..., ou seja, simplesmente o programa não contou as palavras "yoshi"
 > e "knuth".

Eu experimentei rodar com a sua entrada e obtive o seguinte:

======================================================================
<4>[random:/home/yoshi/examples/mac122] > freq < tmp.txt 
yoshi 2
lemos 2
knuth 2
Numero de palavras lidas = 6
Numero de comparacoes feitas = 3
Numero medio de comparacoes feitas por palavra lida = 0.500000
Numero de palavras distintas = 3
Numero esperado de palavras por lista ligada = 0.002973
<5>[random:/home/yoshi/examples/mac122] > cat tmp.txt
lemos
yoshi
lemos
knuth
yoshi
knuth
<6>[random:/home/yoshi/examples/mac122] > 
======================================================================

Experimente fazer o seguinte.  Troque a definicao da funcao pelo seguinte: 

/********************************************************************/
long hash_div(char *s)                                     
{@+                       
  long h;
  for (h=0; *s!='\0'; s++)
    h=(258*h+(unsigned char)*s)%HASH_PRIME;
  return h;
}
/********************************************************************/

Para ser totalmente coerente, talvez voce queira tambem trocar a declaracao de
h_valor para 

long h_valor;

mas isto nao é estritamente necessario.  

O que deve estar acontecendo é o seguinte.  No calculo de h, deve estar dando
overflow em um dos passos em que se calcula 

  258*h+(unsigned char)*s

Aí, quando se calcula este valor %HASH_PRIME, obtemos um numero negativo.
Infelizmente, em C, quando fazemos uma operacao do tipo a%b e tem numeros
negativos envolvidos, nao podemos ter certeza sobre o sinal de a%b (bem, isto
falando a grosso modo). 

Concluindo, provavelmente o seu compilador e o gcc (que estou usando) tem
limites diferentes para os maiores inteiros que eles podem aceitar em
variaveis tipo int.

No gcc, 

INT_MAX=2147483647
INT_MIN=-2147483648

LONG_MAX=2147483647
LONG_MIN=-2147483648

Isto é, tanto para int como para long, os valores admissiveis sao tais que 

-2^31 <= x <= 2^31-1.

Provavelmente isto é diferente em seu compilador.  Para saber quais sao os
limites nele, escreva um programinha que imprime as constantes

INT_MAX e INT_MIN,

definidas em <limits.h>.  Veja Seçao B.11 de Kernighan & Ritchie.

Boa sorte!

Yoshi 

 >      Bem, no cálculo do h_valor, substituí 258 por 128:
 > 
 >         h = (128 * h + (unsigned char) *s) % HASH_PRIME;
 > 
 >      Aí o programa retornou a resposta correta:
 >      lemos 2
 >      yoshi 2
 >      knuth 2
 >      Fiz alguns testes e descobri que com o valor 258, o programa estava
 > tentando armazenar a palavra "yoshi" na posição -302 do vetor!!!
 >      Será que este problema está acontecendo somente comigo ? Gostaria que
 > alguém verificasse...
 > 
 > Lemos