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的长度为1百万字符(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循环中有很多次迭代我假设有很多复制和垃圾收集正在进行,但是,我不知道如何在Java中实现Substring.

题

此时我有什么选择？子串的数量和长度没有办法(这已经最大化了).是否有一种我不知道的方法(或许可能是数据结构)可以为我解决这个问题？

请求最小化实施(来自评论)

我遗漏了后缀树的实现,它在构造中是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进行测试的.出于某种原因,1百万个字符在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))
{
    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功能,我必须转到Project> Manage NuGet Packages,勾选"Include prerelease"复选框并浏览System .Memory并安装它.

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