Mój tytuł został zredagowany, więc chciałem się upewnić, że wszyscy wiedzą, że to zadanie domowe. Problem polega na tym, aby zoptymalizować program, a moim pomysłem jest mieszanie.

-

Pracuję nad optymalizacją programu C, który grupuje ze sobą słowa będące anagramami, a następnie drukuje je.

Obecnie program jest połączoną listą połączonych list. Każde łącze na liście zewnętrznej jest grupą słów, które są anagramami siebie.

Profil programu pokazuje, że zdecydowanie największą część czasu wykonania stanowi funkcjawordLookup. Dzieje się tak, ponieważ musi przeszukiwać każdy węzeł, a przy możliwym odczytaniu 100k słów z pliku może to zająć bardzo dużo czasu. Na przykład tutaj jestgprof wyjście do odczytu w 40k słów:

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

Moim pomysłem na przyspieszenie tego procesu jest zmiana struktury danych na tablicę mieszania, która łączy wszystkie anagramy ze sobą w tym samym gnieździe.

Opierając się na tym, co powiedział mój profesor, i na tym, co tutaj przeczytałem, myślę o czymś takim dla mojej funkcji skrótu. (Uwaga: liczby pierwsze są rozmieszczone w taki sposób, że najczęściej używane litery to małe liczby, a najmniej używane to liczby duże).

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
}

Czy istnieje rozmiar tabeli mieszania dla tego problemu, który odpowiednio rozdzieliłby wartości w taki sposób, że każda grupa anagramów ma odrębny indeks w tabeli?

Jeśli nie jest to możliwe, to czy powinienem:

połączyć listy słów razem (lista list)użyj rozwiązania sondującego (liniowego lub kwadratowego)Dla każdego z tych scenariuszy, jakie są plusy / minusy w porównaniu?