我有一个长度为 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++;
}
最佳答案
有了更多的信息,我们可能会给你更好的建议,但根据我对这个问题的理解,这里有一些想法:
- 由于您使用每个字符来表示 1 或 0,因此您使用的内存比您需要使用的内存多几倍,这在缓存等方面会产生很大的性能影响。相反,使用您可以根据一系列位来考虑的数值来表示您的数据。
- 实现#1 后,您可以一次获取一个完整的整数或长整数,然后执行按位异或运算,最终得到一个数字,该数字在两个数字没有的每个地方都有一个 1相同的值。然后你可以使用一些the tricks mentioned here快速计算这些位。
稍微“展开”您的循环以避免必要的跳跃次数。例如下面的代码:
total = total + array[i]; total = total + array[i + 1]; total = total + array[i + 2];
... 将比仅循环遍历
total = total + array[i]
三次更快。跳转是昂贵的,并且会干扰处理器的流水线。 更新:我应该提一下,您的编译器可能已经为您完成了其中的一些工作——您可以查看编译后的代码。- 将您的整体数据集分成多个 block ,以便您充分利用缓存。将您的问题想象成一个“正方形”,一个轴上有
i
索引,另一个轴上有j
索引。如果您从一个i
开始并遍历所有 175000 个j
值,那么您访问的第一个j
值将在此时从缓存中消失你到达了行尾。另一方面,如果你从左上角开始,从 j=0 到 256,j
轴上的大部分值在你循环到将它们与 i=0、1、2 等进行比较。
最后,虽然这不言而喻,但我想值得一提:确保您的编译器设置为优化!
关于c++ - 长数组性能问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7897802/