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{}，甚至创建一个 IEnumerable 并通过引用返回给定位置内的字符。所有这些尝试最终都失败了，因为必须完成某种形式的数据连接，因为我没有简单的方法可以在不影响性能的情况下逐个字符地遍历我的树。如果只有一种方法可以一次跨越数组中的多个内存地址，就像您可以在 C++ 中使用一些指针算法一样......除了有......（归功于@Ivan Stoev 的评论）解决方案解决方案是使用System.ReadOnlySpan<T>（不可能是System.Span<T>因为字符串是不可变的），除其他外，它允许我们在不创建副本的情况下读取现有数组中内存地址的子数组。这段代码发布：string _s1 = s1.Substring(i, j);if (stree.has(_s1)){&nbsp; &nbsp; score += j - i;&nbsp; &nbsp; longest = j - i;}更改为以下内容：if (stree.has(i, j)){&nbsp; &nbsp; score += j - i;&nbsp; &nbsp; longest = j - i;}哪里stree.has()现在需要两个整数（子字符串的位置和长度）并执行：ReadOnlySpan<char> substr = s1.AsSpan(i, j);请注意，substr变量实际上是对初始s1数组字符子集的引用，而不是副本！（该s1变量已可从此函数访问）请注意，在撰写本文时，我使用的是 C#7.2 和 .NET Framework 4.6.1，这意味着要获得 Span 功能，我必须转到 Project > Manage NuGet Packages，勾选“Include prerelease”复选框并浏览 System .内存并安装它。重新运行初始测试（在长度为 100 万个字符的字符串上，即 1MB）速度从 2+ 分钟（我在 2 分钟后放弃等待）增加到 ~86 毫秒！！