2

I have implemented dictionary as a trie and it's working fine. Check50 okays it, so does valgrind. Now, comparing the running times, my check() is as fast as the staff solution, but load() and unload() are three to four times slower (my 6 to 8ms vs staff's 2ms).

Load involves reading from file and allocating memory in many little chunks, so there can certainly be significant differences in implementation. But what stumps me is the difference in unload(). All my free_node() function does is recursively call itself for each of a node's children, and then it frees the node it was passed. A for loop and a free() call, nothing else. Not sure if it's ok to post working code here, so in pseudocode:

function free_node( node )
{
    if node is not NULL
    {
        for each item in children
        {            
            free_node( node->children[this_item] ) // recursive call
        }        
        free( node )
    }
} 

I really can't see how this could be made any faster, let alone three times as fast - unless the number of nodes were significantly smaller. So my one guess is that the staff solution does not use a trie, but is there a way to know, or to optimize the above any further?

1
  • Maybe they are using a hashmap instead. Hashmaps have O(1) insert (but O(n) check for constant number of bins), and unload requires two nested loops, no recursion. Overall performance depends on how much those different things are used. – Blauelf Apr 12 '17 at 13:24
1

Well, recursive code is sometimes the most elegant solution but most of the times, it's not the most optimal solution.

Every time you call a function, a new entry for that function and all its local variables has to be created in the stack, so that the program knows how to return to the calling function. This is called a backtrace. You can read more about the stack (and the heap, and their differences) here.

What would be a more optimal way, is to do the freeing via a loop, and not a recursive way. I think that's what the staff has done.

Just create an array of pointers to nodes and treat it as a FIFO (First In First Out) storage (a queue basically). Start by adding the root node to the queue. Then in a loop, get the first node in queue, add it's children nodes that are not null to the end of the queue, free the current node, and go to the next node in the queue. Stop when the current node is NULL.

That's a rough diagram of what you could do, and there are certainly other ways to achieve the same goal (releasing the memory within a loop and not recursively) that are going to be faster than your current solution.

Happy coding!

You must log in to answer this question.

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