c - 如何优化 "Find all possible triangles without duplicates"代码

Question

我有一个 C 程序可以找到所有可能的三角形(例如 3 3 4 4 5 5 => 20 个三角形，其中 7 个没有重复)。我设法通过连接 a、b、c 以 abc 格式存储所有三角形来做到这一点，但我的程序太慢了。我发现找到所有三角形的函数对于 1000 个数字和 uniq() 函数需要 1.68 秒。(限制为2s):

int getTriangles(const int nosniky[], int N, int trojuhelniky[]) {
  int count = 0;
  tcount = 0;
  // The last triangle found
  int TEMP = 0;

  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      for (int m = j + 1; m < N; m++) {
        int a = nosniky[i];
        int b = nosniky[j];
        int c = nosniky[m];

        if (a + b > c && a + c > b && c + b > a) {
          // Order a,b,c so that a<b<c
          order(&a, &b);
          order(&a, &c);
          order(&b, &c);
          count++;
          // Triangle will be stored as abc, so we need to join all ints into
          // one (3,3,4 => 334)
          int temp = joinInts(a, b);

          if (i == 0 && j == 1 && m == 2) {
            // first triangle, for example a=3,b=3,c=4 => 334
            TEMP = joinInts(temp, c);
            tcount++;
            trojuhelniky[tcount - 1] = joinInts(temp, c);
          } else if (joinInts(temp, c) == TEMP) {
            // This is a duplicate, ignoring this one
          } else {
            tcount++;
            trojuhelniky[tcount - 1] = joinInts(temp, c);
            // TEMP = the new last found triangle
            TEMP = joinInts(temp, c);
          }
        }
      }
    }
  }
  // Remove remaining duplicates, 1.68s as well
  int newcount = uniq(trojuhelniky, tcount);
  return newcount;
}

我对输入进行排序，将“最后找到的”三角形存储在 TEMP 变量中，然后检查下一个是否相同，如果不同，则下一个三角形是新的 TEMP。这样我就摆脱了大部分重复项，我在 uniq() 函数中删除了其余部分。

所以我的问题是，我可以做些什么来提高我的代码速度？我已经设法从 6s 到 3.2s，现在我卡住了。

最好的情况是在 3 个 for 循环中实时删除重复项，但我不知道该怎么做，所以我现在最好的选择是尝试优化我不太好的代码 :D

编辑:“三角形”是指 a+b>c、b+c>c 和 a+c>b，因此对于输入 3 3 4 4 5 5，我应该找到 20 种可能的组合来满足该要求.删除重复项后，结果应为 7(3,3,4 与 4,3,3 相同)。

编辑 2:输入范围为 3 到 1000 个随机整数。这是 uniq() 函数:

int uniq(int *a, size_t len) {
size_t i, j;

qsort(a, len, sizeof(int), icmp);

for (i = j = 0; i < len; i++) {
    if (a[i] == 0) {
        break;
    }
    if (a[i] != a[j]) a[++j] = a[i];
}
return (int) j + 1;
}

输入 2 9 18 4 1 5 19 6 3 1 2 8 的输出应该是 27。

Answer 1

首先请注意，如果您保证输入数组已排序，同时保持 i < j < m ，你永远不会得到 (3,4,3) 的组合。服用

    int a = nosniky[i];
    int b = nosniky[j];
    int c = nosniky[m];

将使(a,b,c)一个非递减序列。所以这根本不是问题。

但是，当您的输入数据包含重复项时，您可以获得重复项。例如，输入 3,4,4,5你得到相同的三元组 (a,b,c) = (3,4,5) for (i,j,m) = (0,1,3) and for (i,j,m) = (0,2 ,3).

为了避免这种情况，您只需要以巧妙的方式增加 i,j,m 以跳过重复项:if nosniky[1] == 4和 nosniky[2] == 4你不应该增加 j从 1 到 2，而是不断递增直到找到 nosniky[j]不同于nosniky[j-1] (或者您点击 j == N )。

  int count = 0;

  .....  // sort nosniky[] in ascending order here
  
  for (int i = 0; i < N;) {
    int a = nosniky[i];

    for (int j = i + 1; j < N;) {
      int b = nosniky[j];

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (a + b > c && a + c > b && c + b > a) {
          int temp = jointInts(joinInts(a, b), c);

          trojuhelniky[count] = temp;
          count ++;
        }
        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }
      while (++j < N && nosniky[j] == b)
        ; // skip duplicates of the second edge
    }
    while (++i < N && nosniky[i] == a)
      ; // skip duplicates of the first edge
  }

  return count;

顺便说一句，一旦你保证nosniky[]数组已排序，你知道c不小于a和 b .然后，正如@pmg 在评论中指出的那样，三角不等式的测试可以简化为第一次比较，因为剩下的两个肯定是满足的:

        if (a + b > c) {
          int temp = jointInts(joinInts(a, b), c);

          trojuhelniky[count] = temp;
          count ++;
        }

---

如果你只需要数三角形就可以了，不需要把它们都收集起来，你可以简化最内层的循环:

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (a + b > c) {
          count ++;
        }
        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }

---

按照 Michael Dorgan 评论中的建议，您可以通过提前终止长度为 c 的搜索来节省一些时间。已知太大:

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (c >= a + b)    // too large
          break;           // skip the rest

        if (a + b > c) {
          count ++;
        }
        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }

然后下一个条件变成重言式，因为它是前一个条件的否定，因此我们可以去掉它:

      for (int m = j + 1; m < N;) {
        int c = nosniky[m];

        if (c >= a + b)    // too large
          break;           // skip the rest

        count ++;

        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }

---

如果您期望 N 的值非常大, 你也可以尝试通过 c 优化搜索太小的值，例如二分查找。您将需要一个二进制搜索函数，该函数接受一个要搜索的数组、一系列索引和一个目标值，并返回等于或大于目标的第一个值的索引(位置)(如果是，则返回范围的右端)未找到)。

      int c_minimal = b - a;

      // do binary search for c_minimal
      // between indices j+1 (inclusive) and N (exclusive)
      int initial_m = search(nosniky, j+1, N, c_minimal);

      // start from the first value big enough
      for (int m = initial_m; m < N;) {
        int c = nosniky[m];

        if (c >= a + b)   // too large
          break;          // skip the rest

        count ++;

        while (++m < N && nosniky[m] == c)
          ; // skip duplicates of the third edge
      }