title: cs50 pset5 Speller optimisation
body: <p>I've completed speller and passed all checks. But I'm still bugged about the performance. I did my best with research and running tests, but my implementation is slower by 10-20% compared to staff's one. How can I improve my code?</p>
  <pre><code>    // Implements a dictionary's functionality
  
  #include &lt;ctype.h&gt;
  #include &lt;stdbool.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  #include &lt;strings.h&gt;
  #include &quot;dictionary.h&quot;
  
  // Represents a node in a hash table
  typedef struct node
  {
      char word[LENGTH + 1];
      struct node *next;
  }
  node;
  //Prototypes
  unsigned int hash(const char *word);
  
  // TODO: Choose number of buckets in hash table
  const unsigned int N = 187751; //odd prime number bigger than word count, because math
  
  // Hash table
  node *table[N]; //may need to use calloc
  
  //word count
  int word_count = 0;
  
  // Returns true if word is in dictionary, else false
  bool check(const char *word)
  {
      // TODO
      //debug
      //int hashcode = hash(word);
      //printf(&quot;bucket: %i, word: %s\n&quot;, hash(word), table[hash(word)]-&gt;word);
      for (node *tmp = table[hash(word)]; tmp != NULL; tmp = tmp-&gt;next) //iterate through bucket
      {
          if (strcasecmp(tmp-&gt;word, word) == 0) //compare strings
          {
              return true;
          }
      }
      return false;
  }
  
  // Hashes word to a number
  unsigned int hash(const char *word)
  {
      // TODO: Improve this hash function
      //Used Data Structures youtube course of Dr. Rob Edwards from San Diego State University mostly
      int hash = 0;
      /*int w = 0;
      //convert to upper case
      while (word[w] != '\0')
      {
          word[w] = toupper(word[w]);
          w++;
      }*/
      for (int i = 0; i &lt;= strlen(word); i++)
      {
          hash = (31 * hash + toupper(word[i])) % N; //31 because math
          //check hash size
          /*if (hash &gt;= N)
              {
                  printf(&quot;incorrect hash!&quot;);
              }*/
      }
      return hash;
  }
  
  // Loads dictionary into memory, returning true if successful, else false
  bool load(const char *dictionary)
  {
      // TODO
      //open dictionary file
      FILE *dict = fopen(dictionary, &quot;r&quot;);
      if (dict == NULL)
      {
          //printf(&quot;Could not open file.\n&quot;);
          return false;
      }
      //create temp string for word
      char *word = malloc(LENGTH + 1);
      if (word == NULL)
      {
          return false;
      }
      //read words from dictionary and write to hash table
      while (fscanf(dict, &quot;%s&quot;, word) != EOF)
      {
          //node *tmp_word = NULL;
          node *n = malloc(sizeof(node));
          if (n == NULL)
          {
              return false;
          }
          int pos = hash(word); //run hash to find the bucket in table
          strcpy(n-&gt;word, word); //write word to temp node
          if (table[pos] == NULL) //check if node is first in bucket (may need to use calloc to create a table)
          {
              n-&gt;next = NULL;
          }
          else //if not the first, write node to the head
          {
              n-&gt;next = table[pos]; //reference first node
          }
          table[pos] = n; //write node to table
          word_count++; //count new word
      }
      fclose(dict);
      free(word);
      //debug
      /*int j = 0;
      while (j &lt;= 11)
      {
          for (node *tmp = table[j]; tmp != NULL; tmp = tmp-&gt;next) //делаем ноду; пока не дойдем до последней; переходим к следующей
                  {
                      printf(&quot;%s\n&quot;, tmp-&gt;word); //забираем значение ноды
  
                  }
          printf(&quot;Bucket number: %i\n&quot;, j);
          j++;
      }*/
      //printf(&quot;word count:%i\n&quot;, word_count);
      return true;
  }
  
  // Returns number of words in dictionary if loaded, else 0 if not yet loaded
  unsigned int size(void)
  {
      return word_count;
  }
  
  // Unloads dictionary from memory, returning true if successful, else false
  bool unload(void)
  {
      // TODO
      for (int i = 0; i &lt;= N; i++)
      {
          while (table[i] != NULL)
          {
              node *tmp = table[i]-&gt;next; //делаем ноду и переходим на следующую ячейку
              free(table[i]); //освобождаем текущую
              table[i] = tmp; //начинаем list со второй ячейки
          }
      }
      return true;
  }
  </code></pre>
  <p>My results:</p>
  <pre class="lang-none prettyprint-override"><code>WORDS MISSPELLED:     955
  WORDS IN DICTIONARY:  143091
  WORDS IN TEXT:        17756
  TIME IN load:         0.04
  TIME IN check:        0.02
  TIME IN size:         0.00
  TIME IN unload:       0.01
  TIME IN TOTAL:        0.07
  </code></pre>
  <p>Cs50 staff's results:</p>
  <pre class="lang-none prettyprint-override"><code>WORDS MISSPELLED:     955
  WORDS IN DICTIONARY:  143091
  WORDS IN TEXT:        17756
  TIME IN load:         0.02
  TIME IN check:        0.02
  TIME IN size:         0.00
  TIME IN unload:       0.01
  TIME IN TOTAL:        0.06
  </code></pre>
  <p>I've already played with bucket size, to no avail(((</p>
  <p>Pset5 instructions: <a href="https://cs50.harvard.edu/x/2022/psets/5/speller/" rel="nofollow noreferrer">https://cs50.harvard.edu/x/2022/psets/5/speller/</a></p>
  <p>I'm also including dictionary.h, if you need one. Check is getting string from another text file, not the one used in load.</p>
  <pre><code>#ifndef DICTIONARY_H
  #define DICTIONARY_H
  
  #include &lt;stdbool.h&gt;
  
  // Maximum length for a word
  // (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
  #define LENGTH 45
  
  // Prototypes
  bool check(const char *word);
  unsigned int hash(const char *word);
  bool load(const char *dictionary);
  unsigned int size(void);
  bool unload(void);
  
  #endif // DICTIONARY_H
  </code></pre>
  <p>My question was pretty much perfectly answered by <a href="https://stackoverflow.com/users/5382650/craig-estey">Craig Estey</a>. His code runs uber-fast compared to mine and faster than cs50 staff's:
  <a href="https://i.stack.imgur.com/hbNqx.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/hbNqx.png" alt="Lalaland" /></a></p>
  <p>Bigger text:
  <a href="https://i.stack.imgur.com/wETV5.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/wETV5.png" alt="Xueqin" /></a></p>
  <p>I've learned alot and am really greateful. That's my first question here, on SO and I've never anticipated it to be so helpfull and friendly place.</p>