Meu título foi editado, então eu queria ter certeza de que todo mundo sabe que isso é lição de casa. O problema é apenas otimizar o programa, o hashing é minha ideia.

-

Estou trabalhando na otimização de um programa em C que agrupa palavras que são anagramas umas das outras e depois as imprime.

Atualmente, o programa é basicamente uma lista vinculada de listas vinculadas. Cada link na lista externa é um grupo de palavras que são anagramas umas das outras.

O perfil do programa mostra que, de longe, a maior parte do tempo de execução é a funçãowordLookup. Isso ocorre porque ele precisa pesquisar todos os nós e, com as possíveis 100 mil palavras lidas de um arquivo, isso pode levar muito tempo. Por exemplo, aqui está ogprof saída para leitura em 40k palavras:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  us/call  us/call  name
100.31      1.48     1.48    40000    37.12    37.12  wordLookup
  0.00      1.48     0.00    78235     0.00     0.00  newnode
  0.00      1.48     0.00    40000     0.00     0.00  sort_string
  0.00      1.48     0.00    38235     0.00     0.00  wordInsert
  0.00      1.48     0.00     1996     0.00     0.00  swap_words
  0.00      1.48     0.00     1765     0.00     0.00  wordAppend

Minha ideia para tornar isso mais rápido é alterar a estrutura de dados para uma tabela de hash que encadeia todos os anagramas uns dos outros no mesmo slot.

Com base em coisas que meu professor disse e coisas que eu li aqui, estou pensando em algo assim para a minha função de hash. (Nota: os números primos são distribuídos de tal forma que as letras mais usadas são números baixos e os menos usados ​​são números altos.)

sort(string)

array alpha_primes = 5,71,37,29,2,53,59,19,11,83,79,31,43,13,7,67,97,23,17,3,41,73,47,89,61,101
hash(String) {
  hash = 1
  for (char in String) {
    hash *= alpha_primes[char-'a'];
  }
  return hash % tablesize
}

Existe um tamanho de tabela de hash para esse problema que distribuir adequadamente os valores de modo que cada grupo de anagramas tenha um índice distinto na tabela?

Se isso não for possível, então eu deveria:

encadear as listas de palavras juntas (lista de listas)use uma solução de sondagem (linear ou quadrática)Para qualquer um desses cenários, quais são as vantagens / desvantagens quando comparados?