任何人都可以破译为什么这个 'find unique values' 进程不能按预期工作吗？

Question

目标是对于一个变量，它是一个数组:

typedef struct {
 GLuint vertex;
 GLuint normal;
} indice_pairs_t;

，我们想要找到所有唯一的对，并将它们以适当的顺序出现，并且唯一对索引保持不变。

例如:如果初始对是

2 3
6 7
6 7
4 5

(第二和第三对相同)

那么最后的顺序就是

0 1 1 2

('2 3' 是 0，第一个 '6 7' 是 1，第二个 '6 7'；'4 5' 是 2，依此类推)

以下代码尝试这样做，但最终顺序似乎总是“0 1 2 3 4 5”，依此类推。如果'打破;'被删除，它变得一团糟；增量太多。

// First is always unique and first in order:
unique[0] = pairs[0];
order[0] = 0;
num_unique = 1;

// Skip first, we just did it:
for (i = 1; i < num_pairs; i++) {

 // Check if what we have is already the same
 for (y = 0; y < num_unique; y++) {

  if (unique[y].vertex == pairs[i].vertex&&unique[y].normal == pairs[i].normal) {
   /* A new pair was found to be the same; put the old unique index in order;
    keep num of unique items same: */
   order[i] = y;
  } else {
   /* A new pair was unique; copy it in unique pairs and increment number
    of unique items; put in order the new number */
   unique[num_unique] = pairs[i];
   order[i] = num_unique;
   num_unique++; // it follows since it was already incremented to 1.
   break;
  }

 }

}

Answer 1

这是一个非常低效的算法。复杂度为 O(n²)。通过使用排序序列，您可以做得更好。

你所拥有的显然是错误的，但这个想法似乎很清楚。对于每个新值 (next i)，都会检查该值是否已经存在于目前存储的唯一值中。这就是内部循环的用途。如果找到匹配项，order[i] = y 和下一个 i 应该被检查，因此您可以break。但是，如果未找到当前 y 的匹配项，则需要检查下一个 y。只有检查完所有 y 后，您才知道该值是唯一的，因此应该将 else 子句中的部分移到内部循环之外。我认为固定版本应该是这样的:

unique[0] = pairs[0];
order[0] = 0;
num_unique = 1;

// Skip first, we just did it:
for (i = 1; i < num_pairs; i++) {

    // Check if what we have is already the same
    for (y = 0; y < num_unique; y++) {

        if (unique[y].vertex == pairs[i].vertex && unique[y].normal == pairs[i].normal) {
            /*  A new pair was found to be the same; put the old unique index in order;
                keep num of unique items same: */
            order[i] = y;
            break;
        }
    }
    if(y == num_unique){
    /* No match was found in the inner loop,
       so y reached num_unique. You could use a flag
       to indicate this, which might be more readable*/

        /*  A new pair was unique; copy it in unique pairs and increment number
            of unique items; put in order the new number */
        unique[num_unique] = pairs[i];
        order[i] = num_unique;
        num_unique++; // it follows since it was already incremented to 1 in the beginning.
    }
}