File under: Development, C, ancestor tree, linked list, optimisation
code / Common Tail, revisited
Doing dodgey things in C for fun and ... fun
Last time, I posted a solution to the problem of finding the common tail of two lists in C. The code was correct, but it was a little bit inefficient. It traverses both lists more than once, which annoyed me. I feel like I shouldn't have to visit each node more than once.
The task was:
... to find the first common parent of any two leaf nodes. What this boils down to is finding the common tail of two linked lists...
The last solution was a by-the-book solution. I get the length of both lists, shorten the long list, then compare the elements. It works, but it traverses the lists twice each. For long lists, this is necessary, because we might not have enough memory to create the data structures we need to speed this up. However if we assume that we are dealing with moderately small lists, then we can take note of all the elements in the list, so we don't have to revisit them a second time.
The simplest way to do this is to reverse both lists as you traverse them. Then when you get to the end of both lists, you start walking along the reversed versions, checking that the elements are the same for both lists. When the elements are different, you have found the end of your common tail.
But you should not do this in a production environment. Creating a complete copy of each node just to reverse a list is not good C style. We only need to keep track of a pointer to each node, so we use a classic structure - the linked list node. By tradition, it is called the cons.
typedef struct cons {
pointer car;
struct cons* cdr;
} cons;
Again by tradition, the pointer to your data is the car element. The cons element points to the next element of the list, which is another cons structure. You could call them data and list, but then how would Scheme programmers understand the code?
typedef struct node {
pointer data;
struct node* next;
} node;
We can't allocate a new cons for each node however, malloc is way too slow for that. Your project probably has its own version of malloc, and possibly its own flexible array struct, and routines to add and remove elements, resize the array etc. Unfortunately this a self-contained exercise, so I can't rely on any libraries. What I need is a data structure like a stack, that lets me add elements, and does its own memory allocation. Luckily C has one of these built in, it's called the stack.
The fun happens in this routine. Since it is a bit complex, I'll break it down.
TreeNode* findFirstCommonAncestorRec (TreeNode* A, TreeNode* B, cons* reverseA, cons* reverseB) {
cons rA = { A, reverseA};
cons rB = { B, reverseB};
if (A||B) {
return findFirstCommonAncestorRec(
A?A->parent:A,
B?B->parent:B,
A?&rA:reverseA,
B?&rB:reverseB);
} else {
if (!(reverseA->car==reverseB->car)) {
//The branches have no common root!
return NULL;
} else {
return findLastMatchingElement(
reverseA,
reverseB);
}
}
}
A and B are the lists we are checking for a common ancestor. So
A?A->parent:A
B?B->parent:B
Mean "if there is more list to follow, move to the next element". A list ends when the parent is NULL.
A?&rA:reverseA
B?&rB:reverseB
These pass the "reverse lists" forwards to the next step. If one list has finished (A), then we pass the reference to the front of the reversed list (reverseA). Otherwise, we add the current element of the list A to the front of the reversed list (reverseA), and we pass this new reversed A list (rA).
This is, incidentally, why I don't think code is inherently self documenting. Even though I wrote this code, I still have to pause for a while when I read it, to understand what it is actually trying to do (walk two lists and reverse them). Even the most familiar algorithms become difficult to understand once they are implemented (and optimised).
One further note:
rA and rB are declared as stack variables. We take a reference to them, which is normally a bug, because when findFirstCommonAncestorRec returns, the memory for rA and rB becomes invalid. Not invalid in a "segfault" way, just open to being silently overwritten. However findFirstCommonAncestorRec is recursive, so the references will be valid when we use them. rA and rB will be safe in this scenario. In a larger program, possibly not.
So findFirstCommonAncestorRec actually reverses both lists (using pointers), then calls findLastMatchingElement on the reversed lists. This seems like a lot of wonkery to get the same result as last time. Was it really worth it? Let's run the tests and see how fast each version is.
Tree.c is my original implementation, which uses a for loop and goes along each list twice. Tree_recursive is this new, improved version.
gcc tree.c
time: 0m18.068s
gcc Tree_recursive.c
time: 0m42.785s
That's terrible! I've wasted hours minutes for no benefit! Or did I?
gcc -O3 tree.c
time: 0m10.752s
gcc -O3 Tree_recursive.c
time: 0m6.741s
The recursive version runs in 60% of the time of the smaller, simpler version. Was it worth it? If this code was in the critical path, most definitely. Reducing the runtime by 40% in the critical path is a huge win. Any other time, probably not. The simpler version is easier to read and maintain, works for huge lists, and is much easier to understand.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef void* pointer;
typedef struct TreeNodeStruct {
struct TreeNodeStruct* parent;
} TreeNode;
typedef struct cons {
pointer car;
struct cons* cdr;
} cons;
/* Traverse two lists pairwise, checking that the elements in both lists are the same. Stop at the last element for which this is true. */
TreeNode* findLastMatchingElement (cons* A, cons* B) {
if ((!A->cdr)||(!B->cdr)) { return NULL;}
if ((!A->cdr->cdr)||(!B->cdr->cdr)) { return A->car;}
if (A->cdr->car == B->cdr->car) {
return findLastMatchingElement(A->cdr, B->cdr);
} else {
return A->car;
}
}
/* Traverse two lists to find the common tail (the common ancestor in this tree structure. */
TreeNode* findFirstCommonAncestorRec (TreeNode* A, TreeNode* B, cons* reverseA, cons* reverseB) {
cons rA = { A, reverseA};
cons rB = { B, reverseB};
if (A||B) {
return findFirstCommonAncestorRec(A?A->parent:A, B?B->parent:B, A?&rA:reverseA, B?&rB:reverseB);
} else {
if (!(reverseA->car==reverseB->car)) {
//The branches have no common root!
return NULL;
} else {
return findLastMatchingElement(reverseA,reverseB);
}
}
}
/* Take two leaf nodes, traverse towards the root node until we find a common node (if any) */
TreeNode* findFirstCommonAncestor (TreeNode* A, TreeNode* B) {
cons rA = {NULL, NULL};
cons rB = {NULL, NULL};
return findFirstCommonAncestorRec(A, B, &rA, &rB);
}
/* Test function: Create a linked list to test our functions on */
TreeNode* makeBranch (TreeNode* parent, int length) {
int i;
TreeNode* t;
TreeNode* prev_t = parent;
for (i=0;i<length; i++) {
t = (TreeNode*) calloc(1,sizeof(TreeNode));
t->parent = prev_t;
prev_t=t;
}
return t;
}
void test () {
//R is the root not of the tree
TreeNode* R = (TreeNode*) calloc(1,sizeof(TreeNode));
TreeNode* Rbranch = makeBranch(R,200);
TreeNode* A = makeBranch(NULL, 10);
TreeNode* B = makeBranch(NULL, 5);
TreeNode* C = makeBranch(R, 10);
TreeNode* D = makeBranch(R, 5);
TreeNode* E = makeBranch(Rbranch, 1000);
TreeNode* F = makeBranch(Rbranch, 500);
int i;
for (i=0; i<1000000; i++) {
//Check we handle NULL correctly
TreeNode* res = findFirstCommonAncestor(NULL, NULL);
assert(res==NULL);
//Check branches from different trees (no common root)
res = findFirstCommonAncestor(A,B);
assert(res==NULL);
//Check branches are separate up to the tree root
res = findFirstCommonAncestor(C,D);
assert(res==R);
//Check degenerate case
res = findFirstCommonAncestor(R,R);
assert(res==R);
//Check a real case
res = findFirstCommonAncestor(E,F);
assert(res==Rbranch);
//Check branchLength(B)>branchLength(A)
res = findFirstCommonAncestor(F,E);
assert(res==Rbranch);
}
}
int main(int argc, char* argv[])
{
test();
}