PSET5 - spell checker. How can I make my code faster?

Question

My code for pset5 works reasonably well, it passes check50 and isn't orders of magnitude slower than the staff solution, but I'm just wondering where I am losing time. I'm running my code on the large dictionary, checking austinpowers text file.

I've tried playing about with HSIZE (number of buckets) and a value of about 10000 seems to produce the best results with the large dictionary, these are my benchmarks:

TIME IN load: 0.03

TIME IN check: 0.07

TIME IN size: 0.02

TIME IN unload: 0.02

TIME IN TOTAL: 0.14

The staff solution seems to be making up a lot of time in check, but i'm also losing time in size and unload. I know my hash function isn't the best, so I was thinking maybe it's not assigning to buckets uniformly?

Any advice would be appreciated, be as critical as you want!

Thanks

#include "dictionary.h"

//store the bucket location
node *hashtable[HSIZE] = {NULL};
FILE *dp = NULL;


//Returns true if word is in dictionary else false.

bool check(const char *word)
{
    //for the word in the text file, find our what bucket it would be in
    node *cursor = hashtable[hash(word)];

    //traverse the linked list, comparing the word from the text file and the word in each node, if we hit a null pointer
    //and the function hasnt returned true, then we know the word isn't in the dictionary, so leave loop and return false
    while(cursor != NULL)
    {
        if(strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor->next;    
        }
    }
    return false;
}


//Loads dictionary into memory. Returns true if successful else false.

bool load(const char *dictionary)
{

    //open the dictionary
    dp = fopen(dictionary, "r");
    if (dp == NULL)
    {
        return false;
    }

    //load each word in to the dictionary
    char dword[LENGTH+1];
    unsigned int hf = 0;


    while (fscanf(dp, "%s", dword) != EOF)
    {

        //create a new node
        node *new_node = malloc(sizeof(node));

        if (new_node == NULL)
        {
            unload();
            return false;
        }
        else
        {
            //copy word in to new node
            strcpy(new_node->word,dword);

            //hash the word
            hf = hash(dword);

            //insert node in to the beginning of the buckets linked list
            new_node->next = hashtable[hf];
            hashtable[hf] = new_node;

        }

    }
    return true;
}


//Returns number of words in dictionary if loaded else 0 if not yet loaded.

unsigned int size(void)
{

    if(dp == NULL)
    {
        return 0;
    }
    else
    {
        //move file pointer to beginning of file
        fseek(dp, 0, SEEK_SET);

        unsigned int size = 0;

        //count the number of newlines, will return the size of the dictionary
        for (int c = fgetc(dp); c != EOF; c = fgetc(dp))
        {
            if (c == '\n')
            {
                 ++size;
            }
        }

        fclose(dp);
        return size;
    }
}


//Unloads dictionary from memory. Returns true if successful

bool unload(void)
{
    for(int i = 0; i<HSIZE; ++i)
    {

        //assign cursor to head of each list
        node *cursor = hashtable[i];

        //traverse the list, freeing memory as cursor moves along, until reach null pointer
        while(cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }

    return true;
}

//hash function
unsigned int hash(const char *hword)
{
    //hash the word, add up the asci values and mod by the hash table size
    unsigned int h = 0;
    for(int i = 0; i<strlen(hword); ++i)
    {
        h += toupper(hword[i]);
    }

    //mod the sum of asci values by the hash table size
    h = h % HSIZE;

    return h;
}

Answer 1

The issue of optimization is difficult, but since your dictionary works you can have a lot of fun testing things (sometimes it's the only way). We can see some things, for example we can use a large prime number for HSIZE (9941 for example), this reduces the number of collisions, it is also allowed to search hash functions on the internet, although I found it fun to create my own function.

unsigned int size(void)

I do not remember well the implementation of size, but it seems a little complex, the fseek function is going to be a considerable waste of time, I'm sure you have an optimization opportunity.