[C#] .NET에서 문자열을 변경할 수없는 경우 왜 Substring에 O (n) 시간이 걸리나요?

업데이트 : 나는이 질문을 너무 좋아, 방금 블로그에 올렸습니다. 문자열, 불변성 및 지속성을 참조하십시오

짧은 대답은 다음과 같습니다. n이 커지지 않으면 O (n)은 O (1)입니다. 대부분의 사람들은 작은 문자열에서 작은 하위 문자열을 추출하므로 복잡성이 무증상으로 성장하는 방식은 전혀 관련이 없습니다 .

긴 대답은 다음과 같습니다.

인스턴스에 대한 조작이 적은 양 (일반적으로 O (1) 또는 O (lg n))의 복사 또는 새 할당으로 원본의 메모리를 재사용 할 수 있도록 구축 된 불변 데이터 구조를 “지속적”이라고합니다. 불변 데이터 구조. .NET의 문자열은 변경할 수 없습니다. 귀하의 질문은 본질적으로 “왜 지속되지 않는가?”

일반적으로 .NET 프로그램의 문자열에서 수행 되는 작업을 살펴보면 완전히 새로운 문자열을 만드는 것이 전혀 나쁘지 않습니다 . 복잡한 영구 데이터 구조를 구축하는 데 드는 비용과 어려움은 그 자체로 비용을 지불하지 않습니다.

사람들은 일반적으로 “서브 스트링”을 사용하여 약간 긴 문자열에서 짧은 문자열 (예 : 10 ~ 20 자)을 추출합니다. 쉼표로 구분 된 파일에 텍스트 줄이 있고 성인 세 번째 필드를 추출하려고합니다. 줄은 몇 백 자 정도 될 것이고 이름은 수십 개가 될 것입니다. 현대 하드웨어 에서는 50 바이트의 문자열 할당 및 메모리 복사가 매우 빠릅니다 . 기존 문자열의 가운데에 길이를 더한 포인터로 구성된 새로운 데이터 구조를 만드는 것도 놀랍도록 빠릅니다. “충분히 빠름”은 정의상 충분히 빠릅니다.

추출 된 부분 문자열은 일반적으로 크기가 작고 수명이 짧습니다. 가비지 콜렉터가 곧 회수 할 예정이며, 처음에는 힙에 많은 공간을 차지하지 않았습니다. 따라서 대부분의 메모리 재사용을 장려하는 지속적인 전략을 사용하는 것도 승리가 아닙니다. 내부 포인터 처리에 대해 걱정해야하기 때문에 가비지 수집기가 느려집니다.

사람들이 일반적으로 문자열에서 수행하는 하위 문자열 작업이 완전히 다른 경우 지속적인 접근 방식을 사용하는 것이 좋습니다. 사람들이 일반적으로 백만 자의 문자열을 가지고 있으며 수 천 자 범위의 크기를 가진 수천 개의 겹치는 부분 문자열을 추출하고 그 부분 문자열이 힙에서 오랫동안 살았다면 지속적인 부분 문자열을 사용하는 것이 완벽합니다. 접근하다; 그것은 낭비적이고 어리석은 짓입니다. 그러나 대부분의 업무용 프로그래머는 이런 종류의 것들과 같은 모호한 행동을하지 않습니다.. .NET은 Human Genome Project의 요구에 맞춘 플랫폼이 아닙니다. DNA 분석 프로그래머는 이러한 문자열 사용 특성과 관련된 문제를 매일 해결해야합니다. 당신이하지 않을 확률이 좋습니다. 밀접하게 일치하는 자신의 영구적 인 데이터 구조를 구축 않는 극소수의 사람들 자신의 사용 시나리오를.

예를 들어, 우리 팀은 입력 할 때 C # 및 VB 코드를 즉시 분석하는 프로그램을 작성합니다. 이러한 코드 파일 중 일부는 엄청나 므로 하위 문자열을 추출하거나 문자를 삽입 또는 삭제하기 위해 O (n) 문자열 조작을 수행 할 수 없습니다. 우리는 텍스트 버퍼에 대한 편집 내용을 나타 내기 위해 영구적 인 불변 데이터 구조를 많이 만들었습니다.이를 통해 기존 문자열 데이터의 대량 및 기존 편집시의 어휘 및 구문 분석 을 빠르고 효율적으로 재사용 할 수 있습니다. 이것은 해결하기 어려운 문제였으며 솔루션은 C # 및 VB 코드 편집의 특정 도메인에 맞게 조정되었습니다. 내장 문자열 유형이 우리 에게이 문제를 해결할 것으로 기대하는 것은 비현실적입니다.

답변

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);