How to make it faster? Speller Week5 CS50

Viewed 30

I believe there is a problem in hash function or a check, because I got these results of speed when I compile:

TIME IN load: 0.02

TIME IN check: 0.31

TIME IN size: 0.00

TIME IN unload: 0.01

TIME IN TOTAL: 0.35

and benchmark is:

TIME IN load: 0.03

TIME IN check: 0.03

TIME IN size: 0.00

TIME IN unload: 0.02

TIME IN TOTAL: 0.08

I would appreciate your help and knowledge in optimizing code to make it faster.

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// TODO: Choose number of buckets in hash table
const unsigned int N = 10000;

// Hash table --> will be structured alphabetically
node *table[N];
unsigned int count_words = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int index = hash(word);

    node *test = table[index];

    while (test != NULL)
    {
        if (strcasecmp(test->word, word) == 0)
        {
            return true;
        }
        test = test->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    unsigned int sum = 0;
    int index = 0;
    while (word[index++] != '\0')
    {
        sum += toupper(word[index]) - 'A';
    }
    return (sum % N);
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    FILE *dict = fopen(dictionary, "r");

    if (dict == NULL)
    {
        return false;
    }

    // "mot" in french means word
    char mot [LENGTH + 1];

    // Read all words from dictionary
    while (fscanf(dict, "%s", mot) != EOF)
    {
        int index = hash(mot);
        node *new = malloc(sizeof(node));

        if (new == NULL)
        {
            unload();
            return false;
        }

        strcpy(new->word, mot);
        new->next = table[index];
        table[index] = new;

        count_words++;

    }
    fclose(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    return count_words;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO

    for (int i = 0; i < N; i++)
    {
        node *temp = table[i];
        while (temp != NULL)
        {
            node *clear = temp;
            temp = temp->next;
            free(clear);
        }
    }

    return true;
}
0 Answers
Related