c - 如何在 C 中尽可能快地标记数组中的重复数据？

Question

我已经编写了半个程序来执行一些主要的 float 学运算。根据它开始的数据，它可以生成描述线段的非常大的数组。这些线段的位置是用笛卡尔坐标系记录的，用 float 来记录线段每一端的X、Y、Z位置。我不能在两端都使用 X、Y、Z，所以我在开始时使用 X、Y、Z，在结束时使用 Q、R、S。所以基本上我想做的是标记所有相同或翻转的行，以便第一行的 Q、R、S 等于第二行的 X、Y、Z，第一行的 X、Y、Z 等于Q,R,S 在第二行。我目前的标记技术是将 X 设置为 -1，因为我知道没有一条线会以负坐标结束。我不想标记这两条线，只是除了一条线之外的所有线。这是我当前的功能:

int filter(int lines)
{
printf("Filtering...\n");
refline=0;
scanline=1;
while(refline<(lines))
    {
        if( segpointX[refline] == segpointQ[scanline] && segpointY[refline] == segpointR[scanline] && segpointZ[refline] == segpointS[scanline] && segpointQ[refline] == segpointX[scanline] && segpointR[refline] == segpointY[scanline] && segpointS[refline] == segpointZ[scanline] 
         || segpointX[refline] == segpointX[scanline] && segpointY[refline] == segpointY[scanline] && segpointZ[refline] == segpointZ[scanline] && segpointQ[refline] == segpointQ[scanline] && segpointR[refline] == segpointR[scanline] && segpointS[refline] == segpointS[scanline])
            {
                //printf("Origional: %f  %f  %f  ><  %f  %f  %f\n",segpointX[refline],segpointY[refline],segpointZ[refline],segpointQ[refline],segpointR[refline],segpointS[refline]);
                //printf("Duplicate: %f  %f  %f  ><  %f  %f  %f\n\n",segpointX[scanline],segpointY[scanline],segpointZ[scanline],segpointQ[scanline],segpointR[scanline],segpointS[scanline]);
                segpointX[scanline]=-1;
            }

         scanline++;

        if(scanline==lines+1)
            {
                refline++;
                scanline=refline+1;
            }   
    }
return(0);
}

我知道我有多少行，这就是“行”整数。这段代码完全按照它应该的方式工作，但与我程序的其余部分相比它真的很慢。我认为必须有一种方法可以更快地做到这一点，但我不确定如何做。拥有这个功能真的很遗憾，因为它拖累了我的程序的其余部分，考虑到它的所有 float 学，它的速度非常快。如果没有合适的方法让它比现在快 3 倍左右，我可能不得不忍受困惑的数据，并让下一个函数足够聪明以忽略它。然而，现在标记错误行将非常有用，因为下一个函数已经足够复杂了，而无需尝试补偿我的数据中的重复项。

Answer 1

标记数组中重复项的经典方法是以某种方式对数组进行排序 (O(N·logN))，然后在一次传递 (O(N)) 中标记/删除连续的相同元素；这具有总复杂度 O(N·logN)，而您的方法是 O(N²)。

在您的情况下，所有困难都归结为在数据点之间建立某种排序关系。

首先，我会将您的线条格式标准化，以便以相同的方式表示等效的线条(相同的端点)。为此，对每一行比较元组 (XYZ)/(QRS)；如果 Q 小于 X，则 QRS 与 XYZ 交换；如果 X==Q，则检查 Y 和 R，如果它们再次等于 Z 和 S。

在此 O(N) 次遍历结束时，所有等效行都具有相同的 XYZQRS 表示。

现在，如果您不想更改数据的表示形式(6 个独立的数组，其中单个 struct 数组会更简单、更高效)，则更容易对数据进行排序索引数组而不是实际数据(另外，如果您不想更改实际数据的顺序，它可能更有效，甚至是唯一可行的可能性)。用从 0 到 lines-1 的数字初始化一个整数数组；然后，您可以使用 qsort 函数进行排序，并传递您的自定义比较器函数。

此函数将接收要比较的索引；您将使用这些索引来访问相应的 XYZ/QRS 并按顺序比较它们(将第一个元素的 X 与第二个元素的 X 进行比较，如果它们相等，则继续进行 Ys，依此类推)。在排序结束时，您的索引数组将被排序，相同的项目位于附近。

现在你可以做最后一步了:扫描索引数组，并将当前索引对应的元素与下一个索引对应的元素进行比较:如果它们相等，则将第一个标记为重复；否则否则，您要么处于重复序列的最后一项，要么处于新序列的开头，因此您需要(至少暂时)保留此项。由于项目是有序的，相同的项目都排成一排，因此您可以一次性标记它们。

---

请注意，只有当您需要精确匹配时，这才会正确工作 - 即它不会考虑 FP 的不准确性。