Atree: 간단하고 효율적인 포인터 없는 Tree 구현체

• Apter Trees in C++
• [노드값, 부모인덱스) 두개의 벡터만 사용하여 단순하게 표현한 트리
• 대부분의 트리는 이진 트리처럼 구현되며,각 노드가 자신의 값과 왼쪽/오른쪽 자식노드에 대한 포인터를 포함
• 이런 데이터 구조는 재귀로 구현해야 하고, 캐시 동작 및 빈번한 malloc()으로 인해 속도가 느려질수 있음
• 누가 트리 노드를 '소유'하는 지에 대한 개념은 멀티레이어 소프트웨어에서는 복잡해 질수 있음
• Apter 트리는 훨씬 빠르고, 추론하기 쉬우며, 구현하기 쉬움

동작 방식

• 크기가 같은 두개의 배열로 구현
  • 데이터의 벡터(배열) d
  • 부모 인덱스의 벡터 p. d 벡터의 인덱스가 키로 사용됨(c)
  • 종종 키/인덱스 c 는 정수형
• Coco 가 Molly 와 Arca의 부모이고, Arca가 Cricket이라는 자식이 있다면 아래와 같은 구조가 됨
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• 부모가 0이면서 키가 0인 노드가 루트노드 (Apter 트리는 루트노드가 필수이거나 또는 -1 이 "부모 없음"을 의미하지만 여기서는 무시)
• 컴퓨터는 벡터를 매우 빠르게 조작할 수 있음. 포인터 연산보다 훨씬 빠르기 때문에 알고리즘에 대한 빅-O 표기법을 비교하는 것은 실제로는 의미가 없음

중요성

• 이 구현 방식은 본인이 본 트리 구현 방식 중 가장 우아함
• 적절한 벡터 연산 라이브러리를 사용하면 이해하기 쉽고 버그를 찾기 쉬움
• 간단함으로 인해 다른 사용 시나리오에 쉽게 적용 가능
• 부모 인덱스 벡터를 무시하고 값들을 빠르게 반복할 수 있으며, 이는 무료로 사용가능한 Deep Map과 같음
• GPU 친화적이며, 임베디드 환경에서 사용하기 쉬움
• 벡터의 크기를 특정 크기 이상으로 성장하지 않게 함으로써 보안을 쉽게 유지할 수 있음

기원

• 이 기술을 발명한 사람을 찾기 위해 노력 중이며, 60년대와 70년대 벡터 지향적인 시기에 이미 이름이 있었을 것으로 추측함.
• Apter가 설명한 대로 처음 완전한 설명을 보았지만, K3에서도 널리 문서화되었음
• APL은 전통적인 방식으로 트리를 구현하지만, 벡터 그래프에 대해 유사한 기술을 사용함
• J 사용자들에게도 알려져 있으며, Rosetta Code의 J 언어 트리 구현에 대한 설명이 있음
• John Earnest는 벡터 트리 구현에 대해 더 자세히 설명하며, "오프셋 인덱스" 접근 방식을 포함하여 삭제 항목에 대해 설명함.
• 더 복잡한 접근 방식은 각 항목의 깊이를 추적하는 것임

다른 일반적인 트리 구현

• FreeBSD의 커널 트리 구현, klib의 트리, Ruby의 트리 클래스, Python 선언적 트리 클래스 등이 있음
• 이들은 Apter 트리와 동일한 기능을 수행하지 않으며, 일부는 일반화로 인해 훨씬 더 큼

이 코드의 현황

• C++17을 배우기 위해 이를 구현해보는 시도를 함.
• 아직 사용 준비가 되지 않았으며, C++에 대해 더 많이 배울 필요가 있음.

GN⁺의 의견

• Apter Trees는 기존의 복잡한 트리 구조를 단순화하여 빠르고 효율적인 데이터 관리를 가능하게 함.
• 벡터 기반의 트리 구현은 메모리 오버헤드를 최소화하고, 선형적인 접근을 통해 성능을 향상시킬 수 있음.
• 이 기사는 소프트웨어 엔지니어링에서 데이터 구조의 혁신적인 접근 방식을 탐구하는 데 흥미로움을 제공함

[GN⁺]

Hacker News 의견

• 한 사용자는 자신의 작업이 해커뉴스에 링크되어 있는 것을 보고 놀랐음을 표현함. 그는 가벼운 배열 기반 데이터 구조에 관심이 많았고, 특히 3D 모델 스키닝을 위한 노드 트리에 자주 사용되는 구현 방식에 대해 언급함. 부모 노드가 자식 노드보다 먼저 오도록 배열을 정렬하면, 모든 노드에 대해 세계 변환을 재계산하는 것이 단순한 반복문으로 처리될 수 있음을 설명함.
• 다른 사용자는 이러한 트리 스타일에서 자식 노드를 반복하는 것이 O(N)이라는 댓글에 대해, '첫 번째 자식'과 '다음 형제'를 가리키는 포인터를 추가함으로써 atree 디자인을 일반화하는 것이 실제로 쉽다고 언급함. 또한, 필요한 작업을 지원하기 위해 데이터 구조를 변경하는 것을 권장함.
• 한 사용자는 노드를 배열에 저장하고 인덱스를 포인터로 사용하는 것이 트리 알고리즘 구현에 필수적이라고 주장함. 특히, 노드의 자식에 접근해야 할 경우, 메모리 절약을 위해 내부 노드와 잎 노드에 대해 별도의 구조를 고려해야 한다고 조언함.
• 또 다른 사용자는 부모 배열로 트리를 표현하는 방식이 해커뉴스에서 많은 관심을 받는 것이 다소 이상하다고 언급함. 이는 좋은 프레젠테이션이 기본적인 아이디어를 얼마나 멀리 나아가게 할 수 있는지 보여준다고 생각함.
• 한 사용자는 이 프로젝트가 시스템 포인터를 자체 포인터로 대체하는 것에 불과하다고 지적함.
• 다른 사용자는 mallocs를 줄이고 데이터 지역성을 증진시키고자 한다면, 노드 풀을 사용하는 전통적인 트리 구현을 시도해볼 것을 제안함.
• Aaron Hsu의 APL을 사용한 설명을 참고할 것을 권장하는 댓글이 있음.
• 한 사용자는 노드의 모든 자식을 함께 패킹하는 구조 변경을 제안함. 이렇게 하면 이진 검색으로 노드의 모든 자식 목록을 찾을 수 있고 캐시 친화적인 특성을 가질 수 있음을 언급함.
• 배열 내 인덱스를 '핸들' 또는 '인덱스-핸들'로 일컫는 것에 대한 댓글이 있으며, 이 트리 표현 방식이 힙과 분리 집합과 같은 클래식한 데이터 구조를 연상시킨다고 언급함.
• 마지막으로, 배열 인덱스도 일종의 '포인터'라고 할 수 있으며, 전통적인 트리 구현이 malloc을 요구하는 것은 동적으로 노드를 추가하거나 제거할 필요성 때문이라고 설명하는 댓글이 있음. 트리의 크기가 제한적이고 자주 삭제하지 않는 경우 배열 구현이 적합할 수 있음을 언급함.