빠른 인덱싱, 추가, 프리 펜딩 및 반복 (좋은 지역성) 작업을 허용하는 배열과 유사하지만 불변 의 지속적인 데이터 구조를 찾고 있습니다.
Clojure는 지속적인 Vector를 제공하지만 빠른 추가만을위한 것입니다. 스칼라의 Vector는 효과적으로 상수 시간 추가 및 접두어를 갖지만 Clojure 벡터와 동일한 데이터 구조 (비트 매핑 벡터 트리)를 기반으로하고 비트 매핑 벡터 트리를 이해하기 때문에 구현 방법을 알 수 없습니다 몇 가지 트릭없이 빠른 접두사를 가질 수 없습니다.
구현을 사용할 준비가되어 있지 않지만 그러한 데이터 구조를 직접 구현하는 방법에 대한 설명에 관심이 있습니다.
답변
확실한 후보는 지속적 균형 이진 트리입니다. 나열된 모든 작업은 경로 복사를 사용하여 또는 시간에 수행 할 수 있습니다 . 이 런타임을 달성하는 방법에 대한 자세한 내용은 아래에서 참조 된 Chris Okasaki의 책 또는 여기에 대한 답변을 참조 하십시오 .O ( LG N )
O(1)O(lgn)
물론, 변형으로서, 그러한 트리의 각 잎 자체는 불변 배열 (연속적인 값들의 시퀀스)을 포함 할 수있다. 이렇게하면 값을 효율적으로 업데이트 할 수 없지만 기존 값을 수정하지 않으려는 경우 추가하고 앞에 추가하면 상황에 적합합니다. 이런 식으로, 벡터는 불변 시퀀스의 시퀀스로 표현되며, 잎에 불변 배열이있는 균형 이진 트리로 표현됩니다. 이를 통해 빠른 인덱싱 (잎 수의 로그), 빠른 추가 및 접두사 및 빠른 반복이 가능합니다. 최악의 경우 점근 적 복잡성은 더 나쁘지 않지만 실제로는 성능이 크게 향상 될 수 있습니다.
표준 참조는 Chris Okasaki의 1998 년 책 “순전히 기능적인 데이터 구조”입니다.
또한보십시오
답변
나는 증분 정규 표현식 일치에 대한 내 문서에서 이러한 데이터 구조의 구현을 설명했다 – 볼 http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation 아래 해당 섹션 위의 텍스트 .
그것은 일정한 높이의 다양한 나무입니다 (B- 나무 또는 2-3 나무와 같은). 기본적으로 이것은 요소 당 오버 헤드를 피하기 위해 (2,3) 트리이며 잎은 (N, 2N-1) 배열입니다. (A (N, 2N-1) 배열은 길이가 N..2N-1 범위 인 배열입니다.) N이 클수록 오버 헤드는 줄어들지 만 선형 적으로 분할 및 연결의 복잡성이 증가합니다. 인덱싱, 분할 및 연결과 같은 작업은 2-3 수준의 트리에서 작업하는 방식과 매우 유사하며 리프 수준에서 (N, 2N-1)로 일반화됩니다.