Thông não cách mà Go `switch-case string`



  • Thông thường, các ngôn ngữ biên dịch truyền thống như C/C++ đều không hỗ trợ switch-case chuỗi, pointer, hay nói chung là các non-integral.

    Integral là mấy cái thuộc số nguyên.

    Khái niệm chuỗi trong C

    Mặc định thì chuỗi là một dãy (mảng) char nằm trên bộ nhớ, với địa chỉ của từng kí tự liền kề nhau, kết thúc chuỗi là một kí tự có giá trị zero (thường gán bằng 0 hoặc '\0').

    Chuỗi tĩnh, trên stack:

    char *s = "string";
    char s2[] = "hello";
    

    Chuỗi động, trên heap:

    const char *s = "string";
    int len = 6;
    
    char *s2 = alloc(len * sizeof(char) + 1);
    for (int i = 0; i < len; i++)
        s2[i] = s[i];
    
    s2[len] = '\0';
    

    Để so sánh chuỗi, thông thường người ta hay sử dụng các hàm so sánh như strcmp, memcmp hoặc đơn giản hơn là một vòng lặp rồi so sánh từng kí tự một.
    switch-case thì không thể được nên chỉ còn if-else từng cặp một, cách này tương đối bad performance.

    Cách mà C++ xây dựng std::map

    Trong C++, có một loại kiểu đặc biệt trong thư viện stdmap.

    Hiểu đơn giản thì nó là một cái túi, bạn gán từng câu thần chú vào tương ứng với từng món đồ trong túi. Khi bạn thò tay vào lấy đồ và nói ra câu thần chú thì sẽ lấy ra được món đồ tương ứng.

    using namespace std;
    
    // Alibabốn setup cửa
    map<string, bool> mantra;
    mantra.insert(pair<string, bool>("Vừng ơi, mở ra!", true));
    
    // 40củ tên cướp đập cửa
    bool stt = false;
    stt = mantra.find("Đ.m mở nhanh nào, cửa l*n")->second; // invalid key
    

    Vậy là 40củ tên cướp phải nhờ đến hách-cơ phây-búc hách nick của thằng Alibabốn để lấy pass 😂

    Trong ví dụ trên, nếu ta thay std::string bằng const char* sẽ... lỗi. Đơn giản vì nó vẫn không chấp nhận non-integral, compiler sẽ chuyển thành const char (chỉ một kí tự). Vậy std::string hoạt động ra sao?

    Trước tiên thì ta nên nhớ một điều, mấy cái như template, bộ std đều là quy chuẩn của C++ và nó sẽ được xử lý trước các code C thuần (nhưng vẫn sau preprocessor - ba cái #define ấy).

    Standard string trong C++ tất nhiên cũng khác string C thuần (char*).
    Khi bạn tạo một std::string thì chỉ cần cung cấp một const char* là có ngay, nhưng thực tế thì compiler sẽ làm thêm một vài nhiệm vụ nữa là biến đoạn string đó thành hash (chuyển chuỗi thành số trong khoảng so sánh được) để tối ưu hóa việc so sánh chuỗi.

    So sánh hai số nguyên sẽ nhanh hơn so sánh hai chuỗi thông qua so sánh từng kí tự.

    Kết hợp hash trong std::map, trong ví dụ trên thì khi tìm và so sánh từng key để lấy ra value, tất nhiên C++ sẽ không so sánh từng kí tự mà so sánh hash của chúng

    char *ga = "con-ga"; uint32_t hash = 6969;
    char *ga2 = "con-ga"; uint32_t hash2 = 6969;
    bool = hash == hash2; // -> true
    

    Làm sao để có hash?

    Để chuyển chuỗi thành hash thì vô cùng đơn giản, ta có thể sử dụng các loại hash-function bằng cách tìm trên Google hoặc tự nghiên cứu ra một loại mới. Đơn giản nhất là prime hash, cho logic từng kí tự để tạo ra hash.

    uint32_t fa_hashStr(const char *str, int len) {
        uint32_t hash = 0;
        loop(i, 1, len) {
            hash += str[i - 1] * i;
            hash += i % 2;
        }
        return hash;
    }
    

    Ví dụ hash một chiều của mình, được sử dụng cho kiểu box trong fa-lang 😄

    Vậy Go so sánh chuỗi thế nào?

    Nếu bạn xem kỹ qua main repos của Go trên Github thì sẽ thấy có cả Adler32, CRCFNV.

    • Adler32 thường thấy trong zlib, nó chủ yếu để kiểm tra sai sót trong một đoạn mã hoặc kiểm tra file, Go sử dụng nó cho checksum.
    • FNV là một loại hash đặc biệt (tên của nó được đặt theo tên của ba người tạo ra, kí tự V đấy nhé 😂). Và Go sử dụng hash này cho việc so sánh chuỗi.

    Chuỗi trong Go không phải là char* như C. Ban đầu trong việc thiết kế thì chuỗi là một cụm bộ nhớ bao gồm cả pointer đến chuỗi và hash cùng các operator để xử lý chuỗi như trong C++.

    var x = "hello"
    switch x {
        case "gà":
        case "vịt":
        case "hello":
            fmt.Print("true")
    }
    

    Tương tự như cách mà C++ compiler làm, vịt hay hello đều đưa lên stack kèm với hash của nó. Ta có thể hình dung như sau:

    [0] : flt {0x68, 0x65, 0x6c, 0x6c, 0x6f}
    ~ ext, 115
    
    psh -1
        113 | next
        114 | next
        115 | mov, ... prt, ltr, 0b1 ... next
    

    Bài viết đến đây là kết thúc rồi, nếu thấy hay thì cho 1 like nhé 😂


  • Trùm cuối

    Bài viết chất, like cho bác 1 phát 😁

    like



  • @admin
    Hehe, quá khen, quá khen 😂
    alt text


Hãy đăng nhập để trả lời
 

Có thể bạn cũng quan tâm

.
DMCA.com Protection Status