How to make the check function faster?

Question

It seems to be taking too much more time comparing to staff's implementation. The other 3 functions are average, though.

dictionary.c: https://gist.github.com/9dcb901f2007d09ae1c9c4fa934f13df

Mine:

WORDS MISSPELLED: 644

WORDS IN DICTIONARY: 143091

WORDS IN TEXT: 19190

TIME IN load: 0.03

TIME IN check: 2.45

TIME IN size: 0.00

TIME IN unload: 0.01

TIME IN TOTAL: 2.50

Staff's:

WORDS MISSPELLED: 644

WORDS IN DICTIONARY: 143091

WORDS IN TEXT: 19190

TIME IN load: 0.04

TIME IN check: 0.02

TIME IN size: 0.00

TIME IN unload: 0.02

TIME IN TOTAL: 0.08

Answer 1

The reason why your check function is slow is because of how the dictionary is loaded into memory. There are two things to do to right this:

1.) Find a good hash function online like this one I found on a Reddit post that performs pretty close to the staff's solution:

// Ref: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/
inline int hashValue(const char *word)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(word); i<n; i++) {
        hash = (hash << 2) ^ word[i];
    }
    return hash % HASHTABLESIZE;
}

2.) Increase the size of your hash table. Generally the more bins, the more focused individual hashed keys are and therefore less searching that the program has to do (faster!). This does take up more memory however, but since the goal is to make it really fast and not so much memory efficient, go right ahead and use as much memory as you want!