나는 Brodal 외의 Purely Functional Worst Case Constant Time Catenable Sorted Lists을 읽고있다. 및 데이터 구조의 맥락에서 지속성의 종류에 자신의 도입은 명백한 질문을 나에게 잎 :합류 지속성의 실제 적용
플루 지속성 : 모든 버전이 업데이트 쿼리와 추가로 두 가지 버전으로 결합 될 수있다 할 수있다 새 버전을 만드십시오. 이 경우 자체와 반복적으로 결합하여 다항식 에 기하 급수적으로 크기가 지정된 구조를 생성 할 수 있습니다.
반복적으로 자체와 결합하여 다항식 시간에 "기하 급수적으로 크기가 큰"구조를 만들 수 있다는 실제 적용은 무엇입니까?
필자는 Confluent Persistence의 정의를 보았을 때,이를 병합 작업이 로그 실행 시간 인 Binomial Heap과 같은 데이터 구조와 상관시킬 수 있으며, 유니온 종류를 설정하는 데 매우 적합합니다. 알고리즘의. 트리가 기하 급수적으로 커지면서 이항 힙을 고려할 때 우리는 그 중 몇 개를 가질 수 있으며, 각각은 다항식 시간에 병합 될 수 있습니다. 유니온 연산을 수행하는 것은 이런 종류의 데이터 구조와 다항식 시간에서 느낄 수있는 최상의 애플리케이션이 될 것입니다.
이 속성은이 속성이 해당 유형의 지속성을 나타내는 데이터 구조의 장점이라고이 신문을 읽는 것이 좋습니다. 이 논문을 보면서 필자는 저자가 의도 한 바가 아닐 것이라고 생각한다. 이것은 독자가 즐거움과 즐거움을 누리기 위해 지적하고자하는 데이터 구조의 다소 직관적이지 않은 속성 일 뿐이다.
저자가 말한 지수 크기는 메모리 크기가 아니라 "수학적"크기 (추상적 인 의미에서의 노드 수)라고 생각됩니다. 다항식 시간에 메모리 위치의 기하 급수를 액세스하거나 쓰십시오!
다음은 사용 예입니다. 배열이 희박해질 것으로 예상되는 상황에서 배열로 사용되는 범용 "시퀀스"데이터 유형을 상상해보십시오 (즉, 대부분의 요소에는 동일한 값이 포함되며 상대적으로 소수의 점은 다른 값으로 설정됩니다). 시퀀스 데이터 유형에이 속성이 있으면 언급 한 기법을 사용하여 (아마도 매우 큰) 배열을 작성할 수 있으며이 사용법에서는 여전히 공간과 시간면에서 효율적입니다.
확실히, 희소 배열을위한 특수 목적의 데이터 유형을 만들 수 있으며, 아마도 범용 데이터 유형보다 공간과 시간면에서 약간 더 효율적이지만, 요점은 범용 데이터 유형이 정상적으로 적응한다는 것입니다 이 용도 패턴으로는 특수 용도의 데이터 유형을 만들지 않아도됩니다.
(일반적으로이 예제는 종이의 "정렬 된 목록"이 아니라 일반적으로 합류하는 지속성에 대한 것입니다. 그리고 다시이 백서에서는 합리적인 지속성에 대해 언급하고 있습니다. 자신의 데이터 구조.)
처음에는 비슷한 생각이 들었지만 중복을 제거했기 때문에 세트 조합이 공유를 도입 할 수 없다고 생각합니다. 즉, 세트 A의 결합 자체가 A보다 크지 않습니다. –