언롤링된 링크 리스트

이 기사는 대부분 또는 전체적으로 단일 출처에 의존하고 있습니다. 관련 토론은 토크 페이지에서 확인할 수 있습니다. 추가 출처에 인용문을 도입하여 이 기사의 개선에 도움을 주시기 바랍니다.출처 : "Unrolled Linked List"– 뉴스 · 신문 · 도서 · 학자 · JSTOR ( 2021년 3월)

컴퓨터 프로그래밍에서 언롤링 링크드 리스트는 각 노드에 여러 요소를 저장하는 링크드 리스트의 변형입니다.캐시 퍼포먼스를 대폭 향상시키면서 참조 등의 리스트 메타데이터 저장과 관련된 메모리 오버헤드를 줄일 수 있습니다.B-트리와 관련되어 있습니다.

개요

롤링되지 않은 일반적인 링크 목록 노드는 다음과 같습니다.

레코드 노드 { node next // list int numElements // 이 노드의 요소 수, 최대 maxElements 어레이 요소 수 // maxElements 요소에 할당된 공간이 있는 // numElements 요소의 배열 수

각 노드는 최대 수의 요소를 보유하고 있으며, 일반적으로 노드가 단일 캐시 행 또는 소수의 배수를 채울 수 있을 정도로 충분히 큽니다.리스트 내의 위치는 노드에 대한 참조와 요소 배열 내의 위치 양쪽에 의해 나타난다.롤링된 이중 링크 목록에 대한 이전 포인터를 포함할 수도 있습니다.

새 요소를 삽입하려면 요소가 있어야 하는 노드를 찾아 요소를 에 삽입합니다.elements배열, 증가numElements어레이가 이미 가득 찬 경우 먼저 현재 노드 앞 또는 뒤에 새 노드를 삽입하고 현재 노드의 요소의 절반을 이동합니다.

요소를 삭제하려면 요소가 있는 노드를 찾아 에서 삭제합니다.elements배열, 감소numElements노드를 절반 이하로 줄일 경우 다음 노드에서 요소를 이동하여 절반 이상으로 되돌립니다.다음 노드의 용량이 절반 미만인 경우 나머지 모든 요소를 현재 노드로 이동한 후 바이패스하여 삭제합니다.

성능

롤링되지 않은 링크 목록의 주요 이점 중 하나는 스토리지 요구 사항이 줄어든다는 것입니다.모든 노드(최대 1개 제외)가 절반 이상 찼습니다.랜덤 삽입 및 삭제가 많이 이루어지면 평균 노드는 약 4분의 3으로 가득 차게 되며, 삽입 및 삭제가 처음과 끝에서만 이루어지면 거의 모든 노드가 가득 차게 됩니다.다음과 같이 가정합니다.

• m =maxElements, 각 요소의 최대수elements어레이
• v = 참조 및 요소 수에 대한 노드당 오버헤드;
• s = 단일 요소의 크기입니다.

n개의 요소에 사용되는 공간은 (${\displaystyle v}$/${\displaystyle m}$ +${\displaystyle s}$ )$n$ $($v / $m$+ s )n $( 2$${\displaystyle v}$ /${\displaystyle m}$$$+ s )${\displaystyle n}$( 2 v$$/ m +${\displaystyle s}$ )n ( $2$$display style$ ( v$+ m$$+$${\displaystyle s}$)$n$$$$\}$공간이 필요합니다$.{\displaystyle }$비교하기 위해 일반 링크 목록에는 $v$는 작지만 대부분의 데이터 배열은 콤팩트합니다.$공간을 표시합니다$$.$롤링되지 않은 연결 목록은 오버헤드 v를 목록의 여러 요소에 효과적으로 분산시킵니다.따라서 오버헤드가 클 때 가장 큰 공간 이득을 볼 수 있습니다.maxElements크기가 크거나 요소가 작습니다.

비트와 같이 요소가 특히 작을 경우 오버헤드는 많은 기계의 데이터보다 최대 64배 커질 수 있습니다.또한 널리 사용되는 많은 메모리 할당자는 할당된 각 노드에 대해 소량의 메타데이터를 유지하므로 효과적인 오버헤드가 증가합니다. 둘 다 롤링되지 않은 링크 목록을 더욱 매력적으로 만듭니다.

언롤 링크드 리스트노드는 각각 다음 필드 옆에 카운트를 저장하기 때문에 언롤 링크드 리스트의 k번째 요소(인덱싱)의 취득은 n/m + 1 캐시 미스(일반 링크드 리스트보다 최대 m배)로 실행할 수 있습니다.또한 각 요소의 크기가 캐시 회선 크기에 비해 작을 경우 일반적인 링크 목록보다 캐시 누락이 적은 순서대로 목록을 통과할 수 있습니다.어느 경우든 작업 시간은 목록 크기에 따라 선형적으로 증가합니다.

「 」를 참조해 주세요.

• CDR 부호화
• 스킵 리스트
• 티트리
• XOR 링크 리스트
• 해시 어레이 트리

레퍼런스

• Shao, Z.; Reppy, J. H.; Appel, A. W. (1994), "Unrolling lists", Conference Record of the 1994 ACM Conference on Lisp and Functional Programming: 185–191, doi:10.1145/182409.182453, ISBN 978-0897916431, S2CID 3192876

외부 링크

• C로 기술된 구현
• Java로 작성된 다른 구현
• 골랑어로 작성된 구현
• 오픈 데이터 구조 - 섹션 3.3 - SEList: 공간 효율이 뛰어난 링크 리스트, Pat Morin