二分查找优化？

Question

我正在编写一个关键字记录查找，其中i有一个关键字和记录号之间的索引。这是按键排序的。有没有比我在速度优化方面做得更好的地方？

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的倍数，并使用无符号整数比较一次比较4个字节，而不是一次比较1个字节。

如果你没有profiler，你应该买一个。分析器可以很容易地查看各种实现的相对成本。

另一种选择是选择一种不同的方式来组织数据。请查看AVL trees获取灵感。像前面提到的其他函数一样，选择某种Hashing函数可能是一个可行的选择

Answer 2

给定您实现的合适的比较函数，bsearch库函数将对数组执行二进制搜索。作为一个库函数，它经过了很好的优化，并且(希望)没有bug。

Answer 3

与使用二进制搜索来定位项目不同，散列映射可能更适合，因为它具有O(1)个查找特征。然而，这可能会很慢，因为使用简单的方法会产生大量冲突。然而，this paper描述了一种创建类似树的散列图的方法，该树的访问时间为O(log(n) / log(32))，其性能通常优于普通的散列图实现。(固定的aray +链表实现)。