c++ - 长数组性能问题

Question

我有一个长度为 175,000 的 char 指针数组。每个指针指向一个长度为 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 后，您可以一次获取一个完整的整数或长整数，然后执行按位异或运算，最终得到一个数字，该数字在两个数字没有的每个地方都有一个 1相同的值。然后你可以使用一些the tricks mentioned here快速计算这些位。

3. 稍微“展开”您的循环以避免必要的跳跃次数。例如下面的代码:

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

   ... 将比仅循环遍历 total = total + array[i] 三次更快。跳转是昂贵的，并且会干扰处理器的流水线。 更新:我应该提一下，您的编译器可能已经为您完成了其中的一些工作——您可以查看编译后的代码。

4. 将您的整体数据集分成多个 block ，以便您充分利用缓存。将您的问题想象成一个“正方形”，一个轴上有 i 索引，另一个轴上有 j 索引。如果您从一个 i 开始并遍历所有 175000 个 j 值，那么您访问的第一个 j 值将在此时从缓存中消失你到达了行尾。另一方面，如果你从左上角开始，从 j=0 到 256，j 轴上的大部分值在你循环到将它们与 i=0、1、2 等进行比较。

最后，虽然这不言而喻，但我想值得一提:确保您的编译器设置为优化!