两组三个数字是否有至少两个共同的数字？

问题描述：

我只是写了一个看起来很简单的函数，但是当我真的做到了时，结果比我预期的要更高。这真的让我感到困扰，我觉得有一个更好的解决方案，但是我的大脑疯狂地想着想，所以我正在转向你。两组三个数字是否有至少两个共同的数字？

基本上，我有2个三角形，我想知道他们是否有共同的边缘。三角形由它们的顶点索引（即它们的顶点只是包含实际坐标的数组的索引），所以它归结为查找两个三个数字集合是否有两个共同的数字。即三角形（1,2,3）和（3,1,5）确实共享边缘，即（1,3）边缘。但是，三角形（1,2,3）和（1,5,6）不共享边（仅顶点），也不共享（1,2,3）和（4,5,6）。

你会如何写这个“两个数字在共同的功能”？你可以假设每个集合中的所有值是不同的（即（1,1,2）不会是一个输入），你也可以假设两个集合不相等（即，我不打算比较（1,2,3）和（1,3,2），因为那两个是相同的三角形）。然而，没有关于秩序的假设，他们没有排序或类似的东西。

这基本上就是我想出了（假设集是（X0，X1，X2）和（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); 
}

但感觉如此血腥的我！如此多的分支和如此长的布尔语句！我觉得我错过了一个明显简单的解决方案，而且这让我疯狂。另外，这种情况发生在对性能敏感的应用程序的内部循环中，因此性能（分支，算术等等）很重要。

顺便说一句，我正在编写的代码是C＃，但问题是或多或少任何命令式语言相同。

编辑：

我把一个快速基准（这里的code）与到目前为止建议。下面是结果（以百万随机对三角形的运行它）：

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

的数字相当稳定运行之间，用@ qwertyman的方法始终是一个有点比我原来的版本或@ midjii的速度更快。它还具有成为所有人中最干净和最好的优点，所以我打算继续这样做。

我实际上对“许多HashSet”如此接近“Single HashSet”感到有点惊讶，我想构建一百万个HashSet的开销会比16毫秒大（尽管这显然不计算在内垃圾收集器的压力增加），尽管它们显然远远落后于其他方法。

感谢您的帮助！

你在用什么语言？ – xenteros

很大程度上取决于你如何表示你的设置。另外，它们是否是真集？（保证元素是唯一的） – RealSkeptic

根据您使用的语言，只需将数字存储在实际集合中，并使用库函数计算交集的大小。 –

答

你可以做这样的事情：

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;

这依赖于一个事实，即（如你所提到的）每一组数字是不同的，导致一个简单的逻辑。

如果您使用的是C，你可以把它写短：

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;

在第二个C示例中，转换||会更快吗？另外，为了避免短路造成的分支？ – Oskar

顺便说一下，我意识到我们现在谈论的是微小的优化，但我真的需要尽可能快的代码。另外，我很好奇:) – Oskar

它让我很好奇 - 我做了一个基准测试，并且首先设置了[0,300]中的数字，而且时间非常相似，而对于“ “变种。但是，短路发生的情况很少。之后，我还对[0,15]中的x和y值进行了实验，“+”变量更快（可能是因为此处短路发生更频繁，难以预测分支）。 – qwertyman

答

我会用：

... 
{ 
    //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); 
}

主要是因为我觉得它更容易阅读。

从性能角度看，使用正确的设置应该尽可能快。编译器在优化自我封闭，无副作用，逻辑语句和对bool使用惰性评估方面非常出色（假设==没有做任何愚蠢的事情）。

两组三个数字是否有至少两个共同的数字？

相关推荐