증강 연결 목록: 필수 가이드

연결 목록은 어떻게 작동하나요?

연결리스트(Linked List)는 각 데이터의 필드가 오프셋 대신 포인터로 연결된 데이터 구조입니다. 이는 필요한 모든 사용자 필드(예: 전화, 소유자, 회사 등)를 포함하는 소위 노드 요소라고 하는 첫 번째 및 마지막 요소를 저장하는 기본 요소와 다음 노드에 대한 포인터로 구성됩니다. 마지막 요소는 목록의 끝을 나타내는 NULL 필드에 연결됩니다.

연결된 목록에 새 요소가 추가되면 주 노드는 "꼬리" 포인터를 새 끝 노드로 업데이트해야 하며 이전 NULL 포인터는 새 꼬리로 업데이트해야 합니다.

이 데이터 구조를 사용하면 전체 배열의 크기를 조정하지 않고도 새 데이터를 효율적으로 기록할 수 있습니다. 이는 쓰기 전용 데이터를 저장하는 효과적인 방법이며 요소의 양을 미리 알 필요가 없습니다. 이는 간단한 데이터 구조이며, 메모리에서는 다음과 같습니다.

퇴거 키에 대한 연결 목록

이전 기사 에서 우리는 각 항목 삭제 후 트리를 떠나지 않고 트리를 스캔하기 위한 버퍼의 필요성에 대해 논의했습니다. GC가 있는 언어에서는 이는 문제가 되지 않습니다. 그러나 애플리케이션 코드가 메모리를 관리하는 경우 오래된 요소가 포함된 연결 목록을 기반으로 하는 버퍼가 해결책이 될 수 있습니다.

연결된 목록을 사용하면 요소를 빠르게 추가할 수 있습니다. 그러나 연결된 목록에서 무엇이든 찾으려면 순차적 검색이 필요하므로 빠른 키 검색에는 적합하지 않습니다. 따라서 데이터 로깅, 임시 버퍼 생성 및 데이터 구성을 통해 헤드 노드에서 순차적 읽기를 수행하는 효율적인 솔루션입니다.

선점할 요소를 찾는 것이 이러한 작업의 예입니다. 선점은 다양한 캐시 구현에서 자주 사용됩니다. 캐시에는 대기 시간이 더 긴 다른 메모리 소스에서 복원할 수 있는 데이터가 포함되어 있습니다. 캐시는 일반적으로 메인 메모리에 저장됩니다. 주 메모리는 제한되어 있으므로 효과적인 사용을 위해 작은 데이터 스냅샷만 주 메모리에 저장할 수 있습니다.

이를 위해서는 메모리를 보다 현명하게 사용해야 하며, 거의 요청되지 않는 데이터에 대한 메모리 사용을 피하고 요청 빈도가 너무 낮은 경우 해당 데이터를 제거해야 합니다.

캐시에서 필드를 제거하는 효과적인 방법은 LRU(Least Recent Used) 방법입니다. 다음은 LRU 표현입니다.

이 경우 애플리케이션에는 최근에 사용한 개체를 저장하기 위한 연결 목록이 하나 이상 포함되어 있으며 빠른 검색을 위한 다른 데이터 구조(해시 테이블 등)가 있습니다. 노드는 서로 연결되어 있습니다.

사용자가 해시 테이블에서 데이터를 검색하면 연결된 목록은 이 데이터를 꼬리로 이동하여 새로 고칩니다. 결과적으로 여러 작업을 수행한 후 꼬리에는 최근에 사용된 데이터가 포함되고, 머리에는 거의 요청되지 않은 데이터가 포함됩니다.

메모리 오버플로가 발생하는 경우 애플리케이션은 처음 N개 요소를 스캔하여 충분한 메모리를 해제할 수 있습니다. 연결된 목록이 순차 스캔에 적용되므로 이는 간단한 작업입니다. 거의 사용되지 않는 데이터가 있는 메모리가 해제되고, 더 자주 사용되는 새로운 노드가 캐시에 저장될 수 있습니다.

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

한 가지 참고 사항: 사용하는 요소 수의 빈도가 크게 다른 경우(예: 요청의 95%가 100만 개 중 상위 100개 키에 분산됨) 캐시를 저장하는 데 Splay Tree가 더 적합할 수 있습니다. 이 트리는 각 노드 사용 빈도에 따라 균형을 이룹니다.

Splay Tree의 주요 아이디어는 LRU와 반대입니다. 즉, 가장 많이 사용되는 요소가 루트 근처에 위치하므로 이 데이터 구조가 캐시의 기본 구조로 이상적으로 만들어집니다.

퇴거는 두 가지 방법으로 해결될 수 있습니다. 즉, 기본 구조체와 상호 연결된 연결 목록을 사용하거나 스플레이 트리를 스레드 이진 트리로 수정하는 것입니다. 스플레이 트리의 노드는 이미 사용 빈도에 따라 정렬되어 있습니다. 트리 리프의 추가 스레딩에는 더 많은 CPU 시간이 필요할 수 있으므로 메모리를 절약할 수 있습니다.

메모리에서 최근 사용된 데이터의 가속화를 더 잘 이해하려면 이 링크 에서 실시간 VM 마이그레이션의 예를 탐색할 수 있습니다.

연결 목록의 검색 속도 향상

이전에 언급했듯이 연결 목록은 데이터 쓰기를 위한 가장 빠른 솔루션을 제공합니다. 스캔 속도는 좋지만 어레이의 스캔 속도보다 느립니다.

이전 기사 에서는 이 문제를 데이터 지역성으로 설명했습니다. 그러나 이진 트리와 유사하므로 연결 목록은 개선될 가능성이 있습니다. 연결된 목록을 펼치면 목록의 각 노드에 더 많은 데이터를 저장할 수 있습니다. 따라서 다음 포인터 노드에서 메모리를 절약하고 때로는 요소의 크기가 CPU 캐시 라인에 맞는 조건에서 성능을 향상시킵니다.

주요 아이디어는 변경되지 않지만 메모리에 있는 목록의 표현은 변경됩니다.

그것은 여러 면에서 바뀔 것이다. 아래에는 2가지 옵션이 있습니다.

이러한 개선 사항은 연결 목록의 성능을 향상시키지만 코드에 약간의 복잡성을 추가합니다. 연결된 목록이 있는 디스크 작업의 경우 펼쳐진 노드는 더 많은 요소를 가질 수 있습니다. 작동 방식을 이해하는 쉬운 방법은 연결된 배열 목록을 상상하는 것입니다.

코드에서 구조체 설명을 수정해야 하며, 지금부터 구조체 배열의 각 요소를 읽거나 써야 합니다.

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

건너뛰기 목록

스킵 리스트는 연결 리스트의 검색 요소의 속도 특성을 향상시키기 위한 방법이다. 이 유형의 연결 목록은 연결 목록의 순서를 지정하는 키를 저장하고 간단한 검색 작업보다 더 효율적으로 노드를 찾을 수 있는 추가 포인터를 포함합니다.

추가 노드는 건너뛰기 목록의 노드 간 이동 속도를 향상시킵니다. 이진 검색처럼 작동합니다. 오히려 새로운 요소를 추가하는 데 더 많은 시간이 걸립니다. 따라서 건너뛰기 목록에는 키가 있어야 합니다. 응용 프로그램은 속도 특성을 향상시키기 위해 여러 수준을 만들 수 있습니다. 대부분의 경우 더 나은 선택은 트리의 높이와 약간 낮거나 거의 같은 수준을 갖는 것입니다. (위 사진을 보세요)

검색 중에는 가장 빠른 경로인 최상위 레벨부터 애플리케이션이 시작됩니다. Near 키를 감지하면 원하는 노드를 찾을 때까지 더 낮은 수준으로 내려갑니다.

이 프로세스는 O(log(n))의 시간 복잡도를 초래합니다. 예를 들어, 16개 노드가 있는 건너뛰기 목록에 4개 수준, 100만 개 노드에 20개 수준, 40억 개 노드에 32개 수준을 사용하면 RB-트리와 유사한 시간 복잡성을 제공합니다.

건너뛰기 목록은 다음과 같은 이유로 더 좋습니다.

• 구현의 단순성. RB-트리와 유사한 특성에도 불구하고 구현 및 유지 관리가 훨씬 쉽습니다.

• 건너뛰기 목록 끝에 새 노드를 추가하는 효율성이 높습니다.

• 스레드로부터 안전한 건너뛰기 목록 구현을 만드는 것은 트리보다 쉽습니다.

이 개념의 구현을 살펴보겠습니다!

구조 노드:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

노드를 생성하는 기능:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

삽입하는 동안 작업에는 노드를 저장할 올바른 위치를 감지하고 이 노드에 연결할 레벨 수를 결정하는 작업이 포함됩니다. 레벨을 결정하기 위해 무작위 함수를 사용하면 각각의 새 노드에 대한 프로세스를 단순화하는 데 도움이 됩니다. 평균적으로 이 함수는 50%의 사례에서 두 번째 수준을 할당하고, 사례의 25%에서 세 번째 수준을 할당합니다. 이 방법은 요소의 균형을 재조정하기 위해 메모리에 액세스하는 시간을 최소화합니다.

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

노드 검색 기능:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

연결 목록, 건너뛰기 목록 및 RB 트리의 성능을 테스트하는 벤치마크 기능입니다. 키로 사용되는 값은 2의 거듭제곱으로 설정됩니다. 테스트 목적의 값은 중요하지 않습니다.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

순차적으로 증가하는 키에 대해 이 데이터 구조를 테스트한 결과:

이는 삽입하기에 가장 좋은 시기이며(간단한 연결 목록을 고려하지 않는 경우) 요소를 검색하는 매우 빠른 방법입니다.

순차적으로 감소하는 키에 대해 이 데이터 구조를 테스트한 결과:

이는 이해하기 쉽습니다. 이 스킵 리스트 구현에는 첫 번째 요소에 대한 헤드 포인터만 있습니다. 끝에 노드를 추가하는 것은 더 복잡합니다. 이 접근 방식을 변경하려면 두 번째 포인터(꼬리 부분에)를 추가하거나 역방향 건너뛰기 목록(머리 부분이 큰 값을 가리킴)을 추가할 수 있습니다. 이는 건너뛰기 목록이 Kafka 스트림과 같은 로그 데이터에 효과적인 데이터 구조임을 의미합니다. 이 경우 RB 트리보다 최소 2배 빠르고 구현이 더 쉬울 수 있습니다.

Skip List는 Linked list의 삽입 속도를 줄이지만 순차 데이터의 경우 특히 키가 순차적으로 증가하는 동안 요소에 대한 대수 액세스 시간을 사용하여 다른 데이터 구조보다 빠르게 유지됩니다. 그럼에도 불구하고 키가 순차적으로 증가하면 트리 균형을 유지하기 위해 많은 회전이 발생하므로 트리 삽입이 복잡해집니다.

시퀀스 전체에서 값이 증가(또는 감소)하는 경우에만 효과적으로 작동합니다. 예를 들어 키를 무작위로 선택하면 결과가 달라집니다.

보시다시피, 값 전체의 분포는 RB 트리의 속도 특성에 큰 영향을 미치지 않지만 건너뛰기 목록의 성능에는 특히 영향을 미칩니다.

결론

오늘날 우리의 애플리케이션은 다양한 방식으로 메모리나 디스크의 데이터를 구성할 수 있습니다. 맵과 목록은 다양한 목적을 위해 데이터를 다양한 순서로 배열하는 데 중요한 역할을 합니다. 이러한 구조는 충분한 성능, 자원 효율성 및 역량을 보장합니다.

때로는 우리의 요구 사항에 충분하지 않은 경우가 있으며, 응용 프로그램을 더 최적화하기 위해 중요한 부분에서 변경해야 합니다. 일부 경우에는 부정확한 일치 또는 메모리 절약을 위한 트리와 같은 보다 적합한 데이터 구조를 사용하면 이점을 얻을 수 있습니다. 기타 - 비동기식 방법을 사용하여 개별 스레드 성능을 향상시키는 등의 알고리즘 개선.

다른 모든 옵션이 소진되면 남은 접근 방식은 데이터 구조를 조정하고 사용 방법을 조정하는 것입니다. 실제로 특정 작업에 더 적합하도록 데이터 구조를 일부 변경한 예가 있습니다.

연결된 목록은 주로 쓰기 전용 및 시퀀스 검색 데이터 구조이지만 RB 트리보다 더 최적화될 수 있으며 쓰기 전용 경우에도 효율성을 유지할 수 있습니다. 그러나 특정 특성이 향상되면 다른 특성에 영향을 미칠 수 있습니다. 그러므로 가장 좋은 방법은 중요한 것을 우선시하고 그렇지 않은 것을 버리는 것입니다.