改进字符串内存分配的方法

Question

这个问题理论性大于实际性，但仍然如此。

我一直在寻找机会从字符串内存分配的角度改进以下代码：

/* Output for n = 3:
*
*  '  #'
*  ' ##'
*  '###'
*
*/
public static string[] staircase(int n) {
    string[] result = new string[n];

    for(var i = 0; i < result.Length; i++) {
        var spaces = string.Empty.PadLeft(n - i - 1, ' ');
        var sharpes = string.Empty.PadRight(i + 1, '#');

        result[i] = spaces + sharpes;
    }

    return result;
}

PadHelper 是方法，最终每次迭代都会在后台调用两次。

所以，如果我错了，请纠正我，但似乎每次迭代至少分配了 3 次内存。

任何代码改进将不胜感激。

Answer 1

怎么样：

result[i] = new string('#',i).PadLeft(n)

?

请注意，仍然在内部分配了两个字符串，但老实说，我不认为这是一个问题。垃圾收集器会为您处理。

Answer 2

您可以使用 Linq Select 方法投影您想要的结果。例如，像这样：

public static string[] staircase(int n) {
    return Enumerable.Range(1, n).Select(i => new string('#', i).PadLeft(n)).ToArray();
}

使用 int 数组的替代方法：

public static string[] staircase(int n) {
    return (new int[n]).Select((x,i) => new string('#', i+1).PadLeft(n)).ToArray();
}

HTH

Answer 3

StringBuilder 始终是字符串分配的答案；我相信你知道，所以显然你想要别的东西。嗯，因为你的字符串都是相同的长度，你可以声明一个 char[] 数组，每次填充它（只需要在每次迭代中更改一个数组元素）然后使用 string(char[]) constructor:

public static string[] staircase(int n)
{
    char[] buf = new char[n];
    string[] result = new string[n];

    for (var i = 0; i < n - 1; i++)
    {
        buf[i] = ' ';
    }

    for (var i = 0; i < n; i++)
    {
        buf[n - i - 1] = '#';
        result[i] = new string(buf);
    }

    return result;
}

Answer 4

您可以通过从包含您将需要的所有空格和所有锐号的字符串开始，然后从中获取子字符串来节省分配和速度，如下所示：

public string[] Staircase2()
{
    string allChars = new string(' ', n - 1) + new string('#', n); // n-1 spaces + n sharpes

    string[] result = new string[n];
    for (var i = 0; i < result.Length; i++)
        result[i] = allChars.Substring(i, n);

    return result;
}

我使用 BenchmarkDotNet 将 Staircase1（您的原始方法）与 Staircase2（我上面的方法）从 n=2 到 n=8 进行比较，请参阅结果如下。

它表明 Staircase2 总是更快（参见 Mean 列），并且它从 n=3.

开始分配更少的字节

|     Method | n |        Mean |      Error |     StdDev | Allocated |
|----------- |-- |------------:|-----------:|-----------:|----------:|

| Staircase1 | 2 |   229.36 ns |  4.3320 ns |  4.0522 ns |      92 B |
| Staircase2 | 2 |    92.00 ns |  0.7200 ns |  0.6735 ns |     116 B |

| Staircase1 | 3 |   375.06 ns |  3.3043 ns |  3.0908 ns |     156 B |
| Staircase2 | 3 |   114.12 ns |  2.8933 ns |  3.2159 ns |     148 B |

| Staircase1 | 4 |   507.32 ns |  3.8995 ns |  3.2562 ns |     236 B |
| Staircase2 | 4 |   142.78 ns |  1.4575 ns |  1.3634 ns |     196 B |

| Staircase1 | 5 |   650.03 ns | 15.1515 ns | 25.7284 ns |     312 B |
| Staircase2 | 5 |   169.25 ns |  1.9076 ns |  1.6911 ns |     232 B |

| Staircase1 | 6 |   785.75 ns | 16.9353 ns | 15.8413 ns |     412 B |
| Staircase2 | 6 |   195.91 ns |  2.9852 ns |  2.4928 ns |     292 B |

| Staircase1 | 7 |   919.15 ns | 11.4145 ns | 10.6771 ns |     500 B |
| Staircase2 | 7 |   237.55 ns |  4.6380 ns |  4.9627 ns |     332 B |

| Staircase1 | 8 | 1,075.66 ns | 26.7013 ns | 40.7756 ns |     620 B |
| Staircase2 | 8 |   255.50 ns |  2.6894 ns |  2.3841 ns |     404 B |

这并不意味着 Staircase2 绝对是最好的，但肯定有一种方法比原来的更好。

改进字符串内存分配的方法

Ways to improve string memory allocation

.net

c#

string

optimization

stringbuilder