जंप टेबल स्विच केस प्रश्न

Question

मैं कूद तालिकाओं और स्विच केस स्टेटमेंट के बीच इसके संबंधों के बारे में कुछ चीजों को समझने की कोशिश कर रहा हूं।

मुझे बताया गया था कि एक कूद तालिका एक ओ (1) संरचना है जो संकलक उत्पन्न करता है जो आपके द्वारा प्राप्त किए जा सकने वाले मूल्यों के बारे में अनिवार्य रूप से मूल्यों की तलाश करता है। हालांकि कुछ मामलों में एक हैशटेबल/शब्दकोश तेज हो सकता है। मुझे यह भी बताया गया कि यह केवल तभी काम करेगा यदि स्विच केस में ordered डेटा मान हैं।

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

Answer 1

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

ए स्विच स्टेटमेंट सी/सी ++ में कूद तालिकाओं को लिखना है। इस आम मामले में कार्यान्वयन को आसान और तेज़ बनाने के लिए केवल एक सीमित रूप प्रदान किया जाता है (केवल अभिन्न प्रकारों पर स्विच कर सकता है)। (कूदने वाले तालिकाओं को प्रभावी ढंग से कैसे कार्यान्वित किया गया है, सामान्य मामले की तुलना में अभिन्न प्रकारों के लिए बहुत अधिक अध्ययन किया गया है।) एक क्लासिक उदाहरण Duff's Device है।

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

---

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

कंपाइलर प्रत्येक स्विच स्टेटमेंट के लिए लुकअप विधि चुनने के लिए स्वतंत्र है, और कोई गारंटी नहीं है कि आपको एक विशेष कार्यान्वयन मिलेगा; हालांकि, कंपाइलर विकल्प जैसे ऑप्टिमाइज़-फॉर-स्पीड और ऑप्टिमाइज़-टू-साइज को ध्यान में रखा जाना चाहिए।

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

Answer 2

स्विच स्टेटमेंट के लिए संकलन मामलों के आधार पर कई रूप ले सकता है। यदि मामले एक साथ निकट हैं, तो यह कोई ब्रेनर नहीं है: एक कूद तालिका का उपयोग करें। यदि मामले बहुत दूर हैं, तो अगर (केस == मान) का उपयोग करें या मानचित्र का उपयोग करें। या एक कंपाइलर संयोजन का उपयोग कर सकता है: जंप टेबल के चेक द्वारा निर्धारित कूद तालिकाओं के द्वीप निर्धारित करते हैं।

Answer 3

मान लीजिए आप प्रक्रियाओं की एक सरणी था:

char c; 
switch(c) { 
    case 'a': fa();break; 
    case 'b': fb();break; 
    ... 
    case 'z': fz();break;  
    default: exit(-1); 
} 

आदर्श रूप में इस के साथ प्रतिस्थापित किया जाएगा:

void fa() { 
printf("a\n"); 
} 

... 

void fz() { 
printf("it's z!\n"); 
} 



typedef void (*F)(); 
F table[26]={fa,fb,...,fz}; 

आप उपयोगकर्ता से इनपुट की (AZ से) एक चरित्र को स्वीकार करने और एफसी चलाने मान लीजिए कुछ की तरह:

if (c<'a' || c>'z') exit(-1); 
else (*table[c-'a'])(); 

स्वाभाविक रूप से, आप तालिका तो सीमा की जांच wo बड़ा बना सकता है जरूरी नहीं है

कंपाइलर मनमाने ढंग से कोड के लिए ऐसा करेगा, आवश्यक रूप से केवल कॉल कॉल नहीं करेगा, और यह पता लगाने के लिए पते को संग्रहीत करके (अनिवार्य रूप से, एक गोटो) करेगा। सी सीधे किसी भी तरह के गणना वाले गोटो (किसी तालिका में अनुक्रमणित या अन्यथा) का समर्थन नहीं करता है, लेकिन इसके लिए सीपीयू निर्देश बहुत सरल हैं।

Answer 4

एक कूद तालिका मूल रूप से स्विच स्टेटमेंट में विभिन्न मामलों को संभालने के लिए कोड के टुकड़ों के लिए पॉइंटर्स की एक सरणी है। जब आपके मामले घने होते हैं तो यह उत्पन्न होने की संभावना अधिक होती है (यानी आपके पास किसी सीमा में प्रत्येक संभावित मूल्य का मामला है)।

void case1() { printf("case 1"); } 
void case2() { printf("case 2"); } 
void case3() { printf("case 3"); } 

typedef void (*pfunc)(void); 

pfunc functions[3] = {case1, case2, case3}; 

if ((unsigned)i<3)  
    functions[i](); 

यह है हे (के) जटिलता:

switch (i) { 
    case 1: printf("case 1"); break; 
    case 2: printf("case 2"); break; 
    case 3: printf("case 3"); break; 
} 

यह कोड मोटे तौर पर कुछ इस तरह के बराबर उत्पन्न कर सकता है: उदाहरण के लिए, की तरह एक बयान दिया। एक सामान्य हैश तालिका में लगभग ओ (के) अपेक्षित जटिलता है, हालांकि सबसे खराब मामला आमतौर पर ओ (एन) होता है। कूदने वाली मेज आमतौर पर तेज होगी, लेकिन आमतौर पर इसका उपयोग केवल तभी किया जाएगा जब तालिका काफी घनी हो, जबकि एक हैश टेबल/डिक्शनरी काफी अच्छी तरह से काम करती है जब भी मामला काफी अस्पष्ट होगा।

Answer 5

एक कूद तालिका सरल समारोह संकेत की एक सरणी है, तो आप ऐसा तरह मोटे तौर पर एक कूद तालिका चित्र कर सकते हैं:

int (*functions[10])(); /* Array of 10 Function Pointers */

मेरी समझ से, यह इतना तरह के मामले बयान के साथ प्रयोग किया जाता है: प्रत्येक शर्त मामले _,, इस सरणी में एक सूचकांक हो जाएगा उदाहरण के लिए इतना:

switch(a) { 
    case 1: // (*functions[1])() // Call function containing actions in case of 1 
     ... 
    case 2: // (*functions[2])() // Call function containing actions in case of 2 
     ... 

प्रत्येक मामले के लिए, बस कार्यों [एक] बनने के लिए बदल देती है। इसका मतलब है कि कार्यों तक पहुंच [9] केवल कार्यों तक पहुंचने जितनी जल्दी है [1]। आपको उल्लिखित ओ (1) समय देना।

जाहिर है, यदि आपके पास केस 1 है, और मामला 4 9 77 है, तो यह एक अच्छी विधि नहीं होगी, और आपके द्वारा वर्णित हैश टेबल/डिक्शनरी विधियां खेल में आ सकती हैं।

Answer 6

आगे Jerry's answer पर विस्तार करने के लिए और अन्य लोगों के

को देखते हुए:

int f1() {return 6;} 
int f2() {return 1+f3();} 
int f3() {return 8;} 

संकलक एक कूद तालिका सूचकांक {f1, f2, f3} लिए इस्तेमाल कर सकते हैं:

int x=1; 
switch (i) { 
    case 1: x=6; break; 
    case 2: x++; 
    // Fall through 
    case 3: x+=7; break; 
} 

आप निम्नलिखित की तरह कुछ हो सकता था

कंपाइलर कर सकता है इनलाइन करने जब f1, f2, f36,9,8

के लिए सीधे x की स्थापना लेकिन अगर आप कार्यों लिखा था, और अपने खुद के कूद तालिका लुढ़का, f1,f2,f3 कहीं भी हो सकता है, लेकिन संकलक उन्हें switch ज्यादा बेहतर बनाने के करीब डाल करने के लिए पता चल जाएगा होने तालिका बनाने कोड इलाके से आप कर सकते हैं।

ध्यान दें कि कई मामलों में संकलक अगर i सीमा में है एक गार्ड की जाँच करने के लिए (या default को संभालने के लिए) उत्पन्न होगा और यदि आप यकीन है कि यह हमेशा मामलों में से एक है कर रहे हैं, तो आप छोड़ सकते हैं कि

if (i==1) x=f1(); 
else if (i==2) x=f2(); 
else if (i==3) x=f3(); 

या यह हो सकता है:

दिलचस्प बात यह है कि मामलों की एक छोटी संख्या के तहत, और अलग संकलक झंडे के नीचे (संकलक निर्भर) के लिए switch एक मेज का प्रयोग करेंगे नहीं, लेकिन सिर्फ भारतीय विदेश सेवा करना होगा, इसी तरह करने के लिए है इसे अनुकूलित करें (जहां सरल परीक्षण एक निर्देश हैं):

x=(i==1) ? f1() 
: (i==2) ? f2() 
: (i==3) ? f3() 
: x; 

सबसे अच्छा सलाह क्या संकलक अपने वास्तुकला पर अपने कोड के लिए क्या किया देखने के लिए उत्पन्न विधानसभा को देखने के लिए, जी ++ पर लिनक्स/इंटेल, निम्नलिखित की तरह कुछ उत्पन्न होगा अगर वहाँ एक कूद तालिका

है

ध्यान दें कि छोटे छेद कूद तालिका में होगा default

करने के लिए ( टिप्पणी मैं 5 case बयान करने के लिए जाने के लिए कूद तालिका के लिए मजबूर करने के लिए किया था, यह भारतीय विदेश सेवा case बयान की संख्या नीचे प्रयोग किया जाता)

int foo(int i) 
{ 
    int x=1; 
    switch (i) { 
     case 1: x=6; break; 
     case 2: x++; 
     // Fall through 
     case 3: x+=7; break; 
     case 4: x+=2; break; 
     case 5: x+=9; break; 
    } 
    return x; 
} 

निम्नलिखित विधानसभा कोड उत्पन्न होगा (// टिप्पणी मेरा हैं):

 cmp  edi, 5      //make sure it is not over 5 
     ja  .L2      //jump to default case 
     mov  edi, edi 
     jmp  [QWORD PTR .L4[0+rdi*8]] // use the jump table at label L4: 
.L4: 
     .quad .L2      // if i=0, set x=1 (default) 
     .quad .L9      // f1() see below 
     .quad .L10      // f2() see below 
     .quad .L6      // f3() see below 
     .quad .L7      // f4() see below 
     .quad .L8      // f5() see below 
.L10: 
     mov  eax, 9      // x=9 
     ret 
.L9: 
     mov  eax, 6      // x=6 
     ret 
.L8: 
     mov  eax, 10     // x=10 
     ret 
.L6: 
     mov  eax, 8      // x=8 
     ret 
.L7: 
     mov  eax, 3      // x=3 
     ret 
.L2: 
     mov  eax, 1      // default, x was 1, noop is: x=1 
     ret