user52485 user52485 - 3 years ago 123
C Question

Fastest way to find other node

I have a triangle class, with pointers to nodes (n0,n1,n2). I also have a method that returns the 'other' node when passed two node pointers (a,b). The current implementation is this:

if ( n0 == a && n1 == b )
{
return n2;
}
else if ( n0 == b && n1 == a )
{
return n2;
}
else if ( n1 == a && n2 == b )
{
return n0;
}
else if ( n1 == b && n2 == a )
{
return n0;
}
else if ( n0 == a && n2 == b )
{
return n1;
}
else if ( n0 == b && n2 == a )
{
return n1;
}
else
{
assert( 0 );
}
return NULL;


Which works, but may not be best. Upon profiling, my program actually spends measurable time in this routine, so it is worth some time to optimize. However, I'm not very familiar with the optimizations the compiler will do anyway, so I'm not sure if this is redundant.

The nodes are in no particular order, so on average it will have to perform 3.5 of the compound comparisons.

An alternative approach would be this:

if ( n0 == a )
{
if ( n1 == b )
{
return n2;
}
else if ( n2 == b )
{
return n1;
}
return NULL;
}
else if ( n1 == a )
{
if ( n0 == b )
{
return n2;
}
else if ( n2 == b )
{
return n0;
}
return NULL;
}
else if ( n2 == a ) // Theoretically redundant. Kept for safety.
{
if ( n0 == b )
{
return n1;
}
else if ( n1 == b )
{
return n0;
}
return NULL;
}
return NULL;


Which works out to an average of 3.5 of the simple comparisons. Will this be faster -- or will the compiler make them the same?

Is there a faster way?

I know I could eliminate the redundant if's. In the first case, it reduces the average to 3.33 compound comparisons. In the second case, it pulls the average down to 3.0 simple comparisons.

I could eliminate all the else's as every true block of code contains a return. However, I really feel like the compiler should be smart enough to take care of any gain there itself.

Answer Source

Anything XORed with itself will be zero, so if you're given two of the three, you can find the remaining one by just doing n0 ^ n1 ^ n2 ^ a ^ b. It's well deserving of an explanatory comment, but if speed matters, that's almost certainly your fastest alternative.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download