c# - String.Substring() 似乎是这段代码的瓶颈

Question

简介

我有一个我最喜欢的算法，它是我很久以前做的，我一直在用新的编程语言、平台等编写和重写它作为某种基准。尽管我的主要编程语言是 C#，但我只是完全复制粘贴了代码并稍微更改了语法，用 Java 构建它并发现它的运行速度提高了 1000 倍。

代码

有相当多的代码，但我只展示这个似乎是主要问题的片段:

for (int i = 0; i <= s1.Length; i++) 
{
    for (int j = i + 1; j <= s1.Length - i; j++)
    {
        string _s1 = s1.Substring(i, j);
        if (tree.hasLeaf(_s1))
         ...

数据

需要指出的是，此特定测试中的字符串 s1 的长度为 100 万个字符 (1MB)。

测量值

我在 Visual Studio 中分析了我的代码执行情况，因为我认为我构建树的方式或遍历树的方式不是最优的。检查结果后，string _s1 = s1.Substring(i, j); 行似乎占了 90% 以上的执行时间!

额外观察

我注意到的另一个区别是，尽管我的代码是单线程的，但 Java 设法使用所有 8 个内核(100% CPU 利用率)来执行它，而即使使用 Parallel.For() 和多线程技术，我的 C# 代码也设法最多使用 35-40%。由于该算法与内核数量(和频率)成线性比例关系，我对此进行了补偿，Java 中的代码片段的执行速度仍快 100-1000 倍。

推理

我认为发生这种情况的原因与以下事实有关:C# 中的字符串是不可变的，因此 String.Substring() 必须创建一个副本，并且由于它在嵌套的 for 循环中有很多迭代，我认为很多复制和垃圾收集正在进行，但是，我不知道 Substring 在 Java 中是如何实现的。

问题

此时我有哪些选择？没有办法解决子字符串的数量和长度(这已经最大限度地优化)。有没有我不知道的方法(或者数据结构)可以为我解决这个问题？

请求的最小实现(来自评论)

我省略了后缀树的实现，构造复杂度为O(n)，遍历复杂度为O(log(n))

public static double compute(string s1, string s2)
{
    double score = 0.00;
    suffixTree stree = new suffixTree(s2);
    for (int i = 0; i <= s1.Length; i++) 
    {
        int longest = 0;
        for (int j = i + 1; j <= s1.Length - i; j++)
        {
            string _s1 = s1.Substring(i, j);
            if (stree.has(_s1))
            {
                score += j - i;
                longest = j - i;
            }
            else break;
         };

        i += longest;
    };
    return score;
}

探查器的屏幕截图片段

请注意，这是使用大小为 300.000 个字符的字符串 s1 进行测试的。出于某种原因，100 万个字符在 C# 中永远不会完成，而在 Java 中它只需要 0.75 秒。消耗的内存和垃圾收集的数量似乎并不表示内存问题。峰值约为 400 MB，但考虑到巨大的后缀树，这似乎是正常的。也没有发现奇怪的垃圾收集模式。

Answer 1

问题来源

经过两天三夜的光荣战斗(以及来自评论的惊人想法和想法)，我终于设法解决了这个问题!

我想为遇到类似问题的任何人发布一个答案，其中 string.Substring(i, j)函数不是获取字符串子字符串的可接受解决方案，因为字符串太大并且您负担不起 string.Substring(i, j) 完成的复制(它必须制作一个副本，因为 C# 字符串是不可变的，没有办法绕过它)或 string.Substring(i, j)在同一个字符串上被多次调用(就像在我的嵌套 for 循环中一样)给垃圾收集器带来了困难，或者就像我的情况一样!

尝试

我已经尝试了很多建议，例如 StringBuilder、Streams、使用 Intptr 和 Marshal 内unsafe{} block 甚至创建一个 IEnumerable 和 yield 通过在给定位置内的引用返回字符。所有这些尝试最终都失败了，因为必须完成某种形式的数据连接，因为我没有简单的方法可以在不影响性能的情况下逐个字符地遍历我的树。如果有一种方法可以一次跨越一个数组中的多个内存地址，就像您可以在 C++ 中使用一些指针算法那样……除了……(归功于@Ivan Stoev 的评论)

解决方案

解决方案是使用 System.ReadOnlySpan<T> (不能是 System.Span<T>，因为字符串是不可变的)除其他外，它允许我们在不创建副本的情况下读取现有数组中内存地址的子数组。

贴出这段代码:

string _s1 = s1.Substring(i, j);
if (stree.has(_s1))
{
    score += j - i;
    longest = j - i;
}

已更改为以下内容:

if (stree.has(i, j))
{
    score += j - i;
    longest = j - i;
}

在哪里stree.has()现在接受两个整数(子字符串的位置和长度)并执行:

ReadOnlySpan<char> substr = s1.AsSpan(i, j);

请注意 substr变量实际上是对初始 s1 字符子集的引用数组而不是副本! (s1 变量可以从这个函数访问)

请注意，在撰写本文时，我正在使用 C#7.2 和 .NET Framework 4.6.1，这意味着要获得 Span 功能，我必须转到“项目”>“管理 NuGet 包”，勾选“包含预发布”复选框，然后浏览并安装 System.Memory。

重新运行初始测试(在长度为 100 万个字符的字符串上，即 1MB)，速度从 2+ 分钟(我在 2 分钟后放弃等待)增加到 ~86 毫秒!!