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;
}