0

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

3

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!

  • Thanks! I managed to get 0.06 in total, is that good enough? – Mahmoud Khaled Aug 9 '16 at 13:43
  • That sounds pretty close to me. If this answered your question I would appreciate it if you accept the answer to keep up on forum maintenance. – NullityNull Aug 9 '16 at 16:22
  • thanks a lot!, my check function was giving me 0.17s and after changing the hashtable size from 500 to 200K it gives me 0.01~0.03s – Jung-min OK May 1 '17 at 5:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .