0

I've already completed pset5 and optimized it as best I can, but, as I've decided to store the dictionary in a trie, the load time is really high, at around 0.10.

Here's how I implemented load():

bool load(const char* dictionary)
{
    FILE *infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        return false;
    }

    // root of trie
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        return false;
    }
    // initialises each element of pointers as NULL and isend as false
    for (int i = 0; i < 27; i++)
    {
        root->pointers[i] = NULL;
    }
    root->isend = false;

    // pointer to traverse trie
    node *index = root;
    // pointer to store new nodes generated
    node *newnode;

    // read every character of infile until EOF
    for (char c = fgetc(infile); c != EOF; c = fgetc(infile))
    {
        if (c == '\n')
        {
            index->isend = true;
            index = root;
            // counts size of dictionary while loading, removing the need to    traverse trie twice to check size
            count++;
        }
        else if (c == '\'')
        {
            if (index->pointers[26] == NULL)
            {
                // creates new node if one doesn't exist already
                newnode = malloc(sizeof(node));
                if (newnode == NULL)
                {
                    return false;
                }
                // initialises each element of pointers as NULL and isend as false
                for (int i = 0; i < 27; i++)
                {
                    newnode->pointers[i] = NULL;
                }
                newnode->isend = false;

                // add newnode to index's pointers and move to that node
                index->pointers[26] = newnode;
                index = index->pointers[26];
            }
            else
            {
                // if node already exists, move to that node
                index = index->pointers[26];
            }
        }
        else
        {
            // creates new node if one doesn't exist already
            if (index->pointers[c-97] == NULL)
            {
                newnode = malloc(sizeof(node));
                if (newnode == NULL)
                {
                    return false;
                }
                // initialises each element of pointers as NULL and isend as false
                for (int i = 0; i < 27; i++)
                {
                    newnode->pointers[i] = NULL;
                }
                newnode->isend = false;

                // add newnode to index's pointers and move to that node
                index->pointers[c-97] = newnode;
                index = index->pointers[c-97];
            }
            else
            {
                index = index->pointers[c-97];
            }
        }
    }

    fclose(infile);
    return true;
}

The struct for my trie is as follows:

// individual nodes that comprise a trie to store dictionary in memory
typedef struct trie
{
    // the first 26 elements represent lowercase alphabetical characters; 
    // the 27th element represents an apostrophe
    struct trie *pointers[27];
    bool isend;
} node;

Having done my best to optimize my code, I've managed to reduce the time for size() and unload() to almost 0, but I still can't make a sizeable dent in load(). Can anyone give me any tips on how people have managed to get load times of 0.02 or 0.03 on http://speller-leaderboard.freehostia.com/public/show ?

Any help would be much appreciated :)

2

Instead of calling malloc so many times, try using calloc and create an array of node.

unsigned datasize = 0; node* nodes = calloc(200000, sizeof(node));

Then you return allocated nodes addresses instead of malloc.

newnode = &nodes[datasize++];

To make this solution even better you may add check for datasize be not greater than allocated space, otherwise create new array of node.

This solution reduces load time from 0.10 to 0.08. Try structure is really memory consuming (> 80MB), so I think it's ok. Moreover, unload timings become 0.01.

  • get a segmentation fault when I try this approach. Is the declaration of calloc faulty perhaps? Does node* need to be an array itself? How are you able to access the memory using &nodes[datasize]? – Super12man Dec 4 '16 at 4:39

You must log in to answer this question.

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