0

Speller was really tough for me, had to learn a lot of extra material to get it right. But still, even though I've used trie, I've implemented the solution rather very inefficiently.

Here are some comparison between my solution and that of the staff for AustinPowers.txt

Mine:
WORDS MISSPELLED: 644
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 19190
TIME IN load: 0.10
TIME IN check: 0.02
TIME IN size: 0.00
TIME IN unload: 0.06
TIME IN TOTAL: 0.18

Staff:
WORDS MISSPELLED: 644
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 19190
TIME IN load: 0.02
TIME IN check: 0.02
TIME IN size: 0.00
TIME IN unload: 0.02
TIME IN TOTAL: 0.05


Comparing our both's solution with Valgrind I see that my code allocates a lot of memory and of much sizes.

MY Valgrind Summary:
==12691== HEAP SUMMARY:
==12691== in use at exit: 0 bytes in 0 blocks
==12691== total heap usage: 367,084 allocs, 367,084 frees, 82,227,504 bytes allocated
==12691==
==12691== All heap blocks were freed -- no leaks are possible
==12691==
==12691== For counts of detected and suppressed errors, rerun with: -v
==12691== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Staff Valgrind Summary:
==12724== HEAP SUMMARY:
==12724== in use at exit: 0 bytes in 0 blocks
==12724== total heap usage: 143,093 allocs, 143,093 frees, 2,585,092 bytes allocated
==12724==
==12724== All heap blocks were freed -- no leaks are possible
==12724==
==12724== For counts of detected and suppressed errors, rerun with: -v
==12724== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)


Here's my dictionary.c

/**
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>

#include "dictionary.h"

typedef struct node
{
    bool isWord;
    struct node *children[ALPHABETS];
} node;

// allocate our main node root
node *root = NULL;

int dicSize = 0; // dictionary size mind you

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    // prepare to check
    char c;
    int key;

    // a temp node pointer same as root for every word
    node *trav = root;

    // iterate over every letters in the word
    for(int i = 0, n = strlen(word); i < n; i++)
    {
        // store the current letter
        c = tolower(word[i]);

        // find key equivevalent of c
        if(isalpha(c))
        {
            key = c - 97;
        }
        else if (c == '\'')
        {
            key = 26;
        }

        // if current node's children is not NULL move trav else return false
        if(trav->children[key] != NULL)
            trav = trav->children[key];
        else
            return false;
    }

        if (trav->isWord == true)
            return true;
        else
            return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    // open dictionary file
    FILE* Dict = fopen(dictionary,"r");

    if (!Dict)
    {
        return false;
    }

    // prepare to load Dict in memory as Trie
    int key;
    char c;
    char word[LENGTH];

    root = calloc(1, sizeof(node));

    // iterate through every word from Dict until EOF
    while((fscanf(Dict, "%s", word)) != EOF)
    {
        // a temp node pointer same as root for every word
        node *trav = root;

        // iterate over every letters in the word
        for(int i = 0, n = strlen(word); i < n; i++)
        {
            // store the current letter
            c = word[i];

            // find the key equivalent of current key
            if (c == '\'')
                key = 26;
            else
                key = c - 97;


            // if next child does not exist, give birth to it
            if (trav->children[key] == NULL)
                trav->children[key] = calloc(1, sizeof(node));

            // move trav to the next child
            trav = trav->children[key];
        }
            // at the end of the word, set isWord to true
            trav->isWord = true;

        // update dicSize
        dicSize++;
    }

    fclose(Dict);
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    return dicSize;
}

/**
 * Unloads dictionary from memory.
 */
void unloadMain (node* ptr)
{
    if (ptr == NULL)
        return;
    for(int i = 0; i < ALPHABETS; i++)
    {
        if (ptr->children[i] != NULL)
            unloadMain(ptr->children[i]);
    }
    free(ptr);
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    unloadMain(root);
    return true;
}

I'll be very grateful if you could point me out in the right direction.

0

You're comparing apples to oranges. The staff solution is not using a trie, but probably a hashmap. Therefore, they allocate exactly one node (of a linked list) per entry, with that node being smaller on average (224 bytes for your trie nodes, 17.3 bytes on average for their linked-list nodes).

Interestingly, their average node seems to be around 17 bytes, which is not enough to store the longest word allowed per specification. So I assume they allocate as much memory as required for a given word, not wasting extra bytes.

| improve this answer | |
  • Thanks for your answer. I understand that has tables are much friendlier to memory. But I thought a trie is supposed to be faster for dictionary implementations on the expanse of memory. Care to comment on this? – Mittal Shubham Sep 15 '17 at 14:01
  • We see the heap memory allocated, but not stack memory, where the hash map's array probably resides. There's a tradeoff memory vs. access time. Maybe they used a relatively large hashmap with the longest linked list being relatively short (but also not too large, as at some point this slows down especially unload as well). Also, in this range, the results might spread quite a bit (have you repeated your measurements a few times?). – Blauelf Sep 15 '17 at 14:10
  • Yeah, even with different texts, results are always very similar. – Mittal Shubham Sep 15 '17 at 14:14

You must log in to answer this question.

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