실제로는 유용하지만 대부분의 프로그래머에게는 알려지지 않은 데이터 구조가 있습니다. 그들은 어느 것입니까?
링크 된 목록, 이진 트리 및 해시에 대해서는 누구나 알고 있지만 목록 건너 뛰기 및 블룸 필터 는 무엇입니까 ? 나는 일반적이지 않지만 더 많은 데이터 구조를 알고 싶습니다. 훌륭한 아이디어에 의존하고 프로그래머의 도구 상자를 풍부하게하기 때문에 알아야 할 가치가 있습니다.
추신 : 나는 또한 일반적인 데이터 구조의 속성을 영리하게 사용하는 춤 링크 와 같은 기술에 관심 이 있습니다.
편집 : 데이터 구조를 자세히 설명하는 페이지에 대한 링크 를 포함 시키십시오. 또한 Jonas Kölker가 이미 지적한 것처럼 데이터 구조가 멋진 이유 에 대해 몇 마디를 추가하십시오 . 또한 답변 당 하나의 데이터 구조 를 제공하십시오 . 이를 통해 투표만으로 더 나은 데이터 구조를 맨 위에 표시 할 수 있습니다.
답변
접두사 트리 또는 크리트 비트 트리 라고도하는 Tries 는 40 년 이상 존재했지만 여전히 상대적으로 알려지지 않았습니다. 시도를 매우 멋지게 사용하는 방법은 ” TRASH-동적 LC-trie 및 해시 데이터 구조 “에 설명되어 있으며 trie와 해시 함수를 결합합니다.
답변
블룸 필터 : m 비트 의 비트 배열로 , 처음에는 모두 0으로 설정됩니다.
당신은을 통해 그것을 실행 항목을 추가하려면 k 개의 해시 함수를 그건 당신이 줄 것이다 케이 하면 배열에 색인을 하고 1로 설정합니다.
항목이 세트에 있는지 확인 하려면 k 인덱스를 계산하고 모두 1로 설정되어 있는지 확인하십시오.
물론, 이것은 위양성 일 가능성이 있습니다 (wikipedia에 따르면 약 0.61 ^ (m / n)이며 여기서 n은 삽입 된 항목 수입니다). 부정 부정은 불가능합니다.
항목을 제거하는 것은 불가능하지만 int 배열과 증가 / 감소로 표시되는 counting bloom filter를 구현할 수 있습니다 .
답변
로프 : 저렴한 접두사, 부분 문자열, 중간 삽입 및 추가를 허용하는 문자열입니다. 나는 실제로 한 번만 사용했지만 다른 구조로는 충분하지 않았습니다. 규칙적인 문자열과 배열 접두어는 우리가해야 할 일에 비해 너무 비쌌으며 모든 것을 뒤집는 것은 의문의 여지가 없었습니다.
답변
건너 뛰기 목록 은 매우 깔끔합니다.
위키 백과
건너 뛰기 목록은 이진 검색 트리 (대부분의 작업에서 평균 n 시간 평균 순서)와 비교할 수있는 여러 병렬, 정렬 된 연결 목록을 기반으로하는 확률 적 데이터 구조입니다.
그것들은 균형 잡힌 나무의 대안으로 사용될 수 있습니다 (엄격한 균형 시행 대신에 균형 잡힌 균형 사용). 그들은 구현하기 쉽고 빨강-검정 나무보다 빠릅니다. 나는 그들이 모든 훌륭한 프로그래머들에게 있어야한다고 생각합니다.
건너 뛰기 목록에 대한 심층적 인 소개를 원한다면 여기 에 MIT의 알고리즘 소개 강의 비디오 링크가 있습니다.
또한 여기 에 건너 뛰기 목록을 시각적으로 보여주는 Java 애플릿이 있습니다.
답변
공간 인덱스 , 특히 R- 트리 및 KD- 트리는 공간 데이터를 효율적으로 저장합니다. 지리적 인지도 좌표 데이터 및 VLSI 장소 및 경로 알고리즘에 적합하며 때로는 가장 가까운 이웃 검색에 적합합니다.
비트 어레이 는 개별 비트를 콤팩트하게 저장하고 빠른 비트 작동을 허용합니다.
답변
지퍼 (Zipper) -현재 위치 인 ‘커서’라는 자연스러운 개념을 갖도록 구조를 수정하는 데이터 구조의 파생물입니다. xmonad 창 관리자 와 같이 인덱스가 범위를 벗어날 수 없음을 보장하므로 실제로 유용합니다. 에서 어떤 창에 포커스가 있는지 추적하는 데 사용됩니다.
답변
몇 가지가 있습니다 :
-
접미사가 시도합니다. 거의 모든 종류의 문자열 검색에 유용합니다 (http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). 접미사 배열도 참조하십시오. 그것들은 접미사 나무만큼 빠르지는 않지만 훨씬 작습니다.
-
플레이 트리 (위에서 언급 한 바와 같이). 그들이 멋진 이유는 세 가지입니다.
- 그것들은 작습니다 : 이진 트리에서와 같이 왼쪽 및 오른쪽 포인터 만 필요합니다 (노드 색상 또는 크기 정보를 저장할 필요가 없습니다)
- 그들은 (비교적으로) 구현하기가 매우 쉽습니다.
- 모든 “측정 기준”에 대한 최적의 상각 복잡성을 제공합니다 (모두 알고있는 시간 인 log n 조회 시간). 보다http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
-
힙 순서 검색 트리 : 키와 관련하여 검색 트리이고 우선 순위와 관련하여 힙 순서로 정렬되도록 여러 키 (prio) 쌍을 트리에 저장합니다. 그러한 나무가 독특한 모양을 가지고 있음을 보여줄 수 있습니다 (그리고 항상 왼쪽에서 완전히 채워지는 것은 아닙니다). 임의 우선 순위를 사용하면 예상 O (log n) 검색 시간 IIRC를 제공합니다.
-
틈새 시장은 O (1) 인접 쿼리가있는 무 방향 평면 그래프의 인접 목록입니다. 이것은 기존 데이터 구조를 구성하는 특정 방법만큼 데이터 구조가 아닙니다. 방법은 다음과 같습니다. 모든 평면 그래프에는 최대 6 도의 노드가 있습니다. 이러한 노드를 선택하고 이웃을 이웃 목록에 넣고 그래프에서 제거하고 그래프가 비어있을 때까지 반복합니다. 쌍 (u, v)이 주어지면 v의 이웃 목록에서 u를 찾고 u의 이웃 목록에서 v를 찾으십시오. 둘 다 크기가 최대 6이므로 O (1)입니다.
위의 알고리즘에 따르면 u와 v가 이웃이면 v 목록에 u와 u 목록에 v가 모두 없습니다. 필요한 경우 각 노드의 누락 된 이웃을 해당 노드의 이웃 목록에 추가하고 빠른 검색을 위해 살펴보아야 할 이웃 목록의 양을 저장하십시오.
