Jump Table Switch Case câu hỏi

Question

Tôi đang cố gắng hiểu một số điều về các bảng nhảy và mối quan hệ của nó giữa một câu lệnh case switch.

Tôi đã nói rằng một bảng nhảy là một cấu trúc O (1) mà trình biên dịch tạo ra, giúp tra cứu các giá trị về cơ bản nhanh nhất có thể. Tuy nhiên trong một số trường hợp, Hashtable/Dictionary có thể nhanh hơn. Tôi cũng đã nói điều này sẽ chỉ hoạt động nếu trường hợp chuyển đổi chứa ordered giá trị dữ liệu.

Ai đó có thể vui lòng xác nhận hoặc từ chối điều này và giải thích xem bảng nhảy là gì, tầm quan trọng và độ phức tạp của thời gian so với sử dụng từ điển hoặc có thể bắt đầu. Cảm ơn.

Answer 1

Bàn nhảy là cấu trúc trừu tượng được sử dụng để điều khiển chuyển đến một vị trí khác. Goto, tiếp tục, và phá vỡ là tương tự, ngoại trừ họ luôn luôn chuyển đến một địa điểm cụ thể thay vì một khả năng từ nhiều. Đặc biệt, luồng điều khiển này không giống như một cuộc gọi hàm. (Bài viết trên Wikipedia về branch tables có liên quan.)

A tuyên bố chuyển đổi là cách viết bảng nhảy trong C/C++. Chỉ có một hình thức giới hạn được cung cấp (chỉ có thể chuyển đổi trên các loại tích phân) để thực hiện việc triển khai dễ dàng hơn và nhanh hơn trong trường hợp thông thường này. (Làm thế nào để thực hiện các bảng nhảy hiệu quả đã được nghiên cứu nhiều hơn nữa cho các loại tích phân hơn cho trường hợp chung.) Một ví dụ cổ điển là Duff's Device.

Tuy nhiên, khả năng đầy đủ của bảng nhảy thường không được yêu cầu, chẳng hạn như khi mọi trường hợp có tuyên bố ngắt. Các "bảng nhảy giới hạn" này là mẫu khác nhau, chỉ tận dụng hiệu quả của hiệu quả nghiên cứu của bảng nhảy và phổ biến khi mỗi "hành động" độc lập với các hành động khác.

---

Việc triển khai thực tế các bảng nhảy có các dạng khác nhau, chủ yếu là khác nhau về cách lập bản đồ chỉ mục. Ánh xạ đó là nơi các thuật ngữ như "từ điển" và "bảng băm" xuất hiện và các kỹ thuật đó có thể được sử dụng độc lập với bảng nhảy. Nói rằng một số mã "sử dụng một bảng nhảy" không ngụ ý bởi chính nó mà bạn có O (1) tra cứu.

Trình biên dịch được tự do lựa chọn phương pháp tra cứu cho từng câu lệnh chuyển đổi và không có sự đảm bảo nào bạn sẽ nhận được một triển khai cụ thể; tuy nhiên, các tùy chọn trình biên dịch như là tối ưu hóa tốc độ và tối ưu hóa cho kích thước sẽ được tính đến.

Bạn nên xem xét nghiên cứu cấu trúc dữ liệu để xử lý các yêu cầu phức tạp khác nhau mà chúng áp đặt. Tóm lại, nếu bằng "từ điển" bạn ngụ ý một cây nhị phân cân bằng, thì đó là O (log n); và một bảng băm phụ thuộc vào hàm băm và chiến lược va chạm của nó. Trong trường hợp cụ thể của báo cáo chuyển đổi, vì trình biên dịch có thông tin đầy đủ, nó có thể tạo ra một perfect hash function có nghĩa là tra cứu O (1). Tuy nhiên, không bị lạc bởi chỉ cần nhìn vào sự phức tạp của thuật toán tổng thể: nó ẩn các yếu tố quan trọng.

Answer 2

Biên dịch cho một câu lệnh chuyển đổi có thể mất nhiều hình thức, tùy thuộc vào từng trường hợp. Nếu các trường hợp gần nhau, nó không có trí tuệ: sử dụng bảng nhảy. Nếu các trường hợp cách xa nhau, hãy sử dụng if (case == value) hoặc sử dụng bản đồ. Hoặc trình biên dịch có thể sử dụng kết hợp: các hòn đảo của các bảng nhảy được xác định bằng cách kiểm tra các phạm vi bảng nhảy.

Answer 3

Giả sử bạn có một mảng các thủ tục:

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

... 

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



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

Giả sử bạn chấp nhận một nhân vật (từ az) của đầu vào từ người sử dụng và chạy fc:

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

Lý tưởng này sẽ được thay thế bằng một cái gì đó như:

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

Đương nhiên, bạn có thể làm cho bảng lớn hơn để kiểm tra phạm vi uldn't là cần thiết.

Trình biên dịch sẽ thực hiện việc này cho mã tùy ý, không nhất thiết phải thực hiện các cuộc gọi chức năng và sẽ thực hiện việc này bằng cách lưu trữ địa chỉ để chuyển đến (về cơ bản, một goto). C không trực tiếp hỗ trợ bất kỳ loại goto tính toán nào (lập chỉ mục vào bảng hoặc cách khác), nhưng các hướng dẫn CPU cho nó khá đơn giản.

Answer 4

Bàn nhảy về cơ bản là một mảng con trỏ tới các đoạn mã để xử lý các trường hợp khác nhau trong câu lệnh chuyển đổi. Nó rất có thể được tạo ra khi các trường hợp của bạn dày đặc (tức là bạn có một trường hợp cho mọi giá trị có thể trong một phạm vi). Ví dụ, đưa ra một tuyên bố như:

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

nó có thể tạo ra mã tương đương với một cái gì đó như thế này:

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

có O (K) Sự phức tạp này. Một bảng băm điển hình cũng có khoảng O (K) mong đợi phức tạp, mặc dù trường hợp xấu nhất thường là O (N). Bảng nhảy thường sẽ nhanh hơn, nhưng nó thường sẽ chỉ được sử dụng nếu bảng sẽ khá dày đặc, trong khi một bảng băm/từ điển hoạt động khá tốt ngay cả khi các trường hợp sẽ khá thưa thớt.

bảng

Answer 5

Một nhảy rất đơn giản một loạt các chức năng gợi ý, bạn có thể hình dung ra một bảng nhảy xấp xỉ như vậy:

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

Từ hiểu biết của tôi, điều này được sử dụng với một tuyên bố trường hợp như vậy: mỗi điều kiện , trường hợp _, sẽ là một chỉ mục trong mảng này, ví dụ:

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 
     ... 

Mỗi trường hợp, biến đổi thành các hàm đơn giản [a]. Điều này có nghĩa là các chức năng truy cập [9] cũng nhanh như truy cập các chức năng [1]. Cung cấp cho bạn thời gian O (1) bạn đã đề cập.

Rõ ràng, nếu bạn có trường hợp 1 và trường hợp 4907, đây không phải là phương pháp hay và phương pháp bảng/từ điển băm bạn đã đề cập có thể phát huy tác dụng.

Answer 6

Tiếp tục xây dựng trên Jerry's answer và những người khác

Given:

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

bạn có thể có một cái gì đó như sau:

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

Các trình biên dịch có thể sử dụng một bảng nhảy để index {f1, f2, f3}

Trình biên dịch có thể thực hiện nội tuyến khi tạo bảng có f1, f2, f3 thiết x trực tiếp đến 6,9,8

Nhưng nếu bạn đã viết các chức năng, và cán bảng nhảy của riêng bạn, f1,f2,f3 có thể là bất cứ nơi nào, nhưng trình biên dịch sẽ biết phải đặt chúng gần với switch tạo tốt hơn nhiều mã địa phương hơn bạn có thể.

Lưu ý rằng trong nhiều trường hợp trình biên dịch sẽ tạo ra một người bảo vệ để kiểm tra xem i nằm trong phạm vi (hoặc để xử lý các default) và nếu bạn chắc chắn rằng nó luôn luôn là một trong những trường hợp, bạn có thể bỏ qua mà

điều thú vị là cho dưới một số ít trường hợp, và dưới cờ biên dịch khác nhau (biên dịch phụ thuộc) các switch sẽ không sử dụng một bảng, nhưng sẽ chỉ làm IFS, tương tự như:

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

hoặc nó có thể tối ưu hóa điều này (nơi các bài kiểm tra đơn giản là một hướng dẫn) tới:

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

Lời khuyên tốt nhất là nhìn vào lắp ráp tạo ra để xem những gì các trình biên dịch đã làm cho mã của bạn trên kiến ​​trúc của bạn, g ++ trên Linux/intel sẽ tạo ra một cái gì đó như sau, nếu có một bảng nhảy

(lưu ý tôi đã phải đi đến 5 case báo cáo để buộc các bảng nhảy, nó được sử dụng IFS thấp hơn số case báo cáo)

Lưu ý rằng các lỗ nhỏ sẽ nằm trong bảng nhảy để làm 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; 
} 

sẽ tạo mã lắp ráp sau (// ý kiến ​​là của tôi):

 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