1

With the help of @Blauelf and @Yuri Laguardia, I finally made my code working (my previous question here). Then I diff my own results with the staff's, and found that my check() function seem to be the problem of slowing down the whole process. So I tried to tweak it, code provided below.

My question is, if misspelled words number is different from staff's, doesn't that mean my version of code is incorrect? How come it still pass check50?

bool check(const char* word)
{
    char tmpWord[LENGTH + 1];
    int wordLen = strlen(word);

    for (int i = 0; i < wordLen; i++) {
        int lowerChar = tolower(word[i]);
        tmpWord[i] = (char) lowerChar;
    }

    tmpWord[wordLen] = '\0';

    int hashValue = hash(tmpWord);

    // misspelled words = staff's
    // passed check50
    node* targetList = hashTable[hashValue];
    while (targetList != NULL) {
        if (strcmp(targetList->word, tmpWord) == 0) {
            return true;
        }

        targetList = targetList->next;
    }

    // with the following lines
    // misspelled words largely greater than staff's (16939 vs 644)
    // BUT also passed check50
    // WHY???

    // while (hashTable[hashValue] != NULL) {
    //     if (strcmp(hashTable[hashValue]->word, tmpWord) == 0) {
    //         return true;
    //     }

    //     hashTable[hashValue] = hashTable[hashValue]->next;
    // }

    return false;
}

See the records below:

With node* targetList = hashTable[hashValue]; :

// first time run

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         0.05
TIME IN check:        0.14
TIME IN size:         0.00
TIME IN unload:       0.03
TIME IN TOTAL:        0.22

// diff with staff
// check running slower
// same misspelled words as staff

WORDS MISSPELLED:     644                     WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091                  WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190                   WORDS IN TEXT:        19190
TIME IN load:         0.03                  | TIME IN load:         0.04
TIME IN check:        0.11                  | TIME IN check:        0.00
TIME IN size:         0.00                    TIME IN size:         0.00
TIME IN unload:       0.02                  | TIME IN unload:       0.01
TIME IN TOTAL:        0.16                  | TIME IN TOTAL:        0.05

Without node* targetList = hashTable[hashValue]; :

// first time run

WORDS MISSPELLED:     16939
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         0.06
TIME IN check:        0.04
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        0.10

// diff with staff
// check running much faster
// but misspelled words number is much greater than staff's

WORDS MISSPELLED:     16939                   | WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091                    WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190                     WORDS IN TEXT:        19190
TIME IN load:         0.04                    | TIME IN load:         0.02
TIME IN check:        0.02                      TIME IN check:        0.02
TIME IN size:         0.00                      TIME IN size:         0.00
TIME IN unload:       0.00                    | TIME IN unload:       0.01
TIME IN TOTAL:        0.06                    | TIME IN TOTAL:        0.05
2

The second one is incorrect and it only passes check50 because of the very small dictionaries that check50 uses.

In your original version, you create a pointer that points to the hashtable, and you traverse the linked lists by modifying that pointer.

The reason the second is wrong is that you are changing the values in the hashtable itself as you check each word.

So let's say you had the words apple apples applesauce in a linked list at hashtable[0] and you were searching for applepie. Your second code would set hashtable[0] = hashtable[0]->next if it didn't match with apple. So you've thrown apple out of the list entirely, because now hashtable[0] is pointing at the node with apples. Now you check again, and apples doesn't match, so you set hashtable[0] = hashtable[0]->next (which is the node for applesauce). You've thrown apples away. etc.

In your first case, you are simply pointing at apples and then applesauce.

2
  • Thank you! I got it! So I am getting more misspelled words because my second code's been throwing away words, right? Your explanation actually solve the problem I left in my other question as well. Thanks a lot!
    – Levblanc
    Oct 13 '16 at 9:26
  • Yes and that is why it was faster. Your dictionary was shrinking as it ran so that meant fewer words to search through.
    – curiouskiwi
    Oct 13 '16 at 18:35

You must log in to answer this question.

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