比较两个字节数组

10

我有两个整型数组。

int[] data1 #
int[] data2 #

我想创建一个第三个int[]数组data3,用于存储另外两个数组之间的差值。

让我们取data1中的第一个值。

该值为15(例如)。

现在让我们取data2中的第一个值。

该值为3(例如)。

那么data3中的第一个值将是12。

但是,如果第一个值的顺序相反,即data2中的第一个值减去data1中的第一个值,则结果将是负数。

data1[0]  = 3
data2[0]  = 15

那么差异将是-12。但我希望它只是12。

目前,我有一个for循环,我在那里进行计算以获得那种类型的结果。

  1. 是否有一种方法可以做到data1-data2 = data3而不需要枚举循环?
  2. 如果可以,我能否只获取没有使用负数的差异?

谢谢

N.B. 针对“关闭者”的回应。 在某种程度上,我同意你们的看法。 我需要补充的是:

我正在寻找最有效(最快的方式,但内存占用率次之)来实现这一点。 使用Linq(据我所知)可能是最慢的方法?


我稍微升级了我的答案。在你的数据规模下,性能提升可能会很有用。 - PTwr
1
又来一次更新,性能又提升了 ;) - PTwr
@ptwr 你花了点时间 :). 真的非常感谢。我会试一下的。谢谢。 - Andrew Simpson
1
如果你认为我已经完成了,那么你就错了!虽然这次我认为这是最终版本。 - PTwr
@PTwr 嗨,你是一位主要迷!但我没有抱怨。工作完后我会看一下 - 谢谢! - Andrew Simpson
4个回答

8
您正在寻找 Zip 方法。
var data3 = data1.Zip(data2, (d1,d2) => Math.Abs(d1 - d2)).ToArray();

Enumerable.Zip<TFirst, TSecond, TResult> 方法

将指定函数应用于两个序列的对应元素,生成结果序列。

它简单地取每个对应的元素,例如 data1[0]data2[0],然后是 data1[1]data2[1],以此类推... 然后应用函数 Math.Abs(d1-d2),它仅将两个数字相减并得到结果的绝对值。然后返回包含每个操作结果的序列。


嗨,有趣。不过,Zip似乎不是data1的属性。显然,我在这里漏掉了什么? - Andrew Simpson
@AndrewSimpson 你用过 System.LINQ 吗? - flindeberg
啊!使用 LinQ - 抱歉。 - Andrew Simpson
嗨,我目前正在尝试你和@GiannisParaskevopoulos的代码,因为效率是关键。 - Andrew Simpson
1
刚试过了,不错啊。请问在这种情况下Zip实际上是做什么的? - Andrew Simpson

7
"

有没有一种方法可以在不通过枚举循环的情况下执行 data1-data2 = data3?

不,这在技术上是不可能的。

最好(或者说最坏)的情况是,您可以调用一个函数来为您枚举。但这会使速度变慢。在LINQ的情况下,速度非常慢。

对于我目前正在使用的机器,对于4KB表(1024个整数),其他答案的结果如下:

"
  • 23560 滴答声 - Giannis Paraskevopoulos。数组可枚举数组转换不太快,通过ToList() .ToArray()链复制数组大约要慢25倍Array.Copy()。
  • 10198 滴答声 - Selman22。速度提高了2倍,但仍然很慢。Lambda是为了使创建事件更漂亮而不是更快的眼睛糖果。最终你会得到一些匿名方法在那里游荡,它所花费的CPU时间比其操作还要多(记住我们在这里所做的数学CPU可以在几个周期内完成)。
  • 566 滴答声 - Tim Schmelter GetDifference()函数(主要原因是JIT,在本地代码和/或更频繁的使用中差异将是可以忽略的)
  • 27 滴答声 - 只是一个循环。比Zip快400倍,比将数组转换为列表并返回快800倍。

循环代码:

for (int i = 0; i < data3.Length; i++)
{
  data3[i] = Math.Abs(data1[i] - data2[i]);
}

这些基本的内存操作可以直接翻译成机器代码,而不需要使用LINQ带来的性能问题和巨大的内存占用。
故事的寓意是:LINQ适用于可读性(在这种情况下有争议),而不适用于性能(在这种情况下很明显)。

优化时间!让我们稍微滥用一下CPU。

  1. 展开循环。或者不要展开。您的体验可能会有所不同。即使在汇编语言中,循环展开的性能增益或损失也因处理器系列而异。新的CPU和编译器已经了解到旧技巧,并且会自行实现它们。对于i3-3220,我测试了展开4行代码的循环,在32位代码上得到了更快的执行速度,但在64位上稍微慢了一点,而展开8则相反。
  2. 编译为x64。由于我们在这里处理32位数据,因此我们不会使用64位寄存器...或者我们会吗?在x86上,只有不到一半的寄存器真正可用于生成的代码(在手写汇编中,您总是可以挤出更多),但在x64上,您获得了八个额外的寄存器可供使用。越多操作不需要访问内存,您的代码就越快。在这种情况下,速度提高约20%。
  3. 关闭Visual Studio。不要在32位IDE中进行64位代码的速度测试(目前还没有64位版本,而且可能很长时间都不会有)。由于架构不匹配,它将使x64代码大约变慢两倍。(嗯...无论如何,您都不应该在调试器下测试代码的速度...)
  4. 不要过多使用内置函数。在这种情况下,Math.Abs中有隐藏的开销。由于某些原因(需要分析IL才能找出),使用?:检查负值比If-Else更快。这样的检查节省了大量时间。
更新: ?: 比 If-Else 更快,因为它们的机器码有所不同...至少在比较两个值时是如此。 它的机器码比 If-Else 简单得多(看起来不像你手写的代码)。 显然,它不仅是 If-Else 语句的不同形式,而且是针对简单条件赋值进行优化的完全独立的命令。

生成的代码大约比使用 Math.Abs() 的简单循环快8倍;请记住,您只能将循环展开到数据集大小的除数。 您编写的数据集大小为25920,因此8是可以的(最大为64,但我怀疑这样做是否有任何意义)。 我建议将此代码隐藏在某个函数中,因为它非常丑陋。

int[] data3 = new int[data1.Length];
for (int i = 0; i < data1.Length; i += 8)
{
    int b;
    b = (data1[i + 0] - data2[i + 0]);
    data3[i + 0] = b < 0 ? -b : b;
    b = (data1[i + 1] - data2[i + 1]);
    data3[i + 1] = b < 0 ? -b : b;
    b = (data1[i + 2] - data2[i + 2]);
    data3[i + 2] = b < 0 ? -b : b;
    b = (data1[i + 3] - data2[i + 3]);
    data3[i + 3] = b < 0 ? -b : b;
    b = (data1[i + 3] - data2[i + 4]);
    data3[i + 4] = b < 0 ? -b : b;
    b = (data1[i + 5] - data2[i + 5]);
    data3[i + 5] = b < 0 ? -b : b;
    b = (data1[i + 6] - data2[i + 6]);
    data3[i + 6] = b < 0 ? -b : b;
    b = (data1[i + 7] - data2[i + 7]);
    data3[i + 7] = b < 0 ? -b : b;
}

这甚至还不是它的最终形态。我将尝试对其进行更多异端邪术。
BitHack,低级作弊!
正如我所提到的,还有改进的空间。
在剪切LINQ之后,主要ticks munchkin是Abs()。当它从代码中删除时,我们只剩下IF-ELSE和shorthand ?: 运算符之间的竞争。 两者都是分支运算符,在过去曾被广泛认为比线性代码慢。目前,舒适性/编写容易性往往优先于性能(有时正确,有时不正确)。
因此,让我们使我们的分支条件成为线性的。通过滥用这段代码中包含的仅针对单个变量进行数学操作的事实,这是可能的。那么让我们制作与this等效的代码。
现在,你还记得如何否定二进制补码吗?取反所有位并加一。然后让我们在不使用条件的情况下完成它!
现在是位运算符发光的时候了。OR和AND很无聊,真正的男人使用XOR。 XOR有什么很酷的地方?除了它的通常行为外,您还可以将其转换为NOT(否定)和NOP(无操作)。
1 XOR 1 = 0
0 XOR 1 = 1

使用只包含1的值进行XOR操作可以实现NOT运算。
1 XOR 0 = 1
0 XOR 0 = 0

所以,使用只填充0值的值进行异或操作没有任何效果。

我们可以从我们的数字中获取符号。对于32位整数,它非常简单,即x>>31。它将位符移动到最低位。正如维基百科所说,插入的位从左侧插入将为零,因此对于负数(x<0),x>>31的结果将为1,对于非负数(x>=0)则为0,对吗?

不是这样的。对于带符号的值,使用算术移位而不是纯位移。因此,根据符号,我们将获得-1或0....这意味着对于负数和非负数来说,'x>>31'将分别给出111...111和000...000。如果您将原始x与这种移位的结果进行异或运算,则会执行NOT或NOP,具体取决于值的符号。另一个有用的事情是,0将导致加法/否定的NOP,因此我们可以根据值的符号添加/减去-1。

所以'x^(x>>31)'将翻转负数的位,而对非负数不做任何更改,'x-(x>>31)'将给负数x加1(否定的负值给出正值),并对非负值不做任何更改。

当组合在一起时,你会得到'(x ^ (x >> 31)) - (x >> 31)'... 这可以翻译为:

IF X<0
  X=!X+1

而且这只是

IF X<0
  X=-X

如何影响性能? 我们的XorAbs()只需要四个基本整数操作,一个加载和一个存储。分支运算符本身需要大约相同数量的CPU时钟周期。虽然现代CPU在进行分支预测方面表现出色,但当输入连续代码时,它们仍然通过简单地不执行分支来提高速度。
得分情况如何?
1.比内置的Abs()快约四倍; 2.比以前的代码(未展开循环的版本)快约两倍; 3.根据CPU的不同,可以在不展开循环的情况下获得更好的结果。由于消除了代码分支,CPU可以自行“展开”循环。(Haswell处理器在展开循环方面表现奇怪)
生成的代码:
for (int i = 0; i < data1.Length; i++)
{
  int x = data1[i] - data2[i];
  data3[i] = (x ^ (x >> 31)) - (x >> 31);
}

并行性和缓存使用

CPU拥有超快的缓存内存,当按顺序处理数组时,它会将整个块复制到缓存中。 但是,如果你编写糟糕的代码,就会出现缓存未命中。你可以通过 搞乱嵌套循环的顺序 轻易地陷入这个陷阱。

并行性(多线程,同样的数据)必须按顺序分块处理,以充分利用CPU缓存。

手动编写线程将允许你手动选择线程的块,但这是一个麻烦的方法。 自4.0版本起,.NET提供了帮助程序,但默认的 Parallel.For 会搞乱缓存。 因此,由于 缓存未命中,这段代码实际上比单线程版本更慢。

Parallel.For(0, data1.Length,
fn =>
{
  int x = data1[fn] - data2[fn];
  data3[fn] = (x ^ (x >> 31)) - (x >> 31);
}

通过在缓存数据中执行顺序操作,可以手动利用缓存数据。例如,您可以展开循环,但这是一种不良的技巧,并且展开具有自己的性能问题(这取决于CPU型号)。

Parallel.For(0, data1.Length >> 3,
i =>
{
    int b;
    b = (data1[i + 0] - data2[i + 0]);
    data3[i + 0] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 1] - data2[i + 1]);
    data3[i + 1] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 2] - data2[i + 2]);
    data3[i + 2] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 3] - data2[i + 3]);
    data3[i + 3] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 3] - data2[i + 4]);
    data3[i + 4] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 5] - data2[i + 5]);
    data3[i + 5] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 6] - data2[i + 6]);
    data3[i + 6] = b < 0 ? (b ^ -1) + b : b;
    b = (data1[i + 7] - data2[i + 7]);
    data3[i + 7] = b < 0 ? (b ^ -1) + b : b;
}

然而,.NET也有Parrarel.ForEachLoad Balancing Partitioners。使用它们两个可以获得最佳效果:
  • 数据集大小独立的代码
  • 简短、整洁的代码
  • 多线程
  • 良好的缓存使用
所以最终的代码将是:
var rangePartitioner = Partitioner.Create(0, data1.Length);
Parallel.ForEach(rangePartitioner, (range, loopState)
=>
{
    for (int i = range.Item1; i < range.Item2; i++)
    {
        int x = data1[i] - data2[i];
        data3[i] = (x ^ (x >> 31)) - (x >> 31);
    }
});

它远未达到最大CPU使用率(这比仅仅将时钟加速更为复杂,有多个缓存级别、多条流水线等等),但它易读、快速且平台无关(除了整数大小,但C# int是System.Int32的别名,所以我们在这里是安全的)。
在这里,我认为我们应该停止优化。这篇文章不仅仅是一个答案,希望没有人因此清除我。

嗨,感谢您提供的所有信息。是的,我认为使用LINQ比“传统”方法要慢。这段代码与Tim的代码相同吗?不过您给了我更多的信息。 - Andrew Simpson
只是确认我没有漏掉什么。你在速度结果中提供了额外的信息,这给了我上下文。谢谢。 - Andrew Simpson
@PTwr:为什么我的GetDifference比你的循环慢20倍?我也只是使用了一个循环,所以代码完全相同。另外,你是如何测试它的呢?我还会删除那个以“这样基本的内存操作”开头的句子,因为它非常令人困惑,而LINQ通常并不明显地低效。 - Tim Schmelter
@PTwr:如果您使用非常大的数组测试一次方法或使用非常小的数组测试一百万次,那么这是有区别的。但是,您是否也测量了第三个数组的初始化?方法调用本身几乎不会产生任何操作。确保您测量发布模式代码,因为默认情况下在调试构建中关闭优化。在开始测量之前还要调用一个方法。我假设您已经使用了Stopwatch而不是DateTime - Tim Schmelter
1
@PTwr:非方法和方法之间的差别绝对可以忽略不计。编写安全、可读性好且易于维护的代码,而不是在一百万次迭代中节省几毫秒时间的代码。 - Tim Schmelter
显示剩余4条评论

3

这里有另一种方法(可能不太易读,但可能更加高效),它不需要使用LINQ:

public static int[] GetDifference(int[] first, int[] second)
{
    int commonLength = Math.Min(first.Length, second.Length);
    int[] diff = new int[commonLength];
    for (int i = 0; i < commonLength; i++)
        diff[i] = Math.Abs(first[i] - second[i]);
    return diff;
}

为什么要“稍微更高效”?因为ToArray需要调整数组大小,直到知道最终大小为止。(参考链接)


@AndrewSimpson:数组是大还是小,但你需要经常调用它? - Tim Schmelter
1
@AndrewSimpson:除非GetDifference是你代码的瓶颈,否则请优先考虑可读性而不是性能。 - Brian
嗨,数组大小是通过将二维数组展平得出的结果。初始的二维数组为144x180。因此,所得到的展平数组大小为25920。我正在比较尽可能多的这些数组(这是我的FPS速率)。因此,每秒钟会进行多次比较。 - Andrew Simpson
@Brian:我也喜欢LINQ并且已经点赞了Zip方法。但是由于OP已经提到性能很重要,所以我提供了一个非LINQ的方法。此外,这种方法并不是真正复杂的。 - Tim Schmelter
嗨,好的,明白了。我现在正在工作,但回去后就可以进行一些适当的速度测试。然后我会更新我的情况。谢谢 :) - Andrew Simpson
显示剩余2条评论

1
var data3 = data1.Select((x,i)=>new {x,i})
    .Join
    (
        data2.Select((x,i)=>new {x,i}),
        x=>x.i,
        x=>x.i,
        (d1,d2)=>Math.Abs(d1.x-d2.x)
    )
    .ToArray();

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接