哪種查找方法對於簡單整數到字符串查找最有效

Question

我需要在某些C代碼中查找字符串標識符，並且正在考慮如何對查找進行編碼。標識符和字符串在編譯時是固定的，不可能改變。我認爲索引到一個字符串數組將是最有效的 - 那就是lookup1。

有時在代碼標識符不從0開始或有差距在編號如此選擇LOOKUP2用於這些情況。 lookup2使用switch語句。

另一種選擇是lookup3，它使用一個帶有整數到字符串映射的結構。

我想過的一些利弊。

LOOKUP2更加靈活，如果標識符不從零開始，或者如果有差距

如果標識符從零開始，有沒有差距則lookup1是更好？如果不是，那麼去lookup2方法？

lookup3怎麼樣？

這是遺留代碼，定義已經存在。對於新代碼，枚舉會更好嗎？

通常會有5-20個定義在一個類別中。可以有100多個。

這是代碼。

#include <stdio.h> 

#define RINGING  0x0 
#define DIALING  0x1 
#define IDLE  0x2 
#define ENGAGED  0x3 
#define CONNECTED 0x4 

static const char* const lookup1(int id) { 
    static const char* const identifiers[] = { 
     "RINGING", 
     "DIALING", 
     "IDLE", 
     "ENGAGED", 
     "CONNECTED" }; 

    int size = sizeof(identifiers)/sizeof(identifiers[0]); 
    if (id >= 0 && id < size) { 
     return identifiers[id]; 
    } 
    return "Unknown identifier"; 
} 


static const char* const lookup2(int id) { 
    switch (id) { 
    case RINGING: return "RINGING"; 
    case DIALING: return "DIALING"; 
    case IDLE: return "IDLE"; 
    case ENGAGED: return "ENGAGED"; 
    case CONNECTED: return "CONNECTED"; 
    default: return "unknown"; 
    } 
} 

static const char* const lookup3(int id) { 
    struct id2name { 
     int id; 
     const char* const name; 
    }; 

    static struct id2name pairings[] = { 
     { RINGING, "RINGING" }, 
     { DIALING, "DIALING" }, 
     { IDLE, "IDLE" }, 
     { ENGAGED, "ENGAGED" }, 
     { CONNECTED, "CONNECTED" } }; 

    int size = sizeof(pairings)/sizeof(pairings[0]); 
    if (id >= 0 && id < size) { 
     return pairings[id].name; 
    } 

    return "Unknown identifier"; 
} 


int main() { 
    const int identifiers[] = { RINGING, DIALING, IDLE, ENGAGED, CONNECTED }; 
    const int size = sizeof(identifiers)/sizeof(identifiers[0]); 
    for (int i = 0; i < size; ++i) { 
     printf("using lookup1 id %d is: %s\n", i, lookup1(i)); 
     printf("using lookup2 id %d is: %s\n", i, lookup2(i)); 
     printf("using lookup3 id %d is: %s\n", i, lookup3(i)); 
    } 
} 

Answer 1

它是很難被擊敗的表檢索，如您lookup1()爲了清晰，簡潔和速度。然而，這並不是說其他​​方法可能不會在速度上起作用。對於相對性能問題，您確實需要進行基準測試。

如果最大索引號很大或者任何索引號小於零，或者如果不能至少依賴C99，那麼直接基於數組的表查找會出問題，但否則，索引不是一個特別的問題，包括在數組的開始和使用的最低索引之間。這樣考慮：

#define INITIALIZER(x) [x] = #x, 

const char *lookup4(int x) { 
    static const char * const table[] = { 
     INITIALIZER(RINGING) 
     INITIALIZER(DIALING) 
     INITIALIZER(IDLE) 
     INITIALIZER(ENGAGED) 
     INITIALIZER(CONNECTED) 
     // initializers have the form: 
     // [MACRO] = "MACRO", 
    }; 

    const char *result = ((x < 0 | x >= (sizeof(table)/sizeof(table[0]))) 
     ? NULL 
     : table[x]; 

    return result ? result : "unknown"; 
} 

使用指定的初始值（由INITIALIZER()宏生產）來初始化對應於有效字符串查找表的那些元件;其他人將是NULL。這最終與您的lookup1()非常類似。

沒有什麼特別不對您lookup2()。它很乾淨清晰，我想大多數編譯器會爲它生成非常高效的代碼。

由於lookup3()提出，不過，我看不出有任何理由，更喜歡它比任何其他人。你不使用消息號碼，爲什麼把它們存儲在你的結構中？沒有他們，但是，你不需要一個結構，所以你基本上有一個更復雜的實施lookup1()。如果您確實使用了數字 - 例如通過在數組中搜索所請求的消息編號進行搜索 - 那麼平均而言這比其他方法更昂貴。

Answer 2

如果標識符從零開始，有沒有差距則lookup1是更好？

是的。

如果沒有，那麼去LOOKUP2方法？

是的。

如何lookup3？

lookup3是馬車。您需要遍歷所有的配對並檢查ID，即：

static struct id2name pairings[] = { 
    { RINGING, "RINGING" }, 
    { DIALING, "DIALING" }, 
    { IDLE, "IDLE" }, 
    { ENGAGED, "ENGAGED" }, 
    { CONNECTED, "CONNECTED" } }; 

int size = sizeof(pairings)/sizeof(pairings[0]); 
for (i = 0; i < size; i++) { 
    if (pairings[i].id == id) { 
     return pairings[i].name; 
    } 
} 

如果在配對的ID []排序，你可以打破的循環越快，即

for (i = 0; i < size && pairings[i].id < id; i++) { 

對於新代碼，枚舉會更好嗎？

沒有在性能方面，但他們會看起來更好。