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

Question

我做了半个程序做了一些重要的浮点运算。根据开始使用的数据，它可以生成描述线段的非常大的数组。使用带有浮点数的笛卡尔坐标系记录这些线段的位置，以记录直线两端的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);
}

我知道我有多少行，这就是“行”整数的含义。这段代码的工作原理是完全正确的，但与我的程序的其他部分相比，它的速度确实很慢。我想一定有更快的方法，但我不知道怎么做。拥有这个函数实在是太可惜了，因为它拖下了我程序的其余部分，考虑到所有浮点的数学运算，它的速度非常快。如果没有合适的方法使这个比它快3倍左右，我可能只需要忍受混乱的数据，并使下一个函数足够聪明来忽略它。但是，现在标记坏行将非常有用，因为下一个函数足够复杂，因为它没有试图补偿数据中的重复。

Answer 1

你的算法是N^2。您应该能够在N log N中做到这一点。然而，到达N log N所需的复杂性在某种程度上将取决于您的数据。

假设您的数据在X方向上分布良好，我将这样做。

1. 对于每个线段，如果需要的话，翻转它，使X< Q -这是O(N)。
2. 按X对所有线段进行排序--这是O(N log N).
3. 重复现在将是相邻的，所以一个简单的扫描可以删除它们。

这不是100%正确的，但得到粗jist的正确-你需要处理一些退化的案件。

1. 你做的是在翻转阶段的X==Q。(Ans )基于Y/Q的翻转，如果这也等于，那么使用Z/S)
2. 如果两个段在排序阶段有相同的X，你会怎么做。(Ans )以Y，Z，Q，R，S为次键。)