주디 배열

컴퓨터 과학에서 주디 배열은 고성능과 낮은 메모리 사용량을 가진 연관 배열의 유형을 구현하는 데이터 구조다.^[1]대부분의 다른 키-값 스토어와 달리, Judy 어레이는 해싱을 사용하지 않고, 키에 압축을 활용하고(정수 또는 문자열일 수 있음), 희박한 데이터를 효율적으로 나타낼 수 있다. 즉, 메모리 사용량이나 처리 시간을 크게 늘리지 않고도 할당되지 않은 광범위한 지수를 가질 수 있다.O(log n)의 순서로 성능 스케일링을 적용하여 페타 소자 범위의 크기를 가진 구조물에서도 효율을 유지할 수 있도록 설계되었다.^[2]대략적으로 말하면, Judy 배열은 256에이릭스의 라딕스 나무로 매우 최적화되어 있다.^[3]

주디 트리는 CPU 캐시 사용을 최대화하는 데 매우 최적화되어 있기 때문에 대개 AVL 트리, B-tree, 해시 테이블, 스킵 리스트보다 빠르다.또한 트리 밸런싱이 필요 없고 해싱 알고리즘이 사용되지 않는다.^[4]

주디 배열은 더글러스 바스킨스에 의해 발명되었고 그의 여동생의 이름을 따서 명명되었다.^[5]

혜택들

메모리 할당

Judy 배열은 역동적이며 요소들이 배열들에 추가되거나 배열에서 제거될 때 증가하거나 축소할 수 있다.주디 배열에서 사용되는 기억은 주디 배열의 요소 수와 거의 비례한다.

속도

Judy 어레이는 RAM의 값비싼 캐시 라인 충전의 수를 최소화하도록 설계되었으며, 따라서 알고리즘에는 캐시 누락을 가능한 자주 방지하기 위한 복잡한 로직들이 포함되어 있다.이러한 캐시 최적화 때문에 Judy 어레이는 특히 대규모 데이터셋의 경우 속도가 빠르다.순차적이거나 거의 순차적인 데이터 세트에서 Judy 어레이는 해시 테이블을 능가할 수 있는데, 이는 해시 테이블과 달리 Judy 어레이의 내부 트리 구조가 키의 순서를 유지하기 때문이다.^[6]

단점

Judy 배열은 매우 복잡하다.가장 작은 구현은 수천 줄의 코드다.^[5]또한 Judy 어레이는 64바이트 캐시 라인이 있는 기계에 최적화되어 있어 중요한 재작성 없이 기본적으로 휴대할 수 없다.^[6]대부분의 애플리케이션에서 가능한 성능 이점은 데이터 구조 구현의 높은 복잡성을 정당화하기에는 너무 작다.

참고 항목

• 라딕스 트리
• 해시 배열 매핑 트리

참조

외부 링크

• 메인 주디 어레이 사이트
• Judy 어레이의 작동 방식과 속도가 왜 그렇게 빠른 이유
• Judy 어레이에 대한 전체 기술 설명
• Judy와 Hash Tables의 독립적인 성능 비교
• 1250줄의 C 코드에서 Judy 어레이를 콤팩트하게 구현