String.Substring ()이 코드에 병목 현상이있는 것 같습니다.

String.Substring ()이 코드에 병목 현상이있는 것 같습니다.

---

소개

나는 꽤 오래 전에 만든이 좋아하는 알고리즘을 가지고 있는데, 어떤 종류의 벤치 마크로 항상 새로운 프로그래밍 언어, 플랫폼 등으로 작성하고 다시 작성하고 있습니다. 내 주요 프로그래밍 언어는 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이지만 Parallel.For () 및 다중 스레딩 기술을 사용하더라도 내 C # 코드가 35-를 활용하는 동안 모든 8 코어 (100 % CPU 사용률)를 사용하여 실행한다는 것입니다. 최대 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로 테스트되었습니다. 어떤 이유로 100 만개의 문자가 C #에서는 끝나지 않는 반면 Java에서는 0.75 초 밖에 걸리지 않습니다. 소비 된 메모리와 가비지 수집 횟수는 메모리 문제를 나타내는 것 같지 않습니다. 피크는 약 400MB 였지만 거대한 접미사 트리를 고려할 때 이것은 정상적인 것으로 보입니다. 이상한 가비지 수집 패턴도 발견되지 않았습니다.

---

발행 출처

이틀과 3 일 밤 동안 계속되는 영광스러운 전투 (그리고 댓글의 놀라운 아이디어와 생각)를 마친 후 마침내이 문제를 고칠 수있었습니다!

I'd like to post an answer for anybody running into similar issues where the string.Substring(i, j) function is not an acceptable solution to get the substring of a string because the string is either too large and you can't afford the copying done by string.Substring(i, j) (it has to make a copy because C# strings are immutable, no way around it) or the string.Substring(i, j) is being called a huge number of times over the same string (like in my nested for loops) giving the garbage collector a hard time, or as in my case both!

Attempts

I've tried many suggested things such as the StringBuilder, Streams, unmanaged memory allocation using Intptr and Marshal within the unsafe{} block and even creating an IEnumerable and yield return the characters by reference within the given positions. All of these attempts failed ultimatively because some form of joining of the data had to be done as there was no easy way for me to traverse my tree character by character without jeopardizing performance. If only there was a way to span over multiple memory addresses within an array at once like you would be able to in C++ with some pointer arithmetic.. except there is.. (credits to @Ivan Stoev's comment)

The Solution

The solution was using System.ReadOnlySpan<T> (couldn't be System.Span<T> due to strings being immutable) which, among other things, allows us to read sub arrays of memory addresses within an existing array without creating copies.

This piece of the code posted:

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

Was changed to the following:

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

Where stree.has() now takes two integers (position and length of substring) and does:

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

Notice that the substr variable is literally a reference to a subset of characters of the initial s1 array and not a copy! (The s1 variable had been made accessible from this function)

이 문서를 작성하는 현재 C # 7.2 및 .NET Framework 4.6.1을 사용하고 있습니다. 즉, Span 기능을 얻으려면 Project> Manage NuGet Packages로 이동하여 "Include prerelease"확인란을 선택하고 System을 찾아야했습니다. . 메모리 및 설치.

초기 테스트를 다시 실행하면 (1MB 길이의 문자열에서) 속도가 2 분 이상 (2 분 후 기다림을 포기 함)에서 ~ 86 밀리 초로 증가했습니다 !!

참고 URL : https://stackoverflow.com/questions/51673659/string-substring-seems-to-bottleneck-this-code