C에서 메모리 효율적인 이중 링크 목록은 무엇입니까?
저는 C 데이터 구조에 대한 책을 읽다가 "메모리 효율적인 이중 링크 목록"이라는 용어를 접했습니다.메모리 효율적인 이중 링크 목록은 일반 이중 링크 목록보다 메모리를 적게 사용하지만 동일한 작업을 수행한다는 한 줄만 있습니다.그 이상은 설명되지 않았고, 예도 제시되지 않았습니다.단지 이것은 저널에서 가져온 것이고 괄호 안에 있는 "신하"라는 것이 주어졌습니다.
구글에서 검색해 본 결과, 가장 가까운 곳은 이것이었습니다.하지만, 저는 아무것도 이해할 수 없었습니다.
누가 C에서 메모리 효율적인 이중 링크 목록이 무엇인지 설명해 줄 수 있습니까?일반적인 이중 링크 목록과 어떻게 다릅니까?
편집: 네, 제가 심각한 실수를 저질렀습니다.제가 위에 올린 링크를 보세요, 기사의 두 번째 페이지였습니다.저는 첫 페이지가 있는 것을 보지 못했고, 주어진 링크가 첫 페이지라고 생각했습니다.기사의 첫 페이지는 실제로 설명을 해주지만, 저는 그것이 완벽하다고 생각하지 않습니다.메모리 효율적인 연결 목록 또는 XOR 연결 목록의 기본 개념에 대해서만 설명합니다.
저는 이것이 제 두 번째 답변이라는 것을 알고 있지만, 제가 여기서 제공하는 설명이 마지막 답변보다 더 나을 수도 있다고 생각합니다.하지만 그 대답조차도 옳다는 것을 명심하세요.
메모리 효율적인 연결 목록은 XOR 로직 게이트와 해당 속성에 전적으로 의존하기 때문에 XOR 연결 목록이라고도 합니다.
Double Linked List와 다른가요?
네, 그렇습니다.실제로 Double Linked List와 거의 동일한 작업을 수행하고 있지만 다릅니다.
Double-Linked List에는 다음 노드와 이전 노드를 가리키는 두 개의 포인터가 저장되어 있습니다.기본적으로, 돌아가고 싶다면, 당신은 그가 가리키는 주소로 갑니다.back 앞으로 곳에 있는 로 가보세요.next다음과 같습니다.
메모리 효율적인 연결 목록, 즉 XOR 연결 목록에는 두 개의 포인터 대신 하나의 포인터만 있습니다.이전 주소(addr(prev)) XOR(^) 다음 주소(addr(next))를 저장합니다.다음 노드로 이동하려면 특정 계산을 수행하여 다음 노드의 주소를 찾습니다.이전 노드로 이동하는 경우에도 마찬가지입니다.다음과 같습니다.
어떻게 작동합니까?
XOR Linked List는 이름에서 알 수 있듯이 논리 게이트 XOR(^)과 속성에 크게 의존합니다.
속성은 다음과 같습니다.
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
이제 이 문제는 제쳐두고 각 노드가 저장하는 내용을 살펴보겠습니다.
첫 번째 노드 또는 헤드가 저장합니다.0 ^ addr (next)이전 노드 또는 주소가 없기 때문입니다.모양은 다음과 같습니다.
두 는 그면두번노저다니장됩가드째를 저장합니다.addr (prev) ^ addr (next)모양은 다음과 같습니다.
위의 그림은 노드 B 또는 두 번째 노드를 보여줍니다.A와 C는 세 번째와 첫 번째 노드의 주소입니다.머리와 꼬리를 제외한 모든 노드는 위와 같습니다.
목록의 끝에는 다음 노드가 없으므로 다음 노드가 저장됩니다.addr (prev) ^ 0모양은 다음과 같습니다.
이동 방법을 확인하기 전에 XOR Linked List의 표현을 다시 살펴보겠습니다.
보면은
앞뒤로 이동하는 링크 필드가 하나 있다는 것을 의미합니다.
또한 XOR Linked List를 사용하는 경우 이전에 있었던 노드의 주소를 저장하는 임시 변수(노드가 아님)가 있어야 합니다.다음 노드로 이동하면 이전 값을 삭제하고 이전 노드의 주소를 저장합니다.
머리에서 다음 노드로 이동
이제 첫 번째 노드 또는 노드 A에 있다고 가정합니다.이제 노드 B에서 이동하려고 합니다.이를 위한 공식은 다음과 같습니다.
Address of Next Node = Address of Previous Node ^ pointer in the current Node
그러면 다음과 같습니다.
addr (next) = addr (prev) ^ (0 ^ addr (next))
이것이 헤드이므로 이전 주소는 단순히 0입니다. 따라서:
addr (next) = 0 ^ (0 ^ addr (next))
괄호를 제거할 수 있습니다.
addr (next) = 0 ^ 0 addr (next)
none (2)재산, 우리는 말할 수 있습니다.0 ^ 0 00으로 설정됩니다.
addr (next) = 0 ^ addr (next)
none (1)다음과 같이 단순화할 수 있습니다.
addr (next) = addr (next)
다음 노드의 주소를 받았습니다!
노드에서 다음 노드로 이동
이제 이전 노드와 다음 노드가 있는 중간 노드에 있다고 가정해 보겠습니다.
공식을 적용해 보겠습니다.
Address of Next Node = Address of Previous Node ^ pointer in the current Node
이제 값을 대체합니다.
addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))
괄호 제거:
addr (next) = addr (prev) ^ addr (prev) ^ addr (next)
none (2)단순화할 수 있는 자산:
addr (next) = 0 ^ addr (next)
none (1)단순화할 수 있는 자산:
addr (next) = addr (next)
그리고 당신은 그것을 얻습니다!
노드에서 이전에 있던 노드로 이동
제목을 이해하지 못하면 기본적으로 노드 X에 있다가 노드 Y로 이동한 경우 이전에 방문한 노드 또는 기본적으로 노드 X로 돌아가려는 것입니다.
이것은 번거로운 일이 아닙니다.제가 위에서 언급한 것을 기억하세요, 당신은 당신이 있던 주소를 임시 변수에 저장합니다.방문할 노드의 주소가 변수에 있습니다.
addr (prev) = temp_addr
노드에서 이전 노드로 이동
이것은 위에서 언급한 것과 다릅니다.제 말은, 당신은 노드 Z에 있었고, 지금은 노드 Y에 있고, 노드 X에 가고 싶어한다는 것입니다.
이는 노드에서 다음 노드로 이동하는 것과 거의 같습니다.단지 이것은 그 반대입니다.프로그램을 작성할 때 한 노드에서 다음 노드로 이동할 때 언급한 것과 동일한 단계를 사용합니다. 단지 목록에서 다음 요소를 찾는 것보다 이전 요소를 찾는 것입니다.
설명할 필요는 없을 것 같습니다.
XOR 링크드 리스트의 장점
이렇게 하면 이중으로 연결된 목록보다 적은 메모리를 사용합니다.약 33% 감소.
하나의 포인터만 사용합니다.이렇게 하면 노드의 구조가 단순해집니다.
도이낙스가 말했듯이, XOR의 하위 섹션은 일정한 시간에 반전될 수 있습니다.
XOR 링크드 리스트의 단점
이것은 구현하기가 좀 까다롭습니다.그것은 실패할 가능성이 더 높고, 디버깅하는 것은 꽤 어렵습니다.
모든 변환(int의 경우)은 에서 또는 에서 수행되어야 합니다.
uintptr_t노드의 주소만 획득하고 거기서 트래버싱(또는 기타)을 시작할 수는 없습니다.당신은 항상 머리나 꼬리에서 시작해야 합니다.
점프를 하거나 노드를 건너뛸 수 없습니다.한 명씩 가셔야 합니다.이동하려면 더 많은 작업이 필요합니다.
XOR Linked List를 사용하는 프로그램을 디버깅하는 것은 어렵습니다.Double Linked List를 디버그하는 것이 훨씬 쉽습니다.
레퍼런스
http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/
https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
이것은 메모리를 절약할 수 있는 오래된 프로그래밍 트릭입니다.더 이상 많이 사용되지 않는 것 같습니다. 기억력이 예전만큼 빠듯하지 않기 때문입니다.
기본 아이디어는 다음과 같습니다.일반적인 이중 링크 목록에서는 인접한 목록 요소에 대한 포인터 두 개, 다음 요소를 가리키는 "다음" 포인터와 이전 요소를 가리키는 "사전" 포인터가 있습니다.따라서 적절한 포인터를 사용하여 목록을 앞으로 또는 뒤로 이동할 수 있습니다.
축소 메모리 구현에서 "next"와 "prev"를 "next"와 "prev"의 비트별 배타적 OR(비트별 XOR)인 단일 값으로 바꿉니다.따라서 인접 요소 포인터의 저장 공간을 절반으로 줄일 수 있습니다.
이 기술을 사용하여 목록을 어느 방향으로든 이동할 수 있지만, 이를 수행하려면 이전(또는 다음) 요소의 주소를 알아야 합니다.예를 들어, 목록을 순방향으로 이동하는 경우 주소가 "prev"인 경우, "prev"인 현재 결합된 포인터 값인 "prev"의 비트별 XOR를 취하여 "next"를 얻을 수 있습니다.결과는 "prev" XOR "prev" XOR "next"이며, 이는 "next"에 불과합니다.반대 방향에서도 동일한 작업을 수행할 수 있습니다.
단점은 조합된 포인터 값을 디코딩할 컨텍스트가 없기 때문에 "prev" 또는 "next" 요소의 주소를 알지 못하면 해당 요소에 대한 포인터가 지정된 요소를 삭제할 수 없다는 것입니다.
또 다른 단점은 이런 종류의 포인터 트릭이 컴파일러가 예상할 수 있는 일반적인 데이터 유형 검사 메커니즘을 우회한다는 것입니다.
그것은 교묘한 속임수이지만, 솔직히 말해서 요즘에는 그것을 사용할 이유가 거의 없다고 생각합니다.
이 질문에 대한 두 번째 답변을 보는 것이 훨씬 더 명확하기 때문에 추천합니다.하지만 저는 이 대답이 틀렸다고 말하는 것이 아닙니다.이것도 맞습니다.
메모리 효율적인 연결 목록을 XOR 연결 목록이라고도 합니다.
작동 방식
XOR (^) Linked List는 다음을 저장하는 대신 링크 목록입니다.next그리고.back포인터, 우리는 단지 하나의 포인터를 사용하여 두 가지 일을 모두 합니다.next그리고.back속성을 먼저 XOR 로직 게이트 속성을 살펴보겠습니다.
|-------------|------------|------------|
| Name | Formula | Result |
|-------------|------------|------------|
| Commutative | A ^ B | B ^ A |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1) | A ^ 0 | A |
|-------------|------------|------------|
| None (2) | A ^ A | 0 |
|-------------|------------|------------|
| None (3) | (A ^ B) ^ A| B |
|-------------|------------|------------|
이제 예를 들어 보겠습니다.A, B, C, D의 4개 노드로 이중 링크된 목록이 있습니다.다음과 같이 표시됩니다.
각 노드에는 데이터를 저장하기 위한 두 개의 포인터와 하나의 변수가 있습니다.그래서 우리는 세 가지 변수를 사용하고 있습니다.
Double Linked List에 많은 노드가 있는 경우 사용할 메모리가 너무 많습니다.효율성을 높이기 위해 메모리 효율적인 이중 링크 목록을 사용합니다.
메모리 효율적인 이중 연결 목록은 하나의 포인터만 사용하여 XOR 및 해당 속성을 앞뒤로 이동하는 연결 목록입니다.
다음은 그림으로 표현한 것입니다.
어떻게 왔다 갔다 합니까?
임시 변수(노드가 아닌 하나만)가 있습니다.노드를 왼쪽에서 오른쪽으로 이동한다고 가정합니다.노드 A부터 시작합니다.노드 A의 포인터에 노드 B의 주소를 저장합니다.그런 다음 노드 B로 이동합니다.노드 B로 이동하는 동안 임시 변수에 노드 A의 주소를 저장합니다.
는 노B포 (인터의크변) 주는소수입니다.A ^ C이전 노드의 주소(즉 A)를 사용하고 현재 링크 필드와 함께 XOR를 사용하여 C의 주소를 제공합니다.논리적으로, 이것은 다음과 같습니다.
A ^ (A ^ C)
이제 방정식을 단순화해 보겠습니다.다음과 같은 Associative 속성 때문에 괄호를 제거하고 다시 쓸 수 있습니다.
A ^ A ^ C
이를 더욱 단순화하여
0 ^ C
두 번째 속성("표에 명시된 바와 같이 (2) 없음") 때문입니다.
첫 번째 (표에 명시된 바와 같이 "없음 (1)" 속성 때문에, 이것은 기본적으로
C
이 모든 것을 이해할 수 없다면 세 번째 속성(표에 명시된 대로 "없음(3))"을 참조하십시오.
이제 노드 C의 주소를 알게 되었습니다.이것은 돌아가는 것과 같은 과정이 될 것입니다.
노드 C에서 노드 B로 이동했다고 가정해 보겠습니다.노드 C의 주소를 임시 변수에 저장한 후 위의 프로세스를 다시 수행합니다.
참고: 모든 것이 다음과 같습니다.A,B,C요.Bathsheba에게 분명히 말해줘서 고마워요.
XOR 링크드 리스트의 단점
룬딘이 언급했듯이, 모든 변환은 에서 / 로 수행되어야 합니다.
uintptr_t.Sami Kuhmonen이 언급했듯이, 여러분은 단지 무작위 노드가 아니라 잘 정의된 출발점에서 시작해야 합니다.
노드를 그냥 점프할 수는 없습니다.순서대로 가셔야 합니다.
또한 대부분의 경우 XOR 링크된 목록은 이중 링크된 목록보다 좋지 않습니다.
레퍼런스
- https://en.wikipedia.org/wiki/XOR_linked_list
- https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/
- http://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/
좋아요, 그럼 XOR 링크된 목록을 보셨군요. 항목당 포인터가 하나씩 저장됩니다.하지만 그것은 추악하고 추악한 데이터 구조이며, 당신이 할 수 있는 최선과는 거리가 먼 것입니다.
메모리가 걱정되는 경우에는 연결된 배열 목록과 같이 노드당 하나 이상의 요소가 포함된 이중 연결 목록을 사용하는 것이 좋습니다.
예를 들어, XOR 링크된 목록은 항목당 1개의 포인터가 필요하고 항목당 16개의 항목이 포함된 이중 링크된 목록은 16개 항목당 3개의 포인터 또는 항목당 3/16개의 포인터가 필요합니다.(추가 포인터는 노드에 있는 항목 수를 기록하는 정수의 비용입니다.)그것은 1보다 작습니다.
메모리 절약 외에도 노드의 16개 항목이 모두 메모리에서 서로 인접해 있기 때문에 인접성에서 이점을 얻을 수 있습니다.목록을 반복하는 알고리즘이 더 빠를 것입니다.
XOR 링크 목록에서는 노드를 추가하거나 삭제할 때마다 메모리를 할당하거나 사용 가능한 공간을 확보해야 하며 이는 많은 비용이 드는 작업입니다.어레이 연결 목록을 사용하면 노드가 완전히 채워지지 않도록 하여 이보다 더 효과적으로 작업을 수행할 수 있습니다.예를 들어 빈 항목 슬롯을 5개 허용할 경우 최악의 경우 세 번째 삽입 또는 삭제할 때마다 메모리를 할당하거나 사용할 수 있습니다.
노드를 할당하거나 해제하는 방법과 시기를 결정하는 방법에는 여러 가지 가능한 전략이 있습니다.
이미 XOR 링크 목록에 대한 꽤 정교한 설명이 있습니다. 메모리 최적화에 대한 몇 가지 아이디어를 더 공유하겠습니다.
포인터는 일반적으로 64비트 시스템에서 8바이트를 사용합니다.32비트 포인터로 주소 지정 가능한 4GB를 초과하는 RAM의 모든 지점을 지정해야 합니다.
메모리 관리자는 일반적으로 바이트가 아닌 고정 크기 블록을 처리합니다.예: Calloc은 일반적으로 16바이트 단위로 할당합니다.
이 두 가지는 데이터가 1바이트인 경우 해당 이중 링크 목록 요소에 32바이트(8+8+1, 16 배수로 올림)가 필요하다는 것을 의미합니다.XOR 트릭으로 16까지 줄일 수 있습니다.
그러나 더욱 최적화하기 위해 자체 메모리 관리자를 사용하는 것을 고려할 수 있습니다. (a) 1바이트 또는 비트 단위로 이동하는 것과 같은 낮은 세분화도의 블록을 처리하고, (b) 전체 크기에 더 엄격한 제한을 둡니다.예를 들어 목록이 항상 100MB의 연속 블록 안에 들어맞는다는 것을 알고 있는 경우 해당 블록 내의 모든 바이트를 주소 지정하는 데 27비트만 필요합니다.32비트나 64비트가 아닙니다.
일반 목록 클래스를 개발하지는 않았지만 응용 프로그램의 특정 사용 패턴을 알고 있는 경우 대부분의 경우 이러한 메모리 관리자를 구현하는 것이 쉬운 작업일 수 있습니다.예를 들어, 1000개 이상의 요소를 할당하지 않고 각 요소에 5바이트가 필요한 경우 메모리 관리자를 첫 번째 빈 바이트의 인덱스를 유지하는 변수가 있는 5000바이트 배열로 구현할 수 있으며 추가 요소를 할당할 때 해당 인덱스를 가져와 할당된 크기만큼 앞으로 이동하면 됩니다.이 경우 포인터는 실제 포인터(int*와 같은)가 아니라 해당 5000바이트 배열 내의 인덱스일 뿐입니다.
언급URL : https://stackoverflow.com/questions/35841620/what-is-a-memory-efficient-doubly-linked-list-in-c
'programing' 카테고리의 다른 글
| C에서 헤더 파일의 요점은 무엇입니까? (0) | 2023.07.09 |
|---|---|
| 데이터를 제거하지 않고 ggplot 2 축 제한(외부 한계): 확대/축소 (0) | 2023.07.09 |
| asp.net 에서 데이터 테이블 열의 합계를 계산하는 방법은 무엇입니까? (0) | 2023.07.04 |
| 홈브루가 있는 최신 MongoDB로 업데이트할 수 없는 이유는 무엇입니까? (0) | 2023.07.04 |
| 기본, 고유 및 외부 키 제약 조건과 인덱스의 차이점은 무엇입니까? (0) | 2023.07.04 |