How can I optimize load in pset5

Question

I'm trying to optimize my load function (after using gprof to profile speller), as it takes 99.6% time of my program. How can I do it? Here is dictionary.c: /* This function opens a dictionary file and loads it to the memory via hash table */

bool load(const char *dictionary)
{

    FILE* dict;
    size_t index=0; // hashTable array index
    char word[LENGTH]; //LENGTH = 45 (longest word in English)
    struct node* current;
    dict = fopen(dictionary,"r");

    if (dict == NULL || hashTable == NULL){
        printf ("cannot open dictionary file\n");
        fclose(dict);
        return false;
    }

    while(fscanf(dict, "%s", word) != EOF){
        index = getIndex(word); //uses hash function to generate index for hashTable
        struct node* nodeNew = malloc( sizeof(struct node)); //node is a struct with word from dictionary and pointer to the next node
        if (nodeNew == NULL){
            printf("cannot allocate memory for new node when loading dictionary\n");
            fclose(dict);
            return false;
        }
        amountWords++; //words counter
        strncpy(nodeNew->word, word, LENGTH);
        nodeNew->next = NULL;

        current = &hashTable[index];

        /* iterate over nodes until reached to the end of the chain */
        while ( current != NULL && current->next != NULL){
            current = current->next;
        }
        current->next = nodeNew;

    }
    for (int i=0; i<TABLE_SIZE; i++){ //TABLE_SIZE = 26 (size of English alphabet)
        current = &hashTable[i];
        while (current != NULL){
            current = current->next;
        }
    }
    fclose(dict);
    return true;
}
size_t getIndex(const char* s){
    return ((*s)-'0') % TABLE_SIZE;
}

Thank you!

Answer 1

You insert at the end of the linked list. Insertion is faster at the beginning. Instead of

    nodeNew->next = NULL;

    current = &hashTable[index];

    /* iterate over nodes until reached to the end of the chain */
    while ( current != NULL && current->next != NULL){
        current = current->next;
    }
    current->next = nodeNew;

do something like

    nodeNew->next = hashTable[index]->next;
    hashTable[index]->next = nodeNew;

or even better, make your hashTable an array of node pointers, not nodes (a linked list could easily be empty, represented by a NULL pointer), and do something like

    nodeNew->next = hashTable[index];
    hashTable[index] = nodeNew;