如何高效检测四个整数变量的对称性？

Question

我想在4个整数变量 i,j,k 和 l 中找到对称性。 这些对称性包括：

1. 四个数字相等：XXXX，
2. 三个数字相等：XXXY，XXYX，XYXX，YXXX
3. 两个数对相等：XXYY，XYXY，XYYX，...
4. 一个数对相等，另外两个不同：XXYZ，XYXZ，XYZX，...
5. 四个数字互不相同。

所有变量都在一定的非连续范围内运行。我使用嵌套的 if else 语句。第一个 if 检查所有变量是否不相等。如果不是，则属于情况1。下一个 if 检查是否存在任何相等的数对。如果不存在，则属于情况5。下一个 if 检查是否有三个相等的数。如果成立，则属于情况2。否则，最后一个 if 检查是否有两对相等的数。如果成立，则属于情况3，否则属于情况4。

  if(!(i==j && j==k && k==l)){
    if(i==j || i==k || i==l || j==k || j==l || k==l){
     if((i==j && j==k) || (i==j && j==l) || (i==k && k==l) || (j==k && k==l)){            ...//do something
     }else{
    if((i==j && k==l) || (i==k && j==l) || (i==l && j==k)){ 
...//do something
    }else{
     ...//do something
    }           
  }
     }else{
     ...//do something  
     } 
 }else{
  ...//do something
 }  

有更好的方法可以做到这一点吗？我的意思是更好的性能，因为我必须进行数百万次测试。

- Kulibo

---

我会先开始对这4个值进行排序，然后就变得非常简单了。 - Jabberwocky

这将取决于数字的范围和分布。例如，以极端情况为例，假设4个数字是随机的32位整数。在这种情况下，它们几乎总是不同的，因此您将优化首先测试该情况并转到不太常见的情况。在相反的情况下，所有4个数字都相等可能是最常见的情况。在这种情况下，您当前的方法将是最快的。 - samgak

将这些值复制到一个数组中并对它们进行排序。不要关注i、j、k、l，而是关注这个数组中的值，其中索引[0]是最低的。无论如何，这个问题太广泛了，即使作为算法/伪代码也无法回答，因为它不是一个问题，而是5个不同的问题。此外，优化严重依赖于它是否始终为4个项目或者项目数量应该是可变的。 - Lundin

如果您在（小）循环体内执行这些数百万次测试，请尝试优化代码大小，例如使用下面的samgak或Ari的解决方案，以便它能够很好地适应I-caches。否则，如果它是一个外部函数，您可以使用if-else分支级联if (i==j) { if (j==k) { if (k==l) { ... } else { ... } } else { if (k == l) {... } else { ... } ....来最小化比较次数。 - Ctx

如果您选择排序，请使用排序网络。但我认为您很快会发现Ari的答案更好。 - R.. GitHub STOP HELPING ICE

Answer 1

与samgak类似的思路，但无需外部表格。只需计算所有匹配项的总和即可。

int count = (i==j) + (i==k) + (i==l) + (j==k) + (j==l) + (k==l);

并使用以下选项进行switch

switch (count){
case 0: //All differenct
case 1: //One same
case 2: //Two different pairs
case 3: //Three same
case 6: //All are same
}

再次提醒，您当前的代码在某些情况下可能更快。尤其是在所有元素都相等的情况下，这是最常见的情况。

- Ari Hietanen

---

这明显是二次的，排序可以得到O(n log n)。哈希表将是O(n)，空间为O(n)。我想知道是否有一种使用常数空间的O(n)解决方案。 - 2501

我尝试过这个代码，它的行为很奇怪。 i、j、k、l 的值为：0000 0000 case 6 count:6 i、j、k、l 的值为：0001 0001 case 3 count:3 0001 case 6 count:3 i、j、k、l 的值为：0011 0011 case 2 count:2 0011 case 3 count:2 0011 case 6 count:2 i、j、k、l 的值为：0111 0111 case 3 count:3 0111 case 6 count:3 i、j、k、l 的值为：1111 1111 case 6 count:6。非常抱歉排版混乱，似乎相同数量的不同情况被调用了。 - Kulibo

@Kulibo，你需要在每个case的结尾写上break，否则它会在第一个true值之后执行所有的case。 - Ari Hietanen

@Kulibo 我认为你不可能比这更快了，因为在这个例子中，为了计算 count，多个指令将在单个时钟周期内执行，并且 switch 内部高度优化，使用不同的算法取决于案例数量。 此外，对于4个项，O(n*n) 冒泡排序可能是最快的 - 所以在这种情况下我不会太关注大O。 - Danny_ds

虽然对于非常小的集合，有更好的方法可以排序，但是与冒泡排序的O(n*n)而言，常规的O(n log n)可能会慢一些。 - Danny_ds

Answer 2

如果你可以承受一个小（64字节）的查找表，你可以测试每一对值并为每个比较设置一个位，这个位将作为一个索引值用于访问你的表格，例如：

int classifySymmetries(int i, int j, int k, int l)
{
     return table[(i == j) |
                  ((i == k) << 1) |
                  ((i == l) << 2) |
                  ((j == k) << 3) |
                  ((j == l) << 4) |
                  ((k == l) << 5)];
}

然后根据返回值进行开关判断。您可以使用现有的代码生成表格，通过为每个比较替换一些位测试或生成满足从0到63的每个位模式的虚拟i、j、k、l值。

这种方法需要6次恒定比较。请记住，对4个值进行排序需要4到5次比较（有4！=24种可能的排序方式，每次比较可产生1位信息）。但是还要在此基础上进行基于已排序值的测试。

无论是否使用查找表优于当前方法将取决于数值分布和其他因素，如内存访问时间，应进行性能分析以进行确认。

- samgak

---

你的意思是(i == j) >> 0, (i == k) >> 1, (i == l) >> 2吗？我无法理解(i == l) & 4，因为它总是0，不是吗？ - Ctx

是的，但是要向另一个方向移动。 - samgak

Answer 3

更好的方法是使用映射表：

#include <iostream>
#include <map>
using namespace std;


int main()
{
    int i, j, k, l;
    cin >> i >> j >> k >> l;

    std::map<int, int> count;

    int outcomes[5] = { 0, 0, 0, 0, 0 };

    // Store the values in the map
    count[i]++;
    count[j]++;
    count[k]++;
    count[l]++;

    // tally types of outcome according to the map
    for(typename std::map<int, int>::iterator iter = count.begin(); iter != count.end(); ++iter)
    {
        outcomes[iter->second] ++;
    }

    // print out "1 of a kind" count, up to "4 of a kind"
    // this is just for visualization
    for (int i = 1; i <= 4; ++i)
    {
        cout << i << " of a kind = " << outcomes[i] << endl;
    }

    // your bit here, it checks on just the "outcomes" array
    if(outcomes[4] > 0) // 4 of a kind
    {
    }
    else if(outcomes[3] > 0) // 3 of a kind
    {
    }
    else if(outcomes[2] > 1) // two pair
    {
    }
    else if(outcomes[2] > 0) // one pair
    {
    }
    else // singles only
    {
    }

    cin.ignore();
    cin.get();

    return 0;
}

如果您想将其扩展到4个以上的选项，这种方法也会更加灵活。

- Jason Lang

---

这个解决方案可能有太多额外的开销，因此在处理少于4个值时可能不是很高效。 - Jabberwocky