比较2字节数组

Question

我有2个int数组.

int[] data1 #
int[] data2 #

我想创建第3个int [] data3,这是其他2个数组之间的差异.

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

值为15(例如).

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

值为3(例如).

data3中的第一个值为12.

但是,如果第一个值是相反的,即

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

然后差异将是-12.但我希望它只有12岁.

目前我有一个for循环,我在那里做计算的东西来获得那种类型的结果.

1. 有没有办法在不通过循环枚举的情况下执行data1-data2 = data3？
2. 如果是这样,我可以在不使用减号的情况下获得差异吗？

谢谢

NB回应'关闭者'.我同意你的观点.我需要在这个问题上添加的是:

我正在寻找最有效(最快的方式,但低内存是第二优先)来促进这一点.使用Linq(据我所知)可能是最慢的方法？

Answer 1

你正在寻找Zip方法

var data3 = data1.Zip(data2, (d1,d2) => Math.Abs(d1 - d2)).ToArray();

Enumerable.Zip<TFirst, TSecond, TResult> Method

将指定的函数应用于两个序列的相应元素,生成一系列结果.

因此,它只是需要每个对应的元素,如data1[0]和data2[0],然后data1[1]和data2[1]等..然后应用功能,Math.Abs(d1-d2)它只是substracts两个数字,并得到结果的绝对值.然后返回一个包含每个操作结果的序列.

Answer 2

"有没有办法在不通过循环枚举的情况下执行data1-data2 = data3？" 不,这在技术上是不可能的.

充其量,或者更糟糕的是,你可以调用将为你进行枚举的函数.但它会很慢.在LINQ的情况下,不合适的慢.

对于机器我目前正在处理其他答案的结果如下4KB表(1024整数).

• 23560蜱 - Giannis Paraskevopoulos.Array-Enumerable-Array转换速度不太快,通过ToList()复制数组.ToArray()链比Array.Copy()慢大约25倍.
• 10198个蜱虫 - 塞尔曼22.快2倍,但仍然很慢.Lambdas是令人眼花缭乱的东西,可以让创造活动变得更漂亮,而不是更快.你最终会得到一些匿名的方法,这可能会占用更多的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上,你可以获得8个免费使用的奖励寄存器.无需访问内存就能做得越多,代码就越快.在这种情况下,速度增益约为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之后,主要的蜱虫munchkin是Abs().当它从代码中删除时,我们在IF-ELSE和速记？:运算符之间留下了较量.两者都是分支运算符,过去曾被广泛认为比线性代码慢.目前易于使用/写作易于挑选性能(有时正确,有时不正确).

因此,让我们的分支条件是线性的.有可能通过滥用这个代码中的分支包含仅对单个变量进行操作的事实.所以让我们使代码等同于此.

现在你还记得如何否定二的补数？,否定所有的位并加一个.让我们无条件地在一条线上做到这一点!

这是按位运营商的时间发光.OR和AND很无聊,真正的男人使用异或.XOR真的很酷吗？除了通常的行为,您还可以将其转换为NOT(否定)和NOP(无操作).

1 XOR 1 = 0
0 XOR 1 = 1

所以只用1的XOR'ing值就不会给你带来操作.

1 XOR 0 = 1
0 XOR 0 = 0

所以XOR'ing只用0填充的值什么都不做.

我们可以从我们的号码获得标志.对于32位整数,它就像x>>31.它将位符号移动到最低位.正如wiki会告诉你的那样,从左边插入的位将是零,所以你的结果是x>>31负数(x <0)为1而非负数(x> = 0)为0,对吗？

不.对于有符号值,算术移位用于普通位移.所以我们将得-1或0取决于符号....这意味着'x >> 31'将给出111 ... 111为负,000 ... 000为非负.如果您将根据此类移位的结果对原始x进行异或,则根据值符号执行NOT或NOP.另一个有用的事情是0将导致NOP用于加/否,因此我们可以根据值符号加/减-1.

因此'x ^(x >> 31)'将翻转负数位,而不对非负数进行更改,而'x-(x >> 31)'将加1(否定负值给出正数)到负x并且不对非负值进行更改.

当你得到'(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可以自行"展开"循环.(Haswells在展开时很奇怪)

结果代码:

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会使缓存混乱.因此,由于cache-miss,这段代码实际上比单线程版本慢.

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.ForEach和负载均衡分区.通过使用它们,你可以获得最好的世界:

• 数据集大小独立代码
• 简短,整洁的代码
• 多线程
• 良好的缓存使用率

所以最终的代码是:

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所以我们在这里很安全).

在这里,我认为我们将停止优化.它作为一篇文章出现而不是回答,我希望没有人会为此而清除我.