2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 7
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success May 3 '17 at 16:30
10
\$\begingroup\$
  • 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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Small style simplification: root = calloc(1, sizeof(*root)); --> root = calloc(1, sizeof *root);. Drop (). \$\endgroup\$ – chux - Reinstate Monica May 3 '17 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 May 3 '17 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 May 4 '17 at 9:10
6
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ (char c= tolower(fgetc(d))) != EOF is an infinite loop on systems where char is unsigned. Better to use int ch. \$\endgroup\$ – chux - Reinstate Monica May 3 '17 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 May 4 '17 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 May 4 '17 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 - Reinstate Monica May 4 '17 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 May 4 '17 at 15:52
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\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 May 4 '17 at 13:16
  • \$\begingroup\$ @zalidael Unclear. What exactly is the line of code you added? \$\endgroup\$ – chux - Reinstate Monica May 4 '17 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 May 4 '17 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 May 4 '17 at 13:23
  • \$\begingroup\$ @zalidael Answer amended. Use size_t n = sizeof node->children[0] / sizeof node->children[0][0]; \$\endgroup\$ – chux - Reinstate Monica May 4 '17 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.