对于简单整数到字符串查找，哪种查找方法最有效？

Question

我需要在一些C代码中查找字符串标识符，并在考虑如何对查找进行编码。标识符和字符串在编译时是固定的，不太可能更改。我认为，对字符串数组进行索引将是最有效的--即lookup1。

有时，在代码中，标识符不是从0开始，或者在编号中存在空白，因此选择了lookup2作为这些情况。lookup2使用开关语句。

另一个选项是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;
    }
}

如果对pairings[]中的ID进行了排序，则可以更快地中断for循环，即

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

对于新代码，枚举会更好吗？

不是在表现上，但他们会看起来更好。