0

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!

2

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;
3
  • Thank you for replying. What do you mean by inserting at the end of the linked list? I made a second struct which contains a pointer to next node and initialized the hashtable array with it. It didn't decrease the time, but I'm sure that it's not the whole solution. – Cstudent Jan 17 '17 at 13:12
  • You append the new element to the list end. For that, you need to traverse the whole list. It's easier to set the new element's next pointer to the current list head and use the new element as the new list head. It's O(1), while appending to the end is O(n). – Blauelf Jan 17 '17 at 14:02
  • Wow, I see what you did there :) thank you! I have decreased the time substantially, from 2.97 seconds to 0.04 + learned something new. – Cstudent Jan 17 '17 at 18:56

You must log in to answer this question.

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