로프 데이터 구조가 스트링 빌더보다 효율적인 시나리오가 있습니까?
https://stackoverflow.com/questions/1863440
-
16-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian해결책
에 대한 문서 SGI C ++ 구현 큰 o 행동에 대해 자세히 설명합니다.
그들의 문서는 가정합니다 매우 긴 문자열이 관여합니다, 참조에 대한 예제는에 대해 이야기합니다 10 MB 문자열. 그러한 것들을 다루는 프로그램은 거의없고, 그러한 요구 사항에 대한 많은 클래스의 문제에 대해서 스트림 기반 가능한 경우 전체 문자열을 사용할 수 있도록 요구하지 않고 상당히 우수한 결과를 가져올 것입니다. 이러한 로프는 로프를 일련의 문자가 아닌 섹션 (자체 로프)으로 적절하게 처리 할 수있을 때 멀티 메가 바이트 문자 시퀀스의 비 스트리밍 조작을위한 것입니다.
중요한 장점 :
- 연결/삽입은 거의 일정한 시간 조작이됩니다
- 특정 작업은 이전 로프 섹션을 재사용하여 메모리에서 공유 할 수 있습니다.
- Java 문자열과 달리 .NET 문자열은 하위 문자열에서 문자 버퍼를 공유하지 않습니다. 메모리 풋 프린트 측면에서 장단점을 선택합니다. 로프는 이런 종류의 문제를 피하는 경향이 있습니다.
- 로프는 필요할 때까지 지연된 하위 문자열 로딩을 허용합니다
- 이것은 제대로되기 어렵고, 접근의 과도한 열망으로 인해 무의미하게 렌더링하기가 매우 쉽고, 일련의 문자가 아닌 로프로 취급하려면 코드를 소비해야합니다.
중요한 단점 :
- 무작위 읽기 액세스가 O (log n)가됩니다.
- 순차적 판독 액세스에 대한 지속적인 요인은 5에서 10 사이 인 것 같습니다.
- API의 효율적인 사용 필요합니다 로프에 밧줄을 떨어 뜨리는 것이 '정상'문자열 API의 백업 구현으로 간주하는 것이 아니라 로프로 취급합니다.
이것은 몇 가지 '명백한'용도로 이어집니다 (SGI에 의해 처음 언급).
- 쉽게 실행 취소/재도를 허용하는 큰 파일의 버퍼 편집
- 어느 시점에서 전체 문자열을 통해 스트리밍을 포함하는 디스크 변경 사항을 작성해야 할 수도 있으므로 대부분의 편집이 빈번한 지속성을 요구하지 않고 주로 메모리에 상주하는 경우에만 유용합니다 (예 : 자동 저장 기능).
- 상당한 조작이 발생하지만 실제로는 거의 발생하지 않는 DNA 세그먼트의 조작
- 문자열의 로컬 하위 섹션을 돌연변이하는 멀티 스레드 알고리즘. 이론적으로 이러한 경우에는 하위 섹션의 로컬 카피를 가져간 다음 재조합 할 필요없이 스레드와 코어를 분리하여 구분하여 상당한 메모리를 저장하고 마지막에 비용이 많이 드는 직렬 결합 작업을 피할 수 있습니다.
문자열의 도메인 별 동작이 로프 구현에 대한 비교적 간단한 증강과 결합 될 수있는 경우가 있습니다.
- 상당수의 공통 하위 문자열을 가진 문자열 만 읽을 수 있습니다.
- 드문 구조가있는 문자열 또는 상당한 로컬 반복은 길이를 인코딩하면서도 합리적인 수준의 무작위 액세스를 허용 할 수 있습니다.
- 하위 문자열 경계가 정보가 저장 될 수있는 '노드'인 경우, 그러한 구조는 radix trie 거의 수정되지 않았지만 종종 읽는 경우.
나열된 예제에서 볼 수 있듯이 모두 '틈새'카테고리로 잘 떨어집니다. 또한, 여러분이 알고리즘을 스트림 프로세싱 작업으로 기꺼이/다시 쓸 수 있다면 몇몇은 우수한 대안을 가질 수 있습니다.
다른 팁
이 질문에 대한 짧은 대답은 예이며, 설명은 거의 필요하지 않습니다. 물론 로프 데이터 구조가 스트링 빌더보다 더 효율적인 상황이 있습니다. 그것들은 다르게 작동하므로 다른 목적으로 더 적합합니다.
(C# 관점에서)
이진 트리로서의 로프 데이터 구조는 특정 상황에서 더 좋습니다. 매우 큰 문자열 값 (SQL에서 100mb의 XML이 들어오는 것을 생각할 때 로프 데이터 구조는 전체 프로세스를 큰 객체 힙에서 유지할 수 있습니다.
5-1000 자의 문자열을보고 있다면 가치가있을 정도로 성능을 향상시키지 못할 것입니다. 이것은 극단적 인 상황이있는 사람들의 5%를 위해 설계된 데이터 구조의 또 다른 사례입니다.
그만큼 10 번째 ICFP 프로그래밍 콘테스트 의존, 기본적으로 효율적인 해결을 위해 로프 데이터 구조를 사용하는 사람들에게. 그것은 합리적인 시간에 VM을 얻는 큰 트릭이었습니다.
접두사가 많으면 밧줄이 우수합니다 (분명히 "선불"이라는 단어는 사람들에 의해 구성되고 적절한 단어가 아닙니다!) 삽입에 더 좋습니다. StringBuilders는 연속 메모리를 사용하므로 추가로만 작동합니다.
따라서 StringBuilder는 매우 정상적인 사용 사례 인 조각을 추가하여 줄을 건축하는 데 적합합니다. 개발자 가이 작업을 많이해야하므로 StringBuilders는 매우 주류 기술입니다.
로프는 버퍼를 편집하는 데 적합합니다. 따라서 (로프의 완화, 예를 들어 이진 트리가 아닌 링크 된 선 목록)는 UI 컨트롤 세계에서 매우 일반적이지만 해당 컨트롤의 개발자와 사용자에게는 종종 노출되지 않습니다.
로프 보유 장치를 만들기 위해서는 실제로 많은 양의 데이터와 이탈이 필요합니다. 프로세서는 스트림 작업에 매우 능숙하며 RAM이 있으면 단순히 접두사를위한 재 할당은 정상적인 사용 사례에 적합하게 작동합니다. 정상에서 언급 된 경쟁은 내가 필요한 유일한 시간이었습니다.
대부분의 고급 텍스트 편집자는 텍스트 본문을 "종류의 로프"로 나타냅니다 (구현시 잎은 일반적으로 개별 문자가 아니라 텍스트 실행). 주로 큰 텍스트에서 자주 삽입 및 삭제를 개선합니다.
일반적으로 StringBuilder는 추가로 최적화되어 있으며 총 재 할당 수 전반적으로 많이. 일반적인 보증은 (Log2 N 할당, 메모리의 2.5 배 미만)입니다. 일반적으로 문자열은 한 번 제작 된 다음 수정되지 않고 꽤 오랫동안 사용될 수 있습니다.
로프는 빈번한 인서트 및 제거에 최적화되어 있으며 최소화하려고합니다. 복사 된 데이터 금액 (더 많은 수의 할당에 의해). 선형 버퍼 구현에서 각각 삽입 및 삭제는 O (N)가되며 일반적으로 단일 문자 인서트를 나타내야합니다.
JavaScript VM은 종종 문자열에 로프를 사용합니다.
Maxime Chevalier-Boisvert, Higgs JavaScript VM의 개발자, 말한다:
JavaScript에서는 문자열 배열을 사용하고 결국 배열을 사용하여 문자열 연결을 합리적으로 빠르게 연결하여 O (n)을 만들 수 있지만 "천연"방법 JS 프로그래머는 문자열을 구축하는 경향이 있습니다. 점진적으로 구축하십시오. JS 문자열은 불변이 아니므로 내부적으로 최적화되지 않으면 증분 추가가 O (N2)입니다. 나는 줄을 첨부하는 Sunspider 벤치 마크로 인해 JS 엔진에서 로프가 구현되었을 가능성이 있다고 생각합니다. JS 엔진 구현자는 로프를 사용하여 이전에 더 빨리 느리게 무언가를 만들어 다른 사람들보다 우위를 점했습니다. 그 벤치 마크가 아니라면, 나는 열악한 성능을 부여하는 현악기에 대한 커뮤니티의 울음 소리가 "array.prototype.join, 더미!"로 충족되었을 수 있다고 생각합니다.
또한.
