C Academy · पाठ

Resizing और Load Factor

Performance tuning

पाठ 4, कुल 4 में से13 चरण

Resizing और Load Factor, CoddyKit पर C Academy का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह C Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। C Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

लोड फैक्टर क्या है

लोड फैक्टर संग्रहित प्रविष्टियों और बकेटों का अनुपात होता है: alpha = size / capacity। यह मापता है कि तालिका कितनी भरी हुई है और सीधे उसके प्रदर्शन को प्रभावित करता है।

लोड फैक्टर क्यों महत्वपूर्ण है

जैसे-जैसे लोड फैक्टर बढ़ता है, बकेटों में लंबी शृंखलाएँ होती हैं (या जाँचें समूहीकृत होती हैं), इसलिए संक्रियाएँ धीमी हो जाती हैं।

कम alpha: तेज़, लेकिन मेमोरी की बर्बादी
अधिक alpha: कम जगह, लेकिन धीमा

शृंखलाबद्धन के लिए 0.75 का लक्ष्य सामान्य है।

लोड फैक्टर की गणना

इसे फ्लोटिंग-पॉइंट अनुपात के रूप में गणना करें, ताकि आप इसकी तुलना किसी सीमा से कर सकें।

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

आकार कब बदलें

प्रत्येक प्रविष्टि के बाद जाँचें कि लोड फैक्टर सीमा से अधिक तो नहीं हो गया। यदि ऐसा हो, तो तालिका को बढ़ाएँ (आमतौर पर क्षमता को दोगुना करके) और फिर से हैश करें।

#include <stdio.h>

int should_grow(unsigned size, unsigned cap) {
    return (double)size / cap > 0.75;
}

int main(void) {
    printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
    printf("%d\n", should_grow(10, 16)); /* 0.625  -> 0 */
    return 0;
}

फिर से हैश करना समझें

आप बकेटों की सीधे प्रतिलिपि नहीं बना सकते, क्योंकि प्रत्येक कुंजी का सूचकांक क्षमता पर निर्भर करता है। फिर से हैश करना नई क्षमता के आधार पर प्रत्येक कुंजी के बकेट की दोबारा गणना करके उसे फिर से प्रविष्ट करता है।

आकार बदलने वाला फ़ंक्शन

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

#include <stdio.h>

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    const char *key = "session";
    unsigned old_cap = 8, new_cap = 16;
    printf("old slot = %lu\n", djb2(key) % old_cap);
    printf("new slot = %lu\n", djb2(key) % new_cap);
    return 0;
}

दोबारा आवंटित किए बिना नोड स्थानांतरित करना

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; struct Node *next; } Node;
unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

int main(void) {
    Node *old[2] = {0};
    Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
    Node *new_b[4] = {0};
    /* move node a */
    unsigned i = djb2(a->key) % 4;
    a->next = new_b[i]; new_b[i] = a;
    printf("moved to slot %u\n", i);
    return 0;
}

वृद्धि की रणनीति

क्षमता को दोगुना करने से प्रविष्टि की परिशोधित लागत O(1) रहती है: यद्यपि आकार बदलना O(n) होता है, यह इतना कम होता है कि प्रत्येक प्रविष्टि की औसत लागत स्थिर रहती है।

दो की घातें आपको तेज़ AND मास्क का उपयोग करने देती हैं।

#include <stdio.h>

int main(void) {
    unsigned cap = 8;
    for (int i = 0; i < 4; i++) {
        printf("capacity = %u\n", cap);
        cap *= 2;
    }
    return 0;
}

आकार घटाना

जब बहुत सारे विलोपन के बाद लोड फैक्टर बहुत कम हो जाए (उदाहरण के लिए 0.1 से नीचे), तब वैकल्पिक रूप से आकार घटाएँ। आकार घटाने से मेमोरी वापस मिलती है, लेकिन फिर से हैश करने की लागत जुड़ती है, इसलिए बार-बार आकार बदलने से बचने के लिए इसे सावधानी से करें।

खुला एड्रेसिंग और लोड फैक्टर

खुले एड्रेसिंग वाली तालिकाएँ लोड फैक्टर के प्रति बहुत अधिक संवेदनशील होती हैं। जैसे-जैसे alpha 1 के पास पहुँचता है, प्रदर्शन पूरी तरह गिर जाता है। इसलिए इनका आकार आमतौर पर 0.5 से 0.7 पर बदला जाता है, जो शृंखलाबद्धन के 0.75 से कम है।

परिशोधित लागत का प्रदर्शन

ऐसी प्रविष्टियों का अनुकरण करें जो 0.75 पर क्षमता को दोगुना करती हैं और कुल कार्य गिनें, ताकि दिखाई दे कि औसत लागत कम रहती है।

#include <stdio.h>

int main(void) {
    unsigned cap = 4, size = 0;
    long work = 0;
    for (int i = 0; i < 100; i++) {
        size++; work++; /* the insert */
        if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
    }
    printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
    return 0;
}

त्वरित जाँच

आकार बदलने संबंधी अपनी समझ की जाँच करें।

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावृत्ति

आपने हैश तालिका के प्रदर्शन को बेहतर ढंग से समायोजित करना सीखा।

लोड फैक्टर = आकार / क्षमता
जब यह सीमा से अधिक हो जाए, तब आकार बदलें (शृंखलाबद्धन के लिए लगभग 0.75)
फिर से हैश करें, क्योंकि सूचकांक क्षमता पर निर्भर करते हैं
दोगुनी क्षमता से परिशोधित O(1) प्रविष्टियाँ मिलती हैं

शुरुआत निःशुल्क

एआई शिक्षक के साथ C सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 39
पाठ: 144

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “Resizing और Load Factor” पाठ निःशुल्क है?

हाँ—“Resizing और Load Factor” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और C Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। C Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“Resizing और Load Factor” में मैं क्या सीखूँगा?

Performance tuning आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ C Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या C Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर C Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।

“Resizing और Load Factor” पाठ पूरा करने में कितना समय लगता है?

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

क्या मैं इस C Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर C Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← C Academy पर वापस जाएँ