数组的比较(逐个元素)

Question

我正在使用的算法花费了大部分时间将一个数组与一行矩阵进行比较.如果任何第i个元素相同,则算法调用过程A,如果没有元素相等,则调用过程B. 例如:

[1, 4, 10, 3, 5]并且[5, 3, 0, 3, 0]调用A()因为对于第4个位置,两个数组中的值都是3.

[1, 4, 10, 3, 5]并且[5, 3, 0, 1, 0]调用B()因为对于相同的位置,值永远不会相同.

注意(1)数组和矩阵行总是具有相同的大小N,以及(2)算法A() 在至少一个值匹配时调用.

在C中执行此操作的最简单但非常天真的方法是:

for(int i=0; i<N; i++)
   if( A[i] == B[i] ){
      flag = 1;
      break;
   }

这仍然非常低效.在最坏的情况下,我将进行N次比较.这里真正的问题是该算法可以进行数万亿次这些比较.

N(矩阵中数组/行的大小)从100到1000不等.我想加快这个程序.我看了矢量化,发现我可以使用cmpeq_pd.但是,矢量化仍然有限,因为我的所有条目都是 longs.有没有人有想法？我可以申请面具吗？

更多信息/背景:

• 这是一种迭代算法.在每次迭代中,我将矩阵增加到一行并多次检查整个矩阵.我也可以更新几行.
• 匹配的可能性不取决于位置.
• 我愿意有误报和否定,以便大大加快这个程序.
• 如果有匹配,在匹配验证的位置是不相关的(我只需要知道,如果有一个匹配的位置).
• 最大数量(约70%)的比较不会导致匹配.
• 并行化在不同的级别完成,即该内核不能并行化.

Answer 1

如果您使用的是 gcc 并且使用的是 x86 平台，那么您的代码可能会受益于使用memcmp()而不是“自行开发的”for循环。memcmp()（分别是它的内置对应部分）做了一些非常聪明的优化。