Danh sách liên kết mở rộng: Hướng dẫn cần thiết

Danh sách liên kết hoạt động như thế nào?

Danh sách liên kết là cấu trúc dữ liệu trong đó các trường của từng dữ liệu được kết nối bằng con trỏ thay vì offset. Nó bao gồm một phần tử chính lưu trữ phần tử đầu tiên và phần tử cuối cùng, được gọi là phần tử nút, chứa tất cả các trường người dùng cần thiết (chẳng hạn như điện thoại, chủ sở hữu, công ty, v.v.) và một con trỏ tới nút tiếp theo. Phần tử cuối cùng được liên kết với trường NULL cho biết phần cuối của danh sách.

Khi một phần tử mới được thêm vào danh sách liên kết, nút chính phải cập nhật con trỏ “đuôi” thành nút cuối mới và con trỏ NULL trước đó phải được cập nhật thành đuôi mới.

Cấu trúc dữ liệu này cho phép ghi lại dữ liệu mới một cách hiệu quả mà không cần thay đổi kích thước toàn bộ mảng. Đây là một phương pháp hiệu quả để lưu trữ dữ liệu chỉ ghi và không yêu cầu biết trước số lượng phần tử. Đó là một cấu trúc dữ liệu đơn giản và trong bộ nhớ, nó trông như thế này:

Danh sách liên kết cho các chìa khóa trục xuất

Trong bài viết trước, chúng ta đã thảo luận về sự cần thiết của bộ đệm để quét cây mà không rời khỏi cây sau mỗi lần xóa mục. Trong các ngôn ngữ có GC, đây không phải là vấn đề. Tuy nhiên, khi mã ứng dụng quản lý bộ nhớ, bộ đệm dựa trên danh sách liên kết chứa các phần tử lỗi thời có thể là một giải pháp.

Danh sách liên kết cho phép bổ sung nhanh các phần tử. Tuy nhiên, việc tìm kiếm bất kỳ thứ gì trong danh sách liên kết yêu cầu phải quét tuần tự, khiến nó không phù hợp để truy xuất khóa nhanh chóng. Do đó, đây là giải pháp hiệu quả để ghi nhật ký dữ liệu, tạo bộ đệm tạm thời và sắp xếp dữ liệu để thực hiện đọc tuần tự từ các nút chính.

Tìm các phần tử để ưu tiên là một ví dụ về nhiệm vụ như vậy. Quyền ưu tiên thường được sử dụng trong các triển khai bộ đệm khác nhau. Bộ đệm chứa dữ liệu có thể được khôi phục từ các nguồn bộ nhớ khác có độ trễ lớn hơn. Cache thường được lưu trữ trong bộ nhớ chính. Bộ nhớ chính có hạn và để sử dụng hiệu quả, chỉ có thể lưu trữ một ảnh chụp nhanh dữ liệu nhỏ trong bộ nhớ chính.

Nó yêu cầu chúng ta sử dụng bộ nhớ thông minh hơn, tránh sử dụng bộ nhớ cho dữ liệu hiếm khi được yêu cầu và xóa dữ liệu đó nếu dữ liệu đó được yêu cầu quá ít.

Một phương pháp hiệu quả để loại bỏ các trường trong bộ đệm là phương pháp Ít được sử dụng gần đây nhất (LRU). Đây là đại diện LRU bên dưới:

Trong trường hợp này, ứng dụng bao gồm ít nhất một danh sách được liên kết để lưu trữ các đối tượng được sử dụng gần đây và có các cấu trúc dữ liệu khác (như bảng băm) để tìm kiếm nhanh. Các nút được kết nối với nhau.

Khi người dùng lấy dữ liệu từ bảng băm, danh sách liên kết sẽ làm mới dữ liệu này bằng cách di chuyển nó xuống cuối bảng. Kết quả là, sau một số thao tác, phần đuôi chứa dữ liệu được sử dụng gần đây, trong khi phần đầu chứa dữ liệu hiếm khi được yêu cầu.

Trong trường hợp tràn bộ nhớ, ứng dụng có thể quét N phần tử đầu tiên để giải phóng đủ bộ nhớ. Đây là một thao tác đơn giản vì danh sách liên kết sẽ thích ứng với các lần quét tuần tự. Bộ nhớ chứa dữ liệu hiếm khi được sử dụng sẽ được giải phóng và các nút mới thường xuyên hơn có thể được lưu trữ trong bộ đệm.

 #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); }

Một lưu ý: khi số lượng phần tử sử dụng khác nhau đáng kể về tần suất (ví dụ: 95% yêu cầu được phân phối trên 100 khóa hàng đầu trong số 1 triệu), Splay Tree có thể phù hợp hơn để lưu trữ bộ đệm. Cây này được cân bằng dựa trên tần suất sử dụng của mỗi nút.

Ý tưởng chính của Splay Tree trái ngược với LRU - các phần tử được sử dụng nhiều nhất nằm gần gốc, khiến cấu trúc dữ liệu này trở nên lý tưởng làm cấu trúc chính cho bộ đệm.

Việc trục xuất có thể được giải quyết theo hai cách: bằng cách sử dụng danh sách liên kết được kết nối với cấu trúc chính hoặc bằng cách sửa đổi Cây Splay thành Cây nhị phân có luồng. Các nút trong Cây Splay đã được sắp xếp theo tần suất sử dụng. Mặc dù việc phân luồng bổ sung cho lá cây có thể yêu cầu nhiều thời gian CPU hơn, do đó, nó có thể tiết kiệm bộ nhớ.

Để hiểu rõ hơn về khả năng tăng tốc của dữ liệu được sử dụng gần đây trong bộ nhớ, bạn có thể khám phá ví dụ về di chuyển VM trực tiếp trên liên kết này.

Cải thiện tốc độ quét của danh sách liên kết

Như đã đề cập trước đây, danh sách liên kết cung cấp giải pháp nhanh nhất để ghi dữ liệu. Tốc độ quét của chúng tốt nhưng chậm hơn tốc độ quét trong mảng.

Tôi đã mô tả vấn đề này là vị trí dữ liệu trong bài viết trước. Tuy nhiên, vì tương tự như cây nhị phân, danh sách liên kết có tiềm năng cải tiến. Việc hủy danh sách liên kết cho phép bạn lưu trữ nhiều dữ liệu hơn trong mỗi nút của danh sách. Do đó, nó tiết kiệm bộ nhớ trên nút con trỏ tiếp theo và đôi khi nó cải thiện hiệu suất, với điều kiện kích thước của phần tử phù hợp với dòng bộ đệm CPU:

Ý tưởng chính vẫn không thay đổi nhưng cách thể hiện danh sách trong bộ nhớ sẽ bị thay đổi.

Nó sẽ thay đổi theo nhiều cách. Có 2 lựa chọn bên dưới:

Những cải tiến này làm tăng hiệu suất của danh sách liên kết nhưng chúng làm tăng thêm độ phức tạp cho mã. Đối với các hoạt động trên đĩa có danh sách được liên kết, một nút không được kiểm soát có thể có nhiều phần tử hơn. Một cách dễ dàng để hiểu cách thức hoạt động của nó là tưởng tượng một danh sách các mảng được liên kết.

Trong code, chúng ta cần sửa đổi mô tả struct và từ giờ trở đi, đọc hoặc ghi từng phần tử trong mảng của cấu trúc:

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

Bỏ qua danh sách

Danh sách bỏ qua là một phương pháp cải thiện đặc tính tốc độ của các phần tử tìm kiếm trong danh sách liên kết. Loại danh sách liên kết này lưu trữ một khóa để sắp xếp danh sách liên kết và bao gồm các con trỏ bổ sung để định vị các nút hiệu quả hơn thao tác quét đơn giản.

Các nút bổ sung nâng cao tốc độ di chuyển giữa các nút trong danh sách bỏ qua. Nó hoạt động giống như một tìm kiếm nhị phân. Ngược lại, phải mất nhiều thời gian hơn để thêm các yếu tố mới. Vì vậy, danh sách bỏ qua phải có khóa. Các ứng dụng có thể thực hiện bất kỳ số cấp độ nào để cải thiện đặc tính tốc độ. Trong hầu hết các trường hợp, lựa chọn tốt hơn là có mức độ thấp hơn một chút hoặc ngang bằng với chiều cao của cây. (Xem hình trên)

Trong khi tìm kiếm, ứng dụng sẽ bắt đầu từ cấp cao nhất, đây là tuyến đường nhanh nhất. Khi phát hiện khóa gần, nó sẽ giảm xuống mức thấp hơn cho đến khi tìm thấy nút mong muốn.

Quá trình này dẫn đến độ phức tạp về thời gian là O(log(n)). Ví dụ: sử dụng 4 cấp độ cho danh sách bỏ qua có 16 nút, 20 cấp độ cho 1 triệu nút và 32 cấp độ cho 4 tỷ nút sẽ mang lại độ phức tạp về thời gian tương tự như cây RB.

Danh sách bỏ qua sẽ tốt hơn vì những lý do sau:

• Đơn giản thực hiện. Mặc dù có những đặc điểm tương tự như cây RB nhưng nó dễ thực hiện và bảo trì hơn nhiều.

• Hiệu quả cao trong việc thêm các nút mới vào cuối danh sách bỏ qua.

• Việc tạo danh sách bỏ qua theo luồng an toàn dễ dàng hơn so với tạo cây.

Hãy cùng khám phá việc thực hiện khái niệm này!

Nút cấu trúc:

 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;

Chức năng tạo nú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; }

Trong quá trình chèn, nhiệm vụ bao gồm việc phát hiện vị trí chính xác để lưu trữ nút và xác định số cấp độ để kết nối với nút này. Việc sử dụng hàm ngẫu nhiên để xác định cấp độ giúp đơn giản hóa quy trình cho mỗi nút mới. Trung bình, chức năng này phân bổ cấp độ thứ hai trong 50% trường hợp, cấp độ thứ ba trong 25% trường hợp, v.v. Phương pháp này giảm thiểu thời gian truy cập vào bộ nhớ để cân bằng lại các phần tử.

 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; } } }

Chức năng tìm kiếm các nút:

 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; }

Hàm điểm chuẩn để kiểm tra hiệu suất của danh sách liên kết, danh sách bỏ qua và cây RB. Các giá trị, được sử dụng làm khóa, được đặt là lũy thừa của hai. Giá trị cho mục đích thử nghiệm không quan trọng.

 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);

Kết quả kiểm tra cấu trúc dữ liệu này trên các khóa phát triển tuần tự:

Đây là thời điểm tốt nhất để chèn (nếu bạn không tính đến danh sách liên kết đơn giản) và là phương pháp khá nhanh để tìm kiếm các phần tử.

Kết quả kiểm tra cấu trúc dữ liệu này trên các khóa giảm dần tuần tự:

Điều này rất dễ hiểu: việc triển khai danh sách bỏ qua này chỉ có một con trỏ head tới phần tử đầu tiên. Việc thêm các nút vào cuối phức tạp hơn. Để thay đổi cách tiếp cận này, chúng ta có thể thêm con trỏ thứ hai (vào phần đuôi) hoặc đảo ngược danh sách bỏ qua (phần đầu sẽ trỏ đến các giá trị lớn). Điều đó có nghĩa là danh sách bỏ qua là cấu trúc dữ liệu hiệu quả cho dữ liệu nhật ký, chẳng hạn như luồng Kafka. Trong trường hợp đó, nó có thể nhanh gấp đôi cây RB và dễ thực hiện hơn.

Skip List làm giảm tốc độ chèn của Linked list, tuy nhiên, đối với dữ liệu tuần tự, nó vẫn nhanh hơn các cấu trúc dữ liệu khác có thời gian truy cập logarit vào các phần tử, đặc biệt khi các khóa phát triển tuần tự. Tuy nhiên, bất kỳ sự tăng trưởng tuần tự nào của các phím đều làm phức tạp việc chèn vào cây vì nó gây ra nhiều phép quay để duy trì sự cân bằng của cây.

Nó chỉ hoạt động hiệu quả khi giá trị tăng (hoặc giảm) trong suốt chuỗi. Chẳng hạn, nếu chúng ta chọn ngẫu nhiên các khóa, kết quả sẽ khác:

Như đã thấy, sự phân bổ giữa các giá trị không tác động đáng kể đến đặc tính tốc độ của cây RB, nhưng nó ảnh hưởng đáng kể đến hiệu suất của danh sách bỏ qua.

Kết luận

Ngày nay, các ứng dụng của chúng ta có thể sắp xếp dữ liệu trong bộ nhớ hoặc đĩa theo nhiều cách khác nhau. Bản đồ và danh sách đóng vai trò quan trọng trong việc sắp xếp dữ liệu theo các thứ tự khác nhau cho các mục đích đa dạng. Những cấu trúc này đảm bảo đủ hiệu suất, hiệu quả tài nguyên và năng lực.

Đôi khi nó không đủ với nhu cầu của chúng ta và ứng dụng phải được thay đổi ở những phần quan trọng để tối ưu hơn. Một số trường hợp có thể được hưởng lợi từ việc sử dụng các cấu trúc dữ liệu phù hợp hơn, chẳng hạn như cây để khớp không chính xác hoặc tiết kiệm bộ nhớ. Khác - từ những cải tiến của thuật toán, chẳng hạn như sử dụng các phương pháp không đồng bộ để cải thiện hiệu suất của từng luồng.

Khi tất cả các tùy chọn khác đã hết ở đó, cách tiếp cận còn lại là điều chỉnh cấu trúc dữ liệu và điều chỉnh phương pháp sử dụng. Có những ví dụ về một số thay đổi trong cấu trúc dữ liệu để làm cho chúng phù hợp hơn với một nhiệm vụ cụ thể trong thực tế.

Mặc dù danh sách liên kết chủ yếu là cấu trúc dữ liệu chỉ ghi và quét tuần tự, nhưng nó có thể được tối ưu hóa nhiều hơn cây RB và vẫn hoạt động hiệu quả trong trường hợp chỉ ghi. Tuy nhiên, việc tăng cường các đặc điểm cụ thể có thể tác động đến những đặc điểm khác. Vì vậy, cách tốt nhất là ưu tiên những gì quan trọng và loại bỏ những gì không.