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

Question

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

3

我需要编写一个看似简单的函数，但实际上比我预期的要复杂得多。这让我很困扰，我感觉应该有更好的解决方案，但我的大脑正在疯狂地思考，因此我转向你们这些出色的人。基本上，我有两个三角形，我想知道它们是否共享一个公共边缘。这些三角形是通过它们的顶点进行索引的(即它们的顶点只是包含实际坐标的数组的索引)，因此关键在于找到两组三个数字是否有两个数字相同。例如，三角形(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的方法快一些。它还具有最干净和最好的优点，所以我会选择那个方法。

实际上，我有点惊讶于“许多HashSets”与“单个HashSet”如此接近，我认为构造一百万个HashSets的开销比大约16毫秒要大（尽管这显然不包括垃圾收集器上的增加压力），尽管它们显然都远落后于其他方法。

感谢您的帮助！

- Oskar

2

你使用的是哪种编程语言？ - xenteros

很多事情取决于你如何表示你的集合。此外，它们是真正的集合吗？（保证元素唯一） - RealSkeptic

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

2

@Oskar：如果高性能是关键因素，你应该在问题中提到。由于你目前的方法的抱怨似乎与速度无关，而是与它看起来不好 - 这更可能鼓励人们提供可读性较高而非高性能的算法。 - Chris

@chris 我本以为“这发生在一个非常注重性能的应用程序的内部循环中，因此性能（分支、算术等）很重要”已经足够清楚了。 - Oskar

显示剩余10条评论

2个回答

1

我会使用：

...
{
  //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类型使用惰性求值（假设没有对==做出愚蠢的修改）。

- midjji

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- danbanica · Accepted Answer

您可以像这样操作：

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;