c++ programming القفز الجدول التبديل حالة السؤال



switch case in c (6)

تجميع لبيان التبديل يمكن أن تتخذ أشكالا عديدة، اعتمادا على الحالات. إذا كانت الحالات قريبة من بعضها البعض، فإنه ليس من العقل: استخدام طاولة القفز. إذا كانت الحالات متباعدة، استخدم إذا (حالة == قيمة) أو استخدام الخريطة. أو مترجم يمكن استخدام مزيج: الجزر من جداول القفز التي تحددها إذا الشيكات من الجدول القفزة نطاقات.

https://src-bin.com

أنا أحاول أن نفهم بعض الأشياء عن القفز الجداول وعلاقته بين بيان حالة التبديل.

قيل لي أن جدول القفز هو هيكل O (1) أن المترجم يولد الذي يجعل البحث من القيم أساسا عن بأسرع ما يمكن الحصول عليها. ومع ذلك في بعض الحالات قد هاشتابل / قاموس يكون أسرع. قيل لي أن هذا لن يعمل إلا إذا كانت حالة التبديل يحتوي على قيم البيانات ordered .

يمكن للشخص أن يؤكد أو ينكر هذا وشرح ما هو قفزة الجدول هو، انها أهمية وتعقيد الوقت مقابل استخدام القاموس أو هاشتابل. شكر.


Answer #1

جدول القفز بسيط مجموعة من مؤشرات وظيفة، يمكنك صورة جدول القفز تقريبا مثل ذلك:

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]. مما يتيح لك O (1) الوقت الذي ذكرته.

من الواضح، إذا كان لديك حالة 1، وحالة 4907، وهذا لن يكون وسيلة جيدة، وطرق الجدول / القاموس التجزئة التي ذكرتها قد تأتي في اللعب.


Answer #2

جدول القفز هو في الأساس مجموعة من المؤشرات إلى أجزاء من التعليمات البرمجية للتعامل مع الحالات المختلفة في بيان التبديل. فمن المرجح أن يتم إنشاؤها عندما تكون الحالات الخاصة بك كثيفة (أي لديك حالة لكل قيمة ممكنة في نطاق). على سبيل المثال، نظرا لبيان مثل:

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

يمكن أن تولد شفرة تعادل تقريبا شيئا من هذا القبيل:

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

هذا لديه O (K) التعقيد. يحتوي جدول التجزئة نموذجي أيضا تقريبا O (K) المتوقع التعقيد، على الرغم من أن أسوأ حالة عادة O (N). وعادة ما يكون جدول القفز أسرع، ولكن عادة ما يتم استخدامه فقط إذا كان الجدول سيكون كثيفا جدا، في حين أن جدول التجزئة / القاموس يعمل بشكل جيد حتى عندما تكون الحالات متفرقة جدا.


Answer #3

لمزيد من التوضيح على جواب جيري وغيرها

معطى:

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

يمكن أن يكون لديك شيء مثل ما يلي:

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

يمكن للمترجم استخدام جدول القفز إلى الفهرس {f1, f2, f3}

يمكن للمترجم القيام به إنلينينغ عند إنشاء الجدول وجود f1, f2, f3 الإعداد x مباشرة إلى 6,9,8

ولكن إذا كنت كتبت وظائف، وتوالت جدول القفز الخاصة بك، f1,f2,f3 يمكن أن يكون في أي مكان، ولكن مترجم سوف نعرف لوضعها على مقربة من switch خلق أفضل بكثير رمز محلية مما كنت يمكن.

لاحظ أنه في كثير من الحالات سوف يقوم المترجم بإنشاء حارس للتأكد مما إذا i في النطاق (أو للتعامل مع الوضع default ) وإذا كنت متأكدا من أنه دائما إحدى الحالات، فيمكنك تخطي ذلك

الشيء المثير للاهتمام هو أنه في ظل عدد قليل من الحالات، وتحت الأعلام مترجم مختلفة (مترجم تعتمد) switch لن تستخدم جدول، ولكن سوف تفعل فقط إفس، على غرار:

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

أو قد يحسن هذا (حيث الاختبارات البسيطة هي تعليمات واحدة) إلى:

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

أفضل نصيحة هي أن ننظر إلى الجمعية ولدت لمعرفة ما قام مترجم إلى التعليمات البرمجية الخاصة بك على الهندسة المعمارية الخاصة بك، ز ++ على لينكس / إنتل سوف تولد شيئا مثل ما يلي، إذا كان هناك جدول القفز

( ملاحظة كان علي أن أذهب إلى 5 تصريحات case لإجبار طاولة القفز، فإنه يستخدم إفس أدناه هذا العدد من بيانات case )

لاحظ أن الثقوب الصغيرة ستكون في جدول القفز للقيام default

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

Answer #4

لنفترض أن لديك مجموعة من الإجراءات:

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

...

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



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

لنفترض أنك تقبل حرفا (من أز) للإدخال من المستخدم وتشغيل فك:

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

من الناحية المثالية سيتم استبدال هذا مع شيء مثل:

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

وبطبيعة الحال، قد تجعل الجدول أكبر وبالتالي فإن الاختيار النطاق لن يكون ضروريا.

سوف مترجم تفعل ذلك لشفرة التعسفي، وليس بالضرورة تعمل المكالمات فقط، وسوف تفعل ذلك عن طريق تخزين عنوان للانتقال إلى (أساسا، غوتو). C لا تدعم مباشرة أي نوع من غوتو المحسوبة (الفهرسة في جدول أو خلاف ذلك)، ولكن تعليمات وحدة المعالجة المركزية لذلك بسيطة جدا.


Answer #5

جدول القفز هو بنية مجردة تستخدم لنقل السيطرة إلى موقع آخر. غوتو، ومواصلة، وكسر متشابهة، إلا أنها دائما نقل إلى موقع معين بدلا من إمكانية واحدة من العديد. على وجه الخصوص، هذا تدفق السيطرة ليست هي نفس استدعاء وظيفة. (مقالة ويكيبيديا على الجداول الفرعية ترتبط.)

بيان التبديل هو كيفية كتابة جداول القفز في C / C ++. يتم توفير شكل محدود فقط (يمكن التبديل فقط على أنواع متكاملة) لجعل عمليات التنفيذ أسهل وأسرع في هذه الحالة المشتركة. (كيفية تنفيذ جداول القفز بكفاءة وقد درست أكثر بكثير لأنواع متكاملة من الحالة العامة). مثال كلاسيكي هو جهاز داف .

ومع ذلك، غالبا ما لا تكون هناك حاجة إلى القدرة الكاملة للجدول القفز ، مثل عندما يكون لكل حالة بيان استراحة. هذه "الجداول القفز محدودة" هي نمط مختلف ، والتي تستفيد فقط من كفاءة القفز الجدول المدروسة جيدا، وتكون شائعة عندما يكون كل "عمل" مستقل عن الآخرين.

التنفيذ الفعلي للجداول القفز تأخذ أشكال مختلفة، تختلف في الغالب في كيفية القيام به مفتاح الفهرسة رسم الخرائط. أن رسم الخرائط هو حيث مصطلحات مثل "القاموس" و "الجدول التجزئة" تأتي في، وهذه التقنيات يمكن استخدامها بشكل مستقل من جدول القفز. قائلا أن بعض التعليمات البرمجية "يستخدم جدول القفز" لا يعني في حد ذاته أن لديك O (1) البحث.

مترجم حر في اختيار طريقة البحث لكل بيان التبديل، وليس هناك ضمان سوف تحصل على تنفيذ واحد معين. ومع ذلك، ينبغي أن تؤخذ في الاعتبار خيارات المترجم مثل الأمثل للسرعة والأمثل للحجم.

يجب عليك النظر في دراسة هياكل البيانات للحصول على التعامل مع متطلبات التعقيد المختلفة التي تفرضها. باختصار، إذا كان عن طريق "القاموس" يعني شجرة ثنائية متوازنة، ثم هو O (لوغ ن). و جدول التجزئة يعتمد على وظيفة التجزئة و استراتيجية الاصطدام. في حالة معينة من البيانات التبديل، منذ مترجم لديه معلومات كاملة، يمكن أن تولد وظيفة التجزئة الكمال مما يعني O (1) البحث. ومع ذلك، لا تضيع بمجرد النظر في تعقيد الخوارزمية الشاملة: فإنه يخفي عوامل هامة.





switch-statement