XOR 링크 리스트

XOR linked list

XOR 연결 목록은 컴퓨터 프로그래밍에 사용되는 데이터 구조의 한 유형입니다.또한 비트 단위 XOR 연산을 활용하여 이중 링크 목록에 대한 스토리지 요구 사항을 줄입니다.

묘사

일반적인 이중 링크 리스트는 각 목록노드에 이전 및 다음 목록 항목의 주소를 저장합니다.다음 2개의 주소 필드가 필요합니다.

...A B C D E...–> next –> next –> next –> <– prev <– prev>

XOR 링크 리스트는 이전 주소의 비트 단위 XOR(여기서는 「」로 표시)와 다음 주소의 비트 단위 XOR를 하나의 필드에 저장함으로써 동일한 정보를 하나의 주소 필드에 압축합니다.

...A B C D E...【A】【B】【D】【C】【C】【E】

좀 더 형식적으로:

link(B) = addr(A) addr(C), link(C) = addr(B) addr(D), ...

목록을 왼쪽에서 오른쪽으로 이동할 때: 커서가 C에 있다고 가정하면 이전 항목 B는 링크 필드(B'D)의 값과 XOR될 수 있습니다.D 의 주소가 취득되어 리스트 트래버설이 재개될 가능성이 있습니다.다른 방향에도 같은 패턴이 적용됩니다.

예.addr(D) = link(C) ⊕ addr(B)어디에

link(C) = addr(B) addr(D)

그렇게

addr(D) = addr(B) addr(D) add addr(B) = addr(B) add addr(D)

부터

X = 0 = > addr(D) = 0 add addr(D)

부터

X00 = X = > addr(D) = addr(D)

XOR 작업이 취소됩니다.addr(B)이 방정식에 두 번 나타나고 우리에게 남은 건addr(D).

어느 지점에서부터 리스트의 어느 방향으로도 트래버스를 개시하려면 , 연속하는 2개의 항목의 주소가 필요합니다.연속되는 2개의 항목의 주소가 반대로 되어 있는 경우, 리스트 트래버설은 반대 [1]방향으로 발생합니다.

연산 이론

키는 첫 번째 조작이며 XOR 속성은 다음과 같습니다.

  • X = 0
  • Xµ0 = X
  • X-Y = Y-X
  • (XyY) = X((YzZ)

R2 레지스터에는 항상 현재 항목 C의 주소 XOR과 이전 항목 P: CpP의 주소가 포함되어 있습니다.레코드의 [Link]필드에는 좌우 후계자 주소의 XOR이 포함됩니다.예를 들어 현재 링크필드(L'R)를 가진 R2(C'P)의 XOR은 C'P'L'R을 출력합니다.

  • 전자가 L이면 P(=L)와 L은 CΩR에서 소거된다.
  • 전자가 R이면 P(=R)와 R은 소거되고 CΩL은 남는다.

어느 경우든 결과는 다음 주소가 있는 현재 주소의 XOR입니다.이 중 현재 주소가 R1인 XOR은 다음 주소를 남깁니다.R2에는 (현재) 현재 주소와 이전 주소의 필수 XOR 쌍이 남아 있습니다.

특징들

  • 2개의 XOR 조작으로 1개의 항목에서 다음 항목으로의 트래버설을 실행할 수 있습니다.두 경우 모두 동일한 명령으로 충분합니다.아이템이 있는 리스트 검토{…B C D…}또, R1 및 R2는, 현재의 리스트 항목의 주소(예를 들면 C)와 현재의 주소(예를 들면 C theD)의 XOR를 각각 격납한 작업 레지스터이다.시스템으로 캐스팅/360 지침:
X R2, Link R2 <- C'D > B'D(즉, 현재 레코드의 링크필드인 B'C, B'D 포함) XR R1, R2 R1 <-C'B'C(다음 Voil 레코드:
  • 리스트의 종료는 엔드포인트와 같이 엔드포인트 근처에 배치된 어드레스 0의 리스트 아이템을 상상함으로써 나타납니다.{0 A B C…}A의 링크필드는 0µB가 됩니다.두 번의 XOR 연산 후에 현재 항목의 주소를 개발하는 0 결과를 감지하기 위해 위의 시퀀스에서 추가 명령이 필요합니다.
  • 링크 포인터를 0으로 함으로써 리스트 엔드 포인트를 반사시킬 수 있다.제로 포인터는 미러입니다(좌측과 우측 네이버주소의 XOR은 같기 때문에 제로입니다).

결점

  • 범용 디버깅툴은 XOR 체인을 따를 수 없기 때문에 디버깅이 [2]어려워집니다.
  • 메모리 사용량의 감소에 따른 대가는 코드의 복잡성이 증가하여 유지보수가 더 비싸집니다.
  • 대부분의 가비지 수집 방식은 리터럴 포인터가 포함되지 않은 데이터 구조에서는 작동하지 않습니다.
  • 모든 언어가 포인터와 정수 사이의 유형 변환을 지원하는 것은 아닙니다. 포인터의 XOR은 일부 컨텍스트에서 정의되지 않습니다.
  • 목록을 이동하는 동안 이전에 액세스한 노드의 주소가 다음 노드의 주소를 계산하기 위해 필요하며, 예를 들어 목록 항목에 대한 포인터가 다른 데이터 구조에 포함되어 있는 경우, 한 노드가 목록을 통과하지 않으면 포인터를 읽을 수 없습니다.
  • XOR 링크 리스트에는 주소만 알고 목록에서 노드를 삭제할 수 있는 기능이나 기존 노드의 주소만 알고 있을 때 기존 노드 앞 또는 뒤에 새 노드를 삽입하는 기능 등 이중 링크 리스트의 중요한 이점이 몇 가지 없습니다.

컴퓨터 시스템의 메모리는 점점 더 저렴해지고 풍부해지고 있기 때문에 스토리지 오버헤드는 전문 임베디드 시스템 이외에서는 일반적으로 가장 큰 문제가 아닙니다.링크된 목록의 오버헤드를 줄이는 것이 여전히 바람직한 경우, 언롤링은 보다 실용적인 접근법(캐시 성능 향상 및 랜덤 액세스 속도 향상 등 기타 이점)을 제공합니다.

바리에이션

XOR 링크 리스트의 기본 원리는 모든 리버서블 바이너리 연산에 적용할 수 있습니다.XOR를 덧셈 또는 뺄셈으로 대체하면 다음과 같이 약간 다르지만 대체로 동일한 공식들이 나타납니다.

링크 리스트 추가

...A B C D E...【A+C】【B+D】【C+E】

이러한 종류의 리스트는 제로 링크필드가 "미러"가 아니라는 점을 제외하고 XOR 링크 리스트와 완전히 동일한 속성을 가지고 있습니다.목록의 다음 노드의 주소는 현재 노드의 링크 필드에서 이전 노드의 주소를 빼서 지정됩니다.

감산 링크 리스트

...A B C D E...【C-A】 【D-B】【E-C】

이러한 종류의 목록은 목록을 앞으로 이동하기 위해 필요한 명령 시퀀스가 목록을 반대로 이동하기 위해 필요한 시퀀스와 다르다는 점에서 표준 "기존" XOR 링크 목록과 다릅니다.다음 노드의 주소는 이전 노드의 주소에 링크필드를 추가하여 지정됩니다.이전 노드의 주소는 다음 노드의 주소에서 링크필드를 빼서 지정됩니다.

리스트 내의 각 주소에 일정한 오프셋을 추가해도 링크필드에 저장되어 있는 값을 변경할 필요가 없기 때문에 빼기 링크목록은 포인터 값의 패치 없이 목록 전체를 메모리에 재배치할 수 있다는 점도 중요합니다.(시리얼라이제이션도 참조).이는 XOR 링크 목록과 기존 링크 목록 모두에 비해 뛰어난 이점입니다.

이진 검색 트리

XOR 연결 목록 개념은 XOR 이진 검색 [3]트리로 일반화할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "XOR Linked List - A Memory Efficient Doubly Linked List Set 1 - GeeksforGeeks". GeeksforGeeks. 2011-05-23. Retrieved 2018-10-29.
  2. ^ Gadbois, David; et al. "GC [garbage collection] FAQ – draft". Retrieved 5 December 2018.
  3. ^ "c++ associative containers based on the XOR scapegoat tree". Retrieved 5 November 2021.

외부 링크