13

我一直在研究向我提出的一个问题：如何编写一个将字符串作为输入并返回字符之间有空格的字符串的函数。编写该函数以在每秒调用数千次时优化性能。

  1. 我知道 .net 有一个名为 的函数String.Join，我可以将空格字符作为分隔符与原始字符串一起传递给该函数。

  2. 除非使用 ，否则String.Join我可以使用StringBuilder该类在每个字符后附加空格。

  3. 完成此任务的另一种方法是声明一个包含 2*n-1 个字符的字符数组（您必须为空格添加 n-1 个字符）。字符数组可以在循环中填充，然后传递给 String constructor。

我已经编写了一些 .net 代码，它们使用参数运行这些算法中的每一个一百万次，"Hello, World"并测量执行所需的时间。方法 (3) 比 (1) 或 (2) 快得多。

我知道（3）应该非常快，因为它避免了创建任何额外的字符串引用来进行垃圾收集，但在我看来，内置的 .net 函数（例如）String.Join应该会产生良好的性能。为什么使用String.Join比手工工作慢得多？

public static class TestClass
{
    // 491 milliseconds for 1 million iterations
    public static string Space1(string s) 
    {            
        return string.Join(" ", s.AsEnumerable());
    }

    //190 milliseconds for 1 million iterations
    public static string Space2(string s) 
    {
        if (s.Length < 2)
            return s;
        StringBuilder sb = new StringBuilder();
        sb.Append(s[0]);
        for (int i = 1; i < s.Length; i++)
        {
            sb.Append(' ');
            sb.Append(s[i]);
        }            
        return sb.ToString();
    }

    // 50 milliseconds for 1 million iterations
    public static string Space3(string s) 
    {
        if (s.Length < 2)
            return s;
        char[] array = new char[s.Length * 2 - 1];
        array[0] = s[0];
        for (int i = 1; i < s.Length; i++)
        {
            array[2*i-1] = ' ';
            array[2*i] = s[i];
        }
        return new string(array);
    }

更新：我已将我的项目更改为“发布”模式，并相应地更新了我在问题中的经过时间。

4

6 回答 6

7

为什么使用 String.Join 比手动工作慢得多？

在这种情况下String.Join速度较慢的原因是您可以编写一个算法，该算法具有先验知识的确切性质。IEnumerable<T>

String.Join<T>(string, IEnumerable<T>)另一方面，（您正在使用的重载）旨在与任意可枚举类型一起使用，这意味着它无法预先分配到适当的大小。在这种情况下，它是用灵活性换取纯粹的性能和速度。

许多框架方法确实处理了某些可以通过检查条件来加快速度的情况，但这通常只在“特殊情况”很常见时才会这样做。

在这种情况下，您实际上是在创建一个手写例程会更快的边缘案例，但这不是String.Join. 在这种情况下，由于您事先确切地知道需要什么，因此您可以通过预先分配一个大小正好合适的数组并手动构建结果来避免进行灵活设计所需的所有开销。

您会发现，一般来说，通常可以编写一个方法来执行特定输入数据的某些框架例程。这很常见，因为框架例程必须与任何数据集一起使用，这意味着您无法针对特定的输入场景进行优化。

于 2012-06-14T17:30:25.237 回答
4

您的String.Join示例适用于IEnumerable<char>. 枚举IEnumerable<T>withforeach通常比执行for循环慢（这取决于集合类型和其他情况，正如 Dave Black 在评论中指出的那样）。即使Join使用 a StringBuilder， 的内部缓冲区StringBuilder也必须增加数倍，因为要附加的项目数是事先不知道的。

于 2012-04-05T17:08:44.577 回答
3

由于您没有使用 Release 构建（默认情况下应该检查优化）和/或您正在通过 Visual Studio 进行调试，因此将阻止 JITer 进行大量优化。因此，您只是无法很好地了解每个操作真正需要多长时间。添加优化后，您可以了解正在发生的事情的真实情况。

不要在 Visual Studio 中进行调试也很重要。转到 bin/release 文件夹并完全在 Visual Studio 之外双击可执行文件。

于 2012-04-05T17:07:35.743 回答
2

在您的第一个方法中，您使用的String.Join是对 Enumerable 进行操作的重载，这要求该方法使用枚举器遍历字符串的字符。在内部，这使用 a StringBuilder，因为确切的字符数是未知的。

您是否考虑过使用String.Join带字符串（或字符串数​​组）的重载？该实现允许使用固定长度的缓冲区（类似于您的第三种方法）以及一些内部不安全的字符串操作以提高速度。电话将更改为 - String.Join(" ", s); 在没有实际进行测量的情况下，我希望这与您的第三种方法相当或更快。

于 2012-04-05T17:28:16.093 回答
1

糟糕的表现不是来自String.Join，而是来自你处理每个角色的方式。在这种情况下，由于必须单独处理字符，因此您的第一种方法将创建更多的中间字符串，而第二种方法会.Append为每个字符调用两次方法。您的第三种方法不涉及大量中间字符串或方法调用，这就是您的第三种方法最快的原因。

于 2012-04-05T17:12:34.283 回答
0

当您传递一个IEnumerableto 时String.Join，它不知道需要分配多少内存。我分配了一块内存，如果它不够，则调整它的大小并重复该过程，直到它获得足够的内存来容纳所有字符串。

数组版本更快，因为我们提前知道分配的内存量。

另外请注意，当您运行第一个版本时，可能会发生 GC。

于 2012-04-05T17:14:24.257 回答