c - c中的二进制搜索优化？

Question

我正在编写一个 key 记录查找，其中我在 key 和记录编号之间有一个索引。这是按键排序的。有什么办法比我的速度优化做得更好吗？

typedef struct
{
    char key[MAX_KEYLEN];
    int  rec;
} KeyRecPair;

typedef struct
{
    KeyRecPair *map;
    int         numRecs;
} KeyRecMap;

int GetRecFromKey(char *key, KeyRecMap *theMap)
{
    int cmpValue, bottom = 0;
    int half = theMap->numRecs / 2;
    int top = theMap->numRecs - 1;

    while (bottom != top)
    {
        cmpValue = strncmp(key, theMap->map[half].key, MAX_KEY_LEN); 

        if (cmpValue > 0)
        {
            /*top stays*/
            bottom = half + 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        if (cmpValue < 0)
        {
            /*bottom stays*/
            top = half - 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        return theMap->map[half].rec;
    }

    if (0 == strncmp(key, theMap->map[half].key, MAX_KEY_LEN))
        return theMap->map[half].rec;
    return 0;
}

Answer 1

您的大部分时间将花在 strncmp 上。

我建议将其设为 inlined ，或内联重写它，以避免头顶的函数调用。

如果您有勇气，可以unroll the loop一次或两次并看到性能提升。

如果您的字符串实际上是一个固定长度的 char 数组，您可以将长度设为 4 的倍数，然后使用 unsigned int 比较一次比较 4 个字节，而不是一次比较 1 个字节。

如果您没有 profiler ， 你应该得到一个。剖析器可以轻松查看各种实现的相对成本。

另一种选择是选择一种不同的方式来组织您的数据。查看AVL trees寻找灵感。选择某种 Hashing功能，就像提到的其他功能一样，可能是一个可行的选择