Do two sets of three numbers have at least two common numbers?
I just had to write a function that seemed easy to write, but when I did, it turned out to be more gorier than I expected. It worries me very much, I feel like there is a better solution, but my brain is going crazy trying to think about it, so I turn to you wonderful people.
Basically, I have two triangles and I want to know if they have a common edge. Triangles are indexed by their vertices (i.e., their vertices are just an index to the array containing the actual coordinates), so it boils down to finding if two sets of three numbers have two numbers in common. That is, the triangles (1,2,3) and (3,1,5) do indeed separate the edge, the edge (1,3). However, triangles (1,2,3) and (1,5,6) do not have edges (only vertices), nor do (1,2,3) and (4,5,6).
How would you write this "two numbers in a common function"? You can assume that all the values within each set are different (i.e. (1, 1, 2) will not enter), and you can also assume that the two sets are not equal to each other (i.e., I am not going to compare (1,2,3) and (1,3,2) since these two are the same triangle). However, there are no assumptions about the order, they are not sorted or anything like that.
This is basically what I ran into (assuming the sets (x0, x1, x2) and (y0, y1, y2)):
// If the x0 is equal to any of (y0, y1, y2), make sure at least one of (x1, x2)
// is equal to one of the y numbers
if (x0 == y0) {
return x1 == y1 || x1 == y2 || x2 == y1 || x2 == y2;
} else if (x0 == y1) {
return x1 == y0 || x1 == y2 || x2 == y0 || x2 == y2;
} else if (x0 == y2) {
return x1 == y0 || x1 == y1 || x2 == y0 || x2 == y1;
} else {
// if x0 is not equal to any of (y0, y1, y2), then x1 and x2 both have
// to be equal to two of the y numbers.
return (x1 == y0 && x2 == y1)
|| (x1 == y0 && x2 == y2)
|| (x1 == y1 && x2 == y0)
|| (x1 == y1 && x2 == y2)
|| (x1 == y2 && x2 == y0)
|| (x1 == y2 && x2 == y1);
}
but I like it so much! So many branches and such long boolean statements! I feel like I am missing an obvious simple solution and this is driving me crazy.
Also, this happens in an inner loop in a very performance sensitive application, so performance is important (branching, arithmetic, etc.).
By the way, the code I'm writing is C #, but the question is the same in a more or less imperative language.
EDIT:
I've put together a quick guide ( code here ) with suggestions so far. Here are the results (running them on a million random pairs of triangles):
Original method result: 7035, time elapsed in ms: 8.6252
qwertyman method result: 7035, time elapsed in ms: 8.2537
midjji method result: 7035, time elapsed in ms: 8.7984
Single HashSet method result: 7035, time elapsed in ms: 184.4984
Many HashSets method result: 7035, time elapsed in ms: 190.5785
The numbers remain fairly consistent to run, with @qwertyman's method always slightly faster than my original version or @midjii's. It also has the advantage of being the cleanest and prettiest of them all, so I'm going to go with that.
Actually I was a little surprised that "Many HashSets" was so close to "Single HashSet", I would have thought that creating a million HashSets would have more overhead than about 16 milliseconds (although this obviously does not account for the increased pressure to the garbage collector), although both are clearly far behind other methods.
Thanks for the help!
source to share
You can do something like this:
int n = 0;
// check if x0 is among the values in the second set
if (x0 == y0 || x0 == y1 || x0 == y2) {
n++;
}
// check if x1 is among the values in the second set
if (x1 == y0 || x1 == y1 || x1 == y2) {
n++;
}
// check if x2 is among the values in the second set
if (x2 == y0 || x2 == y1 || x2 == y2) {
n++;
}
return n >= 2;
It depends on the fact that (as you mentioned) the numbers in each set are different, which leads to simpler logic.
If you are using C, you can write it shorter:
int n = 0;
n += x0 == y0 || x0 == y1 || x0 == y2;
n += x1 == y0 || x1 == y1 || x1 == y2;
n += x2 == y0 || x2 == y1 || x2 == y2;
return n >= 2;
source to share
I would use:
...
{
//ti= xi in y
bool t0= (x0==y0) ||(x0==y1)|| (x0==y2);
bool t1= (x1==y0) ||(x1==y1)|| (x1==y2);
bool t2= (x2==y0) ||(x2==y1)|| (x2==y2);
return (t0 && t1) || (t0 && t2) || (t1 && t2);
}
Mostly because I think it's easier to read.
Effective, most likely it should be just as fast with the right settings. The compilers optimize themselves fantastically, don't attach any side effects, boolean assertions, and use lazy evaluation for bool (assuming nothing was done stupidly for ==).
source to share