Loading dictionary words into a trie

Question

I have here a program created for pset5 of the CS50 course. The program compiles correctly and does as it should. However, is there any way to improve the run time of this program? Are there any pieces of code that are redundant and can be omitted? And is there anything that can be improved on in general?

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

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "dictionary.h"

typedef struct trie
{
    bool word;
    struct trie* children[27];
}trie;

trie* root;

unsigned int wordCount;

// Function that frees a node from the heap.
void freenode(trie* node)
{
    for (int i = 0; i < 27; i++)
    {
        if (node->children[i] != NULL)
        {
            freenode(node->children[i]);
        }
    }

    free(node);
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    int n = strlen(word);

    trie* node = root;

    for (int i=0; i < n; i++)
    {
        char c = tolower(word[i]);

        if (c == '\'')
        {
            // ASCII a (97) + 26
            c = 123;
        }

        struct trie* current = node->children[c-97];

        if (current == NULL)
        {
            return false;
        }
        else
        {
            node = current;
        }
    }

    if (node->word == true)
    {
        return true;
    }

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // Open the dictionary file
    FILE* d = fopen(dictionary, "r");
    if (d == NULL)
    {
        return false;
    }

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

    trie* node = root;

    for (char c = tolower(fgetc(d)); c != EOF; c = fgetc(d))
    {
        if (c == '\n')
        {
            if (node != root)
            {
                wordCount++;

                node->word = true;

                node = root;                
            }
        }
        else
        {
            if (c == '\'')
            {
                c = 123;
            }

            struct trie* current = node->children[c-97];
            if (current == NULL)
            {
                node->children[c-97] = calloc(1, sizeof(trie));

                node = node->children[c-97];
            }
            else
            {
                node = current;
            }

        }
    }

    fclose(d);

    return true;
}

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

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

Welcome to Code Review. Please explain what this exercise is about, and make that the title of the question. See How to Ask. As it stands, your title is simply an indication that the performance tag should be applied, and we have to guess what the objective is based on the comments, which makes your code hard to review. — 200_success
– 200_success, Commented May 3, 2017 at 16:30

vnp · Accepted Answer · 2017-05-03 16:44:21Z

10

If you feel you need a comment like this:
```
    // ASCII a (97) + 26
    c = 123;
```
it means that the code is not clear. Consider
```
    c = 'a' + 26;
```
While we can figure out the significance of 26 (size of an English alphabet, right?) again it is better to be explicit. What you want is the first character beyond the [a-z] range, so:
```
    c = 'z' + 1;
```
Similarly, node->children[c-97] should be node->children[c-'a'].

The

    if (node->word == true) {
        return true;
    }

    return false;

is a long way to say

    return node->word;

Avoid globals. Make load return root (or NULL on failure), and pass root to check as a parameter.
Test what calloc returns.
root = calloc(1, sizeof(trie)); requires the knowledge that root is trie *, and therefore results a double maintenance. A preferred idiom is
```
root = calloc(1, sizeof(*root));
```
Branching factor of 27 adds a huge overhead. Most nodes will use just a few pointers, so most of the allocated memory is wasted. This in turn results in poor cache utilization, and may directly affect the performance. Consider allocating just as much as you need, and searching instead of indexing. It may or may not improve performance. Profile and compare.

answered May 3, 2017 at 16:44

vnp

58.7k4 gold badges55 silver badges144 bronze badges

1

\$\begingroup\$ Small style simplification: root = calloc(1, sizeof(*root)); --> root = calloc(1, sizeof *root);. Drop (). \$\endgroup\$

chux
– chux

2017-05-03 21:09:29 +00:00
Commented May 3, 2017 at 21:09
1

\$\begingroup\$ @chux Correct. I must say I never understood the rationale of mandatory parens for a type vs optional parens for a variable, and since parens always work correctly I don't bother. \$\endgroup\$

vnp
– vnp

2017-05-03 21:11:54 +00:00
Commented May 3, 2017 at 21:11
\$\begingroup\$ I rationalize the parens around a type by imagining it's like a cast, but without a value because the value itself is irrelevant. Dunno if that helps, but it makes some kind of twisted sense to me! \$\endgroup\$

Toby Speight
– Toby Speight

2017-05-04 09:10:10 +00:00
Commented May 4, 2017 at 9:10

Add a comment |

Graipher · Accepted Answer · 2017-05-03 19:50:40Z

6

To improve performance replace the multiple calloc() with a single calloc() using size computed from the input file size.

This line appears to be incorrect:

for (char c = tolower(fgetc(d)); c != EOF; c = fgetc(d))

because none of the chars after the first is converted to lowercase. Replace with a while loop:

while ((char c= tolower(fgetc(d))) != EOF)

edited May 3, 2017 at 19:50

Graipher

41.7k7 gold badges70 silver badges134 bronze badges

answered May 3, 2017 at 19:42

cwallach

611 bronze badge

\$\begingroup\$ (char c= tolower(fgetc(d))) != EOF is an infinite loop on systems where char is unsigned. Better to use int ch. \$\endgroup\$

chux
– chux

2017-05-03 21:14:57 +00:00
Commented May 3, 2017 at 21:14
\$\begingroup\$ This doesn't work. I get an error saying error: expected expression while (int c = tolower(fgetc(d)) != EOF). I have defined c before the while loop with: int c= tolower(fgetc(d)); \$\endgroup\$

zalidael
– zalidael

2017-05-04 14:34:35 +00:00
Commented May 4, 2017 at 14:34
\$\begingroup\$ @chux When I do that, I get 6 errors telling me there's 'use of undeclared identifier 'c'' and error: expected ')' while ((char c= tolower(fgetc(d))) != EOF) ^ dictionary.c:92:12: note: to match this '(' while ((char c= tolower(fgetc(d))) != EOF) ^ dictionary.c:92:40: error: expected expression while ((char c= tolower(fgetc(d))) != EOF) \$\endgroup\$

zalidael
– zalidael

2017-05-04 14:48:03 +00:00
Commented May 4, 2017 at 14:48
\$\begingroup\$ @zalidael Yes, of course, There should be one declaration before the while() loop. int ch; and none in the loop while ((c = tolower(fgetc(d)) != EOF) { ... } (Also cleaning up some comments here.) \$\endgroup\$

chux
– chux

2017-05-04 15:05:18 +00:00
Commented May 4, 2017 at 15:05
\$\begingroup\$ @chux It compiles, but I had to add c = fgetc(d); just at the end of the while loop for the program to actually work correctly. \$\endgroup\$

zalidael
– zalidael

2017-05-04 15:52:42 +00:00
Commented May 4, 2017 at 15:52

Add a comment |

chux · Accepted Answer · 2017-05-04 14:38:32Z

5

Avoid magic numbers.

// Function that frees a node from the heap.
void freenode(trie* node) {
    // for (int i = 0; i < 27; i++)
    for (size_t i = 0; i < sizeof node->children / sizeof node->children[i]; i++)

    // or a bit cleaner
    size_t n = sizeof node->children / sizeof node->children[0];
    for (size_t i = 0; i < n; i++)

Minor: A simple pointer test is equivalent to testing against NULL.

    // if (node->children[i] != NULL) {
    if (node->children[i]) {
        freenode(node->children[i]);
    }

A C's free() allows free(NULL). I recommend that functionality for freenode(), which otherwise is UB.

void freenode(trie* node) {
    if (node) {
      ...
    }
}

Use size_t as the right-sized type for array indexing and sizing. It is the type returned by strlen(). int may be too small.

bool check(const char* word) {
  // int n = strlen(word);
  size_t n = strlen(word);

islower() is defined for int values in the range of unsigned char and EOF. Highly portable code accounts for that.

// char c = tolower(word[i]);
char c = tolower((unsigned char) word[i]);

GTG

edited May 4, 2017 at 14:38

answered May 3, 2017 at 21:27

chux

36.4k2 gold badges43 silver badges97 bronze badges

\$\begingroup\$ Thanks for the advice. However when I try to add the for loop you mentioned I get the following error: comparison of unsigned expression < 0 is always false. \$\endgroup\$

zalidael
– zalidael

2017-05-04 13:16:02 +00:00
Commented May 4, 2017 at 13:16
\$\begingroup\$ @zalidael Unclear. What exactly is the line of code you added? \$\endgroup\$

chux
– chux

2017-05-04 13:17:38 +00:00
Commented May 4, 2017 at 13:17
\$\begingroup\$ I added size_t n = sizeof node->children[i] / sizeof node->children[i][0]; for (size_t i = 0; i < n; i++) in replacement for the for loop. \$\endgroup\$

zalidael
– zalidael

2017-05-04 13:20:43 +00:00
Commented May 4, 2017 at 13:20
\$\begingroup\$ If I'm being more clear, I added size_t n = sizeof node->children[i] / sizeof node->children[i][0]; for (size_t i = 0; i < n; i++) gives me error: use of undeclared identifier 'i'. \$\endgroup\$

zalidael
– zalidael

2017-05-04 13:23:46 +00:00
Commented May 4, 2017 at 13:23
\$\begingroup\$ @zalidael Answer amended. Use size_t n = sizeof node->children[0] / sizeof node->children[0][0]; \$\endgroup\$

chux
– chux

2017-05-04 13:25:44 +00:00
Commented May 4, 2017 at 13:25

| Show 2 more comments

Stack Exchange Network

Loading dictionary words into a trie

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Loading dictionary words into a trie

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions