计算两个2D数组中相等元素的最快方法(c#)

Question

我有两个只包含0和1的2D数组。这两个数组具有相同大小的并且相对较小(最大20x20)。我需要计算有多少相等的元素有，考虑到职位。由于我必须在代码中多次调用此函数，我想知道是否有更快的方法要做到这一点(包括不安全的组装)。我有一个把每一行的和并行化的坏主意，但结果更糟。

public int Compare(byte[,] a, byte[,] b)
{
int score = 0;
if (a.Length != b.Length)
return -1;
for (int y = 0; y < a.GetLength(1); y++)
{
for (int x = 0; x < a.GetLength(0); x++)
{
if (a[x, y] == b[x, y])
score++;
}
}
return score;
}
public int CompareParallel(byte[,] a, byte[,] b)
{
int[] yScore = new int[a.GetLength(1)];
if (a.Length != b.Length)
return -1;
ParallelLoopResult result = Parallel.For(0, a.GetLength(1), y => {
for (int x = 0; x < a.GetLength(0); x++)
{
if (a[x, y] == b[x, y])
yScore[y]++;
}
});
return yScore.Sum();
}

主:

int score;
int iterations = 100000000;
Stopwatch s = new Stopwatch();
byte[,] a = new byte[4, 2] { { 1, 0 }, { 1, 1 }, { 0, 0 }, { 1, 1 } };
byte[,] b = new byte[4, 2] { { 1, 0 }, { 0, 1 }, { 0, 0 }, { 1, 1 } };
s.Start();

for(int i = 0; i < iterations; i++)
score = Compare(a, b);
Console.WriteLine($"TEST1 - Elapsed: {s.Elapsed.Seconds} seconds");
s.Restart();
for (int i = 0; i < iterations; i++)
score = CompareParallel(a, b);
Console.WriteLine($"TEST2 - Elapsed: {s.Elapsed.Seconds} seconds");

打印:

TEST1 - Elapsed: 3 seconds
TEST2 - Elapsed: <TOO MUCH>

Answer 1

最简单，但可能不是最快的版本，只是有一些比较:

a.Zip(b, (l, r) => l == r).Count(b => b);

但是，有一个非常重要的优化你错过了:

for (int y = 0;y & lt;a.GetLength (1);y + +)

.GetLength()是慢的，所以应该在循环之外调用一次，而不是每次迭代。这将使您的代码快几倍。您可能还想测试颠倒循环顺序是否有帮助，您希望依次访问值，但我不记得这是否意味着将y或x放在外部循环中。

如果这还不够，我建议你自己制作一个2D数组来包装一个常规的1D数组。首先，这让你摆脱了一个循环，并消除了一些索引计算。这也应该允许您使用SIMD内部函数。

你也可以测试一些循环展开是否有帮助，一个可能的瓶颈可能是指令之间的依赖，所以如果你能减少这一点，它可能会有所帮助。

如果你只有400个字节来比较，我不希望并行循环有什么帮助，这应该是很少的工作，值得在多个线程上运行。我也不确定本地代码是否会比优化好的c#代码有更大的帮助，如果你让抖动变得容易，它应该会产生相当好的代码。但我不是c++开发人员，所以在本地代码中可能会有一些c#无法实现的功能。