长阵列性能问题

Question

我有一个char长度为175,000 的指针数组.每个指针指向一个长度为100的c字符串数组,每个字符都是1或0.我需要比较字符串之间的差异.

char* arr[175000];

到目前为止,我有两个for循环,我将每个字符串与每个其他字符串进行比较.比较函数基本上采用两个c字符串并返回一个整数,该整数是数组的差异数.

这在我的4核机器上花了很长时间.上次我离开它运行45分钟,它从未完成执行.请告知更快的解决方案或一些优化.

---

例:

000010
000001

由于最后两位不匹配,因此差异为2.

在我计算差异后,我将值存储在另一个数组中

                int holder;

                for(int x = 0;x < UsedTableSpace; x++){
                    int min = 10000000;

                    for(int y = 0; y < UsedTableSpace; y++){

                        if(x != y){
                            //compr calculates difference between two c-string arrays
                            int tempDiff =compr(similarity[x]->matrix, similarity[y]->matrix);

                            if(tempDiff < min){
                                min = tempDiff;
                                holder = y;
                            }
                        }       
                    }
                    similarity[holder]->inbound++;

                }

Answer 1

有了更多的信息,我们可能会给你更好的建议,但根据我对这个问题的理解,这里有一些想法:

1. 由于您使用每个字符来表示1或0,因此您使用的内存比您需要的内存多几倍,这在缓存等方面会产生很大的性能影响.相反,使用您可以根据一系列位思考的数值来表示您的数据.
2. 一旦你实现了#1,你可以一次抓取一个整数或一个长整数并进行按位XOR运算,最终得到一个数字,在这两个数字不具有相同值的每个地方都有1.然后你可以使用这里提到的一些技巧来快速计算这些位数.

3. 努力"展开"你的循环,以避免必要的跳跃次数.例如,以下代码:

   total = total + array[i];
   total = total + array[i + 1];
   total = total + array[i + 2];
   

   ...将比循环total = total + array[i]三次更快地工作.跳转很昂贵,并且会干扰处理器的流水线操作. 更新:我应该提一下你的编译器可能已经为你做了一些 - 你可以查看编译后的代码看看.

4. 将整个数据集分成多个块,以便您充分利用缓存.将您的问题视为"正方形",i其中一个轴上的索引和另一个轴上的j轴.如果从一个开始i并遍历所有175000个j值,则j访问的第一个值将在到达行尾时从缓存中消失.另一方面,如果你从左上角开始并从j = 0变为256,那么j轴上的大多数值仍将处于低级缓存中,因为你循环将它们与i = 0,1进行比较,2等

最后,虽然这应该不言而喻,我想值得一提的是:确保你的编译器设置为优化!