比較C中兩個字符串的最快方法是什麼？

Question

爲了清楚起見，我只談論空字符串。

我熟悉在C中使用strcmp進行字符串比較的標準方法。但我覺得這樣很慢並且效率低下。

我不一定會尋找最簡單的方法，但效率最高。

當前比較方法（strcmp）可以進一步優化，而底層代碼仍然是跨平臺嗎？

如果strcmp無法進一步優化，我可以在沒有strcmp的情況下執行字符串比較的最快方法是什麼？

當前使用情況：

• 確定兩個任意的字符串匹配
• 字符串將不超過4096個字節，也不是在尺寸上小於1個字節
• 字符串被分配/解除分配的比較內相同的代碼/庫
• 一旦比較完成，我將字符串傳遞給另一個需要格式的庫，以標準的空終止格式
• 系統內存裏mits不是一個巨大的問題，但我將有數以萬計的這樣的字符串排隊進行比較
• 字符串可能包含高ascii字符集或UTF-8字符，但對於我的目的，我只需要知道它們是否匹配，內容是不是一個問題
• 應用在x86上運行，但也應該在x64上運行

參考當前的strcmp（）實現：

• How does strcmp work?
• What does strcmp actually do?
• GLIBC strcmp() source code

編輯：明確瞭解決方案不需要是STRCMP的修改。

編輯2：增加了這個用例的具體例子。

Answer 1

恐怕你參考imlementation爲strcmp()既是不準確和不相關：

• 這是不準確的，因爲它是在C11標準規定比較使用char類型，而不是字符unsigned char類型：

  7.24。4個比較函數

  由比較功能memcmp，strcmp返回非零值的符號，並strncmp由第一字符對（均爲解釋爲unsigned char），該不同的值之間的差的符號來確定在被比較的對象中。

• 這是不相干的，因爲現代編譯器使用的實際實現更復雜，使用手工編碼彙編語言進行內聯擴展。

任何通用的實現可能不太理想，特別是如果編碼爲跨平臺保持可移植性的話。

下面是幾個方向來探討如果你的程序的瓶頸是比較字符串。

• 分析你的算法，試圖找到方法來減少比較的數量：例如，如果你搜索在數組中的字符串，排序數組和使用具有顯着減少比較數量二進制搜索。
• 如果您的字符串是在許多不同位置使用的令牌，請分配這些令牌的唯一副本並將它們用作標量值。當且僅當指針相等時，字符串纔會相等。我總是用哈希表在編譯器和解釋器中使用這個技巧。
• 如果您的字符串具有相同的已知長度，則可以使用memcmp()而不是strcmp()。 memcmp()比strcmp()簡單，並且可以在已知字符串正確對齊的地方更高效地實現。

編輯：所提供的額外信息，你可以使用這樣的結構，你的字符串：

typedef struct string_t { 
    size_t len; 
    size_t hash; // optional 
    char str[]; // flexible array, use [1] for pre-c99 compilers 
} string_t; 

你分配這樣的結構是這樣的：

string_t *create_str(const char *s) { 
    size_t len = strlen(s); 
    string_t *str = malloc(sizeof(*str) + len + 1; 
    str->len = len; 
    str->hash = hash_str(s, len); 
    memcpy(str->str, s, len + 1); 
    return str; 
} 

如果您可以使用這些東西來處理所有字符串，通過首先比較長度，可以大大提高匹配效率或哈希。您仍然可以將str成員傳遞給您的庫函數，它將正確地以null結尾。