O (1) 제거 및 교체를 위해 어떤 데이터 구조를 사용할 수 있습니까? 또는 당신이 어떻게 말한 구조가 필요할 때 상황을 피할 수 있습니까?
답변
게으름 및 기타 트릭을 활용하여 다양한 종류의 문제에 대해 상각 된 일정한 시간 또는 심지어 ( 대기열 과 같은 제한된 경우 ) 일정한 시간 업데이트 를 달성하는 방대한 데이터 구조 가 있습니다. 크리스 오카 사키의 박사 학위 논문 에 같은 이름의 “순수 기능 데이터 구조”와 책은 좋은 예 (아마도 최초의 주요 일)이지만, 현장 이후 고급 . 이러한 데이터 구조는 일반적으로 인터페이스에서 순수하게 기능 할뿐만 아니라 순수한 Haskell 및 유사한 언어로 구현 될 수 있으며 완전히 영구적입니다.
이러한 고급 도구가 없어도 단순 균형 이진 검색 트리는 로그 시간 업데이트를 제공하므로 최악의 로그 속도 저하로 가변 메모리를 시뮬레이션 할 수 있습니다.
부정 행위로 간주 될 수있는 다른 옵션이 있지만 구현 노력 및 실제 성능과 관련하여 매우 효과적입니다. 예를 들어, 선형 유형 또는 고유 유형은 프로그램이 이전 값 (돌연변이되는 메모리)을 유지하지 못하도록하여 개념적으로 순수한 언어에 대한 구현 전략으로 전체 업데이트를 허용합니다. 이것은 영구적 인 데이터 구조보다 덜 일반적입니다. 예를 들어, 모든 이전 버전의 상태를 저장하여 실행 취소 로그를 쉽게 작성할 수 없습니다. AFAIK는 아직 주요 기능 언어로 제공되지 않지만 여전히 강력한 도구입니다.
변경 가능한 상태를 기능 설정에 안전하게 도입하는 또 다른 옵션 ST은 Haskell 의 모나드입니다. 그것은 돌연변이없이 구현 될 수 있으며, unsafe*기능을 방해 하는 것은 마치 영구적 인 데이터 구조를 암시 적으로 전달하는 것 같은 멋진 래퍼 처럼 작동합니다 ( State). 그러나 평가 순서를 강제하고 이스케이프를 방지하는 일부 유형의 시스템 트릭으로 인해 모든 성능상의 이점과 함께 내부 돌연변이로 안전하게 구현할 수 있습니다.
답변
저렴한 가변 구조 중 하나는 인수 스택입니다.
일반적인 SICP 스타일 계승 계산을 살펴보십시오.
(defn fac (n accum)
(if (= n 1)
accum
(fac (- n 1) (* accum n)))
(defn factorial (n) (fac n 1))
보시다시피, 두 번째 인수 fac는 빠르게 변하는 product를 포함하는 가변 어큐뮬레이터로 사용됩니다 n * (n-1) * (n-2) * .... 가변 변수는 보이지 않지만 어큐뮬레이터를 실수로 다른 나사산으로 변경하는 방법은 없습니다.
이것은 물론 제한된 예입니다.
헤드 노드를 저렴하게 교체하고 헤드에서 시작하는 부분으로 불변의 링크 목록을 얻을 수 있습니다. 이전 헤드와 동일한 다음 노드를 가리 키기 만하면됩니다. 이것은 많은 목록 처리 알고리즘 (모든 것을 fold기반으로 함) 과 잘 작동합니다 .
HAMT를 기반으로하는 연관 배열에서 성능이 매우 우수합니다 . 논리적으로 일부 키-값 쌍이 변경된 새로운 연관 배열을 수신합니다. 구현은 기존 오브젝트와 새로 작성된 오브젝트간에 대부분의 공통 데이터를 공유 할 수 있습니다. 그러나 이것은 O (1)이 아닙니다. 일반적으로 적어도 최악의 경우 대수를 얻습니다. 반면에 불변 트리는 일반적으로 불변 트리에 비해 성능 저하가 발생하지 않습니다. 물론 이것은 일반적으로 엄청 나지 않은 메모리 오버 헤드가 필요합니다.
또 다른 접근법은 나무가 숲에 떨어지면 아무도 듣지 않으면 소리를 내지 않아도된다는 생각에 근거합니다. 즉, 약간의 변형 된 상태가 결코 어떤 로컬 범위를 벗어나지 않는다는 것을 증명할 수 있으면 그 안에있는 데이터를 안전하게 변형 할 수 있습니다.
Clojure에는 로컬 범위 외부로 누출되지 않는 불변 데이터 구조의 변경 가능한 ‘그림자’인 과도 현상 이 있습니다. Clean 은 Uniques를 사용하여 비슷한 것을 달성합니다 (정확하게 기억하는 경우). Rust는 정적으로 확인 된 고유 포인터로 유사한 작업을 수행하는 데 도움이됩니다.
답변
당신이 요구하는 것은 너무 광범위합니다. O (1) 어느 위치에서 제거 및 교체합니까? 시퀀스의 머리? 꼬리? 임의의 위치? 사용할 데이터 구조는 세부 사항에 따라 다릅니다. 즉, 말했다 2-3 손가락 나무가 거기 가장 다재 다능 한 영구 데이터 구조 중 하나처럼 보인다 :
우리는 2-3 손가락 나무, 상각 된 일정한 시간의 끝에 접근을 지원하는 지속적인 시퀀스의 기능적 표현, 더 작은 조각의 크기에서 시간 로그로 연결 및 분할을 제시합니다.
(…)
또한 분할 작업을 일반적인 형식으로 정의하여 시퀀스, 우선 순위 대기열, 검색 트리, 우선 순위 검색 대기열 등으로 사용할 수있는 범용 데이터 구조를 얻습니다.
일반적으로 영구 데이터 구조는 임의 위치를 변경할 때 로그 성능을 갖습니다. O (1) 알고리즘의 상수가 높을 수 있고 로그 속도 저하가 더 느린 전체 알고리즘에 “흡수”될 수 있기 때문에 이는 문제가 될 수도 있고 아닐 수도 있습니다.
더 중요한 것은 지속적인 데이터 구조는 프로그램에 대한 추론을 더 쉽게 만들고 항상 기본 작동 모드 여야한다는 것입니다. 가능하면 영구 데이터 구조를 선호해야하며, 영구 데이터 구조가 성능 병목이라고 프로파일 링하고 결정한 후에는 가변 데이터 구조 만 사용해야합니다. 다른 것은 조기 최적화입니다.