संवर्धित लिंक्ड सूचियाँ: एक आवश्यक मार्गदर्शिका

लिंक्ड सूची कैसे काम करती है?

लिंक्ड लिस्ट एक डेटा संरचना है जहाँ प्रत्येक डेटा के फ़ील्ड ऑफ़सेट के बजाय पॉइंटर्स द्वारा जुड़े होते हैं। इसमें एक मुख्य तत्व होता है जो पहले और अंतिम तत्वों को संग्रहीत करता है, जिन्हें नोड तत्व कहा जाता है, जिसमें सभी आवश्यक उपयोगकर्ता फ़ील्ड (जैसे फ़ोन, स्वामी, कंपनी, आदि) और अगले नोड के लिए एक पॉइंटर होता है। अंतिम तत्व NULL फ़ील्ड से जुड़ा होता है जो सूची के अंत को इंगित करता है।

जब लिंक्ड सूची में कोई नया तत्व जोड़ा जाता है, तो मुख्य नोड को "टेल" पॉइंटर को नए अंत-नोड में अपडेट करना होगा, और पिछले NULL-पॉइंटर को नए टेल में अपडेट करना होगा।

यह डेटा संरचना पूरे सरणी का आकार बदले बिना नए डेटा की कुशल रिकॉर्डिंग की अनुमति देती है। यह केवल-लेखन डेटा संग्रहीत करने के लिए एक प्रभावी तरीका है, और इसके लिए पहले से तत्वों की मात्रा जानने की आवश्यकता नहीं होती है। यह एक सरल डेटा संरचना है, और मेमोरी में, यह इस तरह दिखता है:

निष्कासन कुंजी के लिए लिंक की गई सूची

पिछले लेख में, हमने प्रत्येक आइटम को हटाने के बाद पेड़ को छोड़े बिना पेड़ को स्कैन करने के लिए बफर की आवश्यकता पर चर्चा की। GC वाली भाषाओं में, यह कोई समस्या नहीं है। हालाँकि, जब एप्लिकेशन कोड मेमोरी का प्रबंधन करता है, तो पुराने तत्वों वाली लिंक्ड सूची पर आधारित बफर एक समाधान हो सकता है।

लिंक्ड सूची तत्वों को तेजी से जोड़ने की अनुमति देती है। हालाँकि, लिंक्ड सूची में कुछ भी खोजने के लिए अनुक्रमिक स्कैनिंग की आवश्यकता होती है, जिससे यह त्वरित कुंजी पुनर्प्राप्ति के लिए अनुपयुक्त हो जाती है। इस प्रकार, यह डेटा लॉग करने, अस्थायी बफ़र्स बनाने और हेड नोड्स से अनुक्रमिक रीड बनाने के लिए डेटा को व्यवस्थित करने के लिए एक कुशल समाधान है।

प्रीएमप्ट करने के लिए तत्वों को ढूँढना ऐसे कार्य का एक उदाहरण है। प्रीएमप्शन का उपयोग अक्सर विभिन्न कैश कार्यान्वयनों में किया जाता है। कैश में वह डेटा होता है जिसे बड़ी विलंबता वाले अन्य मेमोरी स्रोतों से पुनर्स्थापित किया जा सकता है। कैश को आमतौर पर मुख्य मेमोरी में संग्रहीत किया जाता है। मुख्य मेमोरी सीमित है, और प्रभावी उपयोग के लिए, डेटा का केवल एक छोटा सा स्नैपशॉट मुख्य मेमोरी में संग्रहीत किया जा सकता है।

इसके लिए हमें मेमोरी का अधिक बुद्धिमानी से उपयोग करने की आवश्यकता है, कम बार अनुरोध किए जाने वाले डेटा के लिए मेमोरी के उपयोग से बचना होगा तथा यदि बहुत कम बार अनुरोध किया जाने लगे तो ऐसे डेटा को हटा देना होगा।

कैश में फ़ील्ड को निकालने के लिए एक प्रभावी तरीका सबसे कम हाल ही में इस्तेमाल किया गया (LRU) तरीका है। नीचे 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); }

एक टिप्पणी: जब उपयोग करने वाले तत्वों की संख्या आवृत्ति में काफी भिन्न होती है (उदाहरण के लिए, 1 मिलियन में से शीर्ष 100 कुंजियों पर वितरित 95% अनुरोध), तो स्प्ले ट्री कैश को संग्रहीत करने के लिए अधिक उपयुक्त हो सकता है। यह ट्री प्रत्येक नोड उपयोग की आवृत्ति के आधार पर संतुलित है।

स्प्ले ट्री का मुख्य विचार LRU के विपरीत है - सबसे अधिक उपयोग किए जाने वाले तत्व रूट के पास स्थित होते हैं, जिससे यह डेटा संरचना कैश के लिए प्राथमिक संरचना के रूप में आदर्श बन जाती है।

निष्कासन को दो तरीकों से हल किया जा सकता है: मुख्य संरचना के साथ जुड़े लिंक्ड सूची का उपयोग करके, या स्प्ले ट्री को थ्रेडेड बाइनरी ट्री में संशोधित करके। स्प्ले ट्री में नोड्स पहले से ही उपयोग की आवृत्ति के अनुसार क्रमबद्ध हैं। हालाँकि ट्री लीव्स के अतिरिक्त थ्रेडिंग के लिए अधिक CPU समय की आवश्यकता हो सकती है, इसलिए, यह मेमोरी बचा सकता है।

मेमोरी में हाल ही में उपयोग किए गए डेटा के त्वरण को बेहतर ढंग से समझने के लिए, आप इस लिंक पर लाइव वीएम माइग्रेशन का एक उदाहरण देख सकते हैं।

लिंक्ड सूची की स्कैन गति में सुधार करें

जैसा कि पहले बताया गया था, लिंक्ड लिस्ट डेटा लिखने के लिए सबसे तेज़ समाधान प्रदान करती हैं। उनकी स्कैनिंग गति अच्छी है, लेकिन यह सरणी में स्कैन गति से धीमी है।

मैंने पिछले लेख में इस समस्या को डेटा लोकलिटी के रूप में वर्णित किया था। हालाँकि, बाइनरी ट्री के समान होने के कारण, लिंक्ड लिस्ट में सुधार की संभावना है। लिंक्ड लिस्ट को अनरोल करने से आप लिस्ट के प्रत्येक नोड में अधिक डेटा स्टोर कर सकते हैं। इस प्रकार, यह अगले पॉइंटर नोड पर मेमोरी बचाता है, और कभी-कभी यह प्रदर्शन में सुधार करता है, इस शर्त पर कि तत्व का आकार CPU कैश लाइन के साथ फिट बैठता है:

मुख्य विचार अपरिवर्तित रहेगा, लेकिन मेमोरी में सूची का प्रतिनिधित्व बदल जाएगा।

यह कई मायनों में बदलेगा। नीचे 2 विकल्प दिए गए हैं:

ये सुधार लिंक्ड लिस्ट के प्रदर्शन को बढ़ाते हैं, लेकिन वे कोड में कुछ जटिलता जोड़ते हैं। लिंक्ड लिस्ट के साथ डिस्क-ऑपरेशन के लिए, एक अनरोल किए गए नोड में अधिक तत्व हो सकते हैं। यह समझने का एक आसान तरीका है कि यह कैसे काम करता है, सरणियों की एक लिंक्ड सूची की कल्पना करना।

कोड में, हमें स्ट्रक्चर विवरण को संशोधित करने की आवश्यकता है, और अब से, संरचना की सरणी में प्रत्येक तत्व को पढ़ना या लिखना होगा:

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

सूची छोड़ें

स्किप लिस्ट एक लिंक्ड लिस्ट में खोज तत्वों की गति विशेषताओं को बेहतर बनाने की एक विधि है। इस प्रकार की लिंक्ड लिस्ट लिंक्ड लिस्ट को ऑर्डर करने के लिए एक कुंजी संग्रहीत करती है और इसमें नोड्स को एक साधारण स्कैनिंग ऑपरेशन की तुलना में अधिक कुशलता से खोजने के लिए अतिरिक्त पॉइंटर्स शामिल होते हैं।

अतिरिक्त नोड्स स्किप सूची में नोड्स के बीच ट्रैवर्सिंग की गति को बढ़ाते हैं। यह बाइनरी सर्च की तरह काम करता है। इसके विपरीत, नए तत्वों को जोड़ने में अधिक समय लगता है। इसलिए, स्किप सूचियों में एक कुंजी होनी चाहिए। गति विशेषताओं को बेहतर बनाने के लिए एप्लिकेशन किसी भी संख्या में स्तर बना सकते हैं। ज़्यादातर मामलों में, पेड़ में ऊंचाई के हिसाब से थोड़ा कम या लगभग समान स्तर रखना बेहतर विकल्प है। (ऊपर चित्र देखें)

खोज करते समय, एक एप्लीकेशन सबसे ऊंचे स्तर से शुरू होता है, जो सबसे तेज़ मार्ग है। निकटतम कुंजी का पता लगाने पर यह वांछित नोड मिलने तक निचले स्तर पर उतरता है।

इस प्रक्रिया के परिणामस्वरूप O(log(n)) की समय जटिलता प्राप्त होती है। उदाहरण के लिए, 16 नोड्स वाली स्किप सूची के लिए 4 स्तरों, 1 मिलियन नोड्स के लिए 20 स्तरों और 4 बिलियन नोड्स के लिए 32 स्तरों का उपयोग करने से 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 ट्री के प्रदर्शन का परीक्षण करने के लिए एक बेंचमार्क फ़ंक्शन। कुंजी के रूप में उपयोग किए जाने वाले मान, दो की घात के रूप में सेट किए जाते हैं। परीक्षण उद्देश्यों के लिए मान मायने नहीं रखता।

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

क्रमिक रूप से बढ़ती कुंजियों पर इस डेटा संरचना के परीक्षण के परिणाम:

यह सम्मिलित करने का सबसे अच्छा समय है (यदि आप सरल लिंक्ड सूची को ध्यान में नहीं रखते हैं) और तत्वों को खोजने का एक बहुत तेज़ तरीका है।

क्रमिक रूप से घटती कुंजियों पर इस डेटा संरचना के परीक्षण के परिणाम:

इसे समझना आसान है: स्किप लिस्ट के इस कार्यान्वयन में केवल पहले तत्व के लिए एक हेड पॉइंटर है। अंत में नोड्स जोड़ना अधिक जटिल है। इस दृष्टिकोण को बदलने के लिए, हम दूसरा पॉइंटर (टेल में) या रिवर्स स्किप लिस्ट (हेड बड़े मानों की ओर इशारा करेगा) जोड़ सकते हैं। इसका मतलब है कि एक स्किप लिस्ट काफ्का स्ट्रीम जैसे लॉग डेटा के लिए एक प्रभावी डेटा संरचना है। उस स्थिति में, यह आरबी ट्री से कम से कम दोगुना तेज़ हो सकता है और इसे लागू करना आसान हो सकता है।

स्किप लिस्ट लिंक्ड लिस्ट की प्रविष्टि गति को कम करती है, हालाँकि, अनुक्रमिक डेटा के लिए, यह तत्वों तक लॉगरिदम पहुँच समय के साथ अन्य डेटा संरचनाओं की तुलना में तेज़ रहता है, खासकर जब कुंजियाँ क्रमिक रूप से बढ़ती हैं। फिर भी, कुंजियों की कोई भी क्रमिक वृद्धि पेड़ में प्रविष्टि को जटिल बनाती है क्योंकि यह पेड़ के संतुलन को बनाए रखने के लिए बहुत सारे घुमावों का कारण बनती है।

यह तभी प्रभावी ढंग से काम करता है जब पूरे अनुक्रम में मान बढ़ रहा हो (या घट रहा हो)। उदाहरण के लिए, यदि हम कुंजियों को यादृच्छिक बनाते हैं, तो परिणाम अलग होंगे:

जैसा कि देखा गया है, मानों में वितरण RB वृक्ष की गति विशेषता को महत्वपूर्ण रूप से प्रभावित नहीं करता है, लेकिन यह स्किप सूची के प्रदर्शन को उल्लेखनीय रूप से प्रभावित करता है।

निष्कर्ष

आज, हमारे अनुप्रयोग मेमोरी या डिस्क में डेटा को अलग-अलग तरीकों से व्यवस्थित कर सकते हैं। मानचित्र और सूचियाँ विभिन्न उद्देश्यों के लिए डेटा को अलग-अलग क्रम में व्यवस्थित करने में महत्वपूर्ण भूमिका निभाते हैं। ये संरचनाएँ पर्याप्त प्रदर्शन, संसाधन दक्षता और क्षमता सुनिश्चित करती हैं।

कभी-कभी, यह हमारी ज़रूरतों के लिए पर्याप्त नहीं होता है, और एप्लिकेशन को अधिक इष्टतम बनाने के लिए महत्वपूर्ण भागों में बदलाव करना पड़ता है। कुछ मामलों में अधिक उपयुक्त डेटा संरचनाओं का उपयोग करने से लाभ हो सकता है, जैसे कि अनिश्चित मिलान या मेमोरी अर्थव्यवस्था के लिए पेड़। अन्य - एल्गोरिदम के सुधार से, जैसे कि व्यक्तिगत थ्रेड प्रदर्शन को बेहतर बनाने के लिए एसिंक्रोनस विधियों का उपयोग करना।

जब सभी अन्य विकल्प समाप्त हो जाते हैं, तो शेष दृष्टिकोण डेटा संरचना को अनुकूलित करना और उपयोग की पद्धति को समायोजित करना है। व्यावहारिक रूप से विशिष्ट कार्य के लिए इन्हें अधिक उपयुक्त बनाने के लिए डेटा संरचना में कुछ बदलावों के उदाहरण हैं।

जबकि लिंक्ड लिस्ट मुख्य रूप से केवल लिखने और अनुक्रम-स्कैनिंग डेटा संरचना है, इसे आरबी ट्री से अधिक अनुकूलित किया जा सकता है और केवल लिखने के मामले में कुशल बना रह सकता है। हालांकि, विशेष विशेषताओं का बढ़ावा दूसरों को प्रभावित कर सकता है। इसलिए, सबसे अच्छा तरीका यह है कि जो महत्वपूर्ण है उसे प्राथमिकता दी जाए और जो महत्वपूर्ण नहीं है उसे त्याग दिया जाए।