为什么这个LINQ查询非常慢？

Question

为什么这个LINQ查询非常慢？

4

我写了以下代码将字节数组data转换为字符串数组hex，每个条目包含32个字节的十六进制字符串，以便将它们写入文件。

byte[] data = new byte[4*1024*1024];
string[] hex = data.Select((b) => b.ToString("X2")).ToArray();
hex = Enumerable.Range(0, data.Length / 32).Select((r) => String.Join(" ", hex.Skip(r * 32).Take(32))).ToArray();  // <= This line takes forever

问题是，尽管生成的文件不到20MB，但需要数分钟才能完成。因此我试图进行优化，并想出了以下方法：

byte[] data = new byte[4*1024*1024];
string[] hex = new string[4*1024*1024/32];
for (var i = 0; i <= hex.Length - 1; i++)
{
    var sb = new System.Text.StringBuilder();
    sb.Append(data[i * 32].ToString("X2"));
    for (var k = 1; k <= 32 - 1; k++)
    {
        sb.Append(' ');
        sb.Append(data[i * 32 + k].ToString("X2"));
    }
    hex[i] = sb.ToString();
}

这个版本做同样的事情，但速度快了几个数量级（133毫秒对比8分钟）。

我的问题是我真的不明白为什么原始版本这么慢。我查看了 String.Join() 的源代码，它看起来与我的改进版非常相似。

我喜欢为这些类型的事情使用LINQ，因为你可以轻松地解决各种问题，并且我认为由于其延迟评估，大多数情况下它是有效的。因此，我想知道我在这里缺少了什么，以改进我的LINQ的未来使用。

顺便说一句，我知道它可能还可以更快地编写，但这确实不是重点，因为第二个版本已经足够快，而且只用于调试目的。

- Karsten

你能否运行性能查看器以查看时间被占用的地方？从一次快速浏览中，可能是字符串和字符串构建器之间的差异。我认为在第一个示例中，您有更多的循环，但是如果不进行深入分析，就很难说清楚。 - Mark Davies

2

那个 Linq 查询由于嵌入的 Skip().Take() 将会一遍又一遍地迭代 data。另外，我想你可能是想使用 hex。一个替代方法是使用包含索引的 Select 并根据索引除以 32 进行分组，然后迭代这些结果并使用字符串生成器。 - juharr

@MarkDavies 目前我对 LINQ 的理解有些怀疑，正在寻找一些通用的答案来解决这个问题。除此之外，我进行了一些测试。我相当确定大部分时间都花在了 String.Join() 上，但我不知道为什么在这种情况下它如此缓慢。这对我很重要，因为我经常使用 String.Join()，想知道何时避免使用它。 - Karsten

1

我的猜测是字符串是不可变的，string.join()会创建新的字符串实例。在创建新对象和清理时可能会浪费时间。有趣的是看看在两种情况下创建了多少个对象。 - AlwaysAProgrammer

1

啊，对了；你在第二个示例中使用了一个 StringBuilder。 - Robert Harvey

2个回答

2

.NET Framework的Take实现不包括对类型IList的任何优化，因此在针对大型列表或数组重复调用时变得非常缓慢。相应的.NET Core实现包括这些优化，因此其性能表现相当不错（与手动编码的循环相当）。

- Theodor Zoulias

在我的情况下，Skip() 是问题所在。在 .NET Core 中，Skip() 也有这个优化。但在 .NET Framework 中则没有。 - Karsten

@Karsten，你是对的。我经常混淆Skip和Take。 :-) - Theodor Zoulias

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joel Coehoorn · Accepted Answer

我遇到的问题是，我不太明白为什么原始版本运行如此缓慢。这是其中的一部分：

hex.Skip(r * 32)

.Skip() 必须遍历序列。它不能直接跳转到正确的索引。换句话说，对于数组中的每32个字节，您需要重新从开头遍历整个数组，直到达到当前块的开始位置。这是一种Shlemiel the Painter情况。

您还可以通过使用 ArraySegment 类型、Array.Copy() 或 Span<string> 来使原始代码更快。您还可以编写自己类似于 LINQ 的 "Chunk()" 运算符，以从原始的 IEnumerable 返回32字节的序列，或使用这个非常简单的 Segment() 方法：

public static IEnumerable<T> Segment<T>(this T[] original, int start, int length)
{
    length = start + length;
    while (start < length) 
        yield return original[start++];
}

这将会改变原始代码的样子，变成这样：

byte[] data = new byte[4*1024*1024];
string[] hex = data.Select((b) => b.ToString("X2")).ToArray();
hex = Enumerable.Range(0, data.Length / 32).Select((r) => String.Join(" ", hex.Segment(r * 32,32))).ToArray();

而且，为了好玩，使用我之前链接的Chunk()实现：

byte[] data = new byte[4*1024*1024];
var hex = data.Select(b => b.ToString("X2"))
              .Chunk(32)
              .Select(c => string.Join(" ", c))
              .ToArray(); //only call ToArray() if you *really* need the array. Often the enumerable is enough.

另一个有趣的选项是使用 String.Create()。

byte[] data = new byte[4*1024*1024];
char[] hexChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                    'A', 'B', 'C', 'D', 'E', 'F' };
var hex = data.Chunk(32)
      .Select(c => string.Create(95, c, (r, d) => {
          int i = 0;
          foreach(byte b in d)
          {
             r[i*3] = hexChars[((b & 0xf0) >> 4)];
             r[(i*3) + 1] = hexChars[(b & 0x0f)];
             if (i*3 < 92) r[(i*3) + 2] = ' ';
             i++;
         }
      }))
      .ToArray();

你还应该看一下这个BitConverter.ToString()重载。

我很想看看每一个基准测试的结果。