영구 데이터 구조 : 영구 인덱스?

Question

기능적 프로그래밍은 변경 불가능한 데이터를 사용합니다. 당신이 무언가를 수정할 때 당신은 당신의 증강 된 세계를 위해 가능한 한 많이 이전의 성육신을 재사용하면서 "세계"를 재 탄생시킵니다.

JavaScript에서 FP를 탐색 중입니다. Lisp의 List와 비슷한 List 객체를 만들었습니다. 기존 꼬리에 새로운 머리가 cons 있습니다. 영구 목록에 항목을 추가하는 동안 목록과 일치하는 영구 색인을 만들고 싶습니다. 따라서 연락처 목록에 새 연락처를 넣으면 전체 테이블 검색을 효과적으로 시작하지 않고 항목을 빨리 찾을 수 있도록 성 및 전화 번호를 색인 할 수 있습니다.

Q : JavaScript에서는 빠른 키 액세스를 제공하는 영구적 인 데이터 구조는 어떤 종류입니까?

즉, 증가 된 인덱스를 구성 할 때 이전 인덱스 데이터를 다시 사용하는 것이 좋다고 생각합니다. 증분 색인에 이전 색인에있는 모든 키 복제의 부족 나는이 문제 마비를 찾는 중이 야. 복제하면 프로그래밍 방식으로 데이터를로드하는 동안 엄청난 양의 메모리가 낭비됩니다. 인덱스는 메모리 효율적이어야하며 값으로 빠른 액세스를 제공해야합니다.

Answer 1

다른 언어에서와 마찬가지로 일종의 자체 균형 조정 이진 검색 트리를 사용할 수 있습니다 (많은 언어에서 이미 데이터 구조가 제공되었지만). 각 삽입물은 O(log n) 개의 새로운 검색 노드를 생성하는 재조정을 포함하여 평균적으로 O(log n)입니다.

아주 간단한 데이터 구조는 splay tree입니다. Chris Okasaki의 Purely Functional Datastructures에는 멋진 스플레이 트리가 구현되어 있습니다. 실제로이 책에는 정말 멋진 데이터 구조가 많이 있습니다. 추천. (검색을하면, 온라인으로 오카사키의 논문을 볼 수 있습니다. 스플레이 트리가 구현되어 있습니다.)