c - c中的二分搜索优化？

Question

我正在写一个键记录查找我在键和记录号之间有一个索引的位置。这是按键排序的。有没有比我在速度优化方面做得更好的方法？

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;
}

score 4 · Accepted Answer

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

score 4 · Accepted Answer

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

我建议强制将其内联或重写内联，以避免函数调用过头。

如果您感到勇敢，则可以展开循环一次或两次并看到性能提升。

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

如果你没有profiler，你应该得到一个。Profiler 可以很容易地查看各种实现的相对成本是多少。

另一种选择是选择一种不同的方式来组织您的数据。查看AVL 树以获取灵感。选择某种散列函数，就像提到的其他函数一样，可能是一个可行的选择

score 2 · Accepted Answer

与其使用二分搜索来定位项目，哈希映射可能更合适，因为它具有 O(1) 查找特性。然而，这可能会因为使用天真的方法的碰撞负载而变慢。然而，本文描述了一种创建类似树的哈希图的方法，该树具有 O(log(n) / log(32)) 访问时间，通常优于普通哈希图实现。（固定数组+链表实现）。

score 1 · Accepted Answer

您有机会使用不是字符串的键吗？或者至少是最短的字符串？（MAX_KEYLEN 的值是多少）strcmp 循环的每次迭代可能是搜索速度较慢的部分之一。

score 1 · Accepted Answer

有没有理由要优化这个？您是否使用探查器运行程序并确定查找占总运行时间的很大一部分？你只是好奇你能多快得到它吗？（在我看来，两者都是很好的理由。）如果您只是随机优化它，请不要。

另外，请记住进行基准测试。在现代系统上很难判断两个版本的函数中哪一个更快（在我的 Z80 上更容易）。有多少缓存未命中可能比错误预测的分支数更重要，也可能不重要。

score 0 · Accepted Answer

我能想到的唯一可能的优化是在计算中使用类似于黄金分割率的东西，half而不是将剩余的子集分成元素数量相等的两半，即

        if (cmpValue > 0)
        {
                /*top stays*/
                bottom = half + 1;
                half = bottom + (top - bottom) * 3 / 5;
                continue;
        }
        if (cmpValue < 0)
        {
                /*bottom stays*/
                top = half - 1;
                half = bottom + (top - bottom) * 2 / 5;
                continue;
        }

score 0 · Accepted Answer

0

而不是除以 2 U 可以利用位移运算符。

=> for /2 你可以使用 >> 1

于 2008-12-11T10:59:00.607 回答

score 0 · Accepted Answer

既然每个循环都必须计算half一次，为什么不在使用它之前只做一次呢？这将减少两行看起来很复杂（至少相对而言）的代码。

score 0 · Accepted Answer

尽管我希望有一个体面的优化器为您执行此操作，但我会将 theMap->map 放入本地，以便它有一半的机会最终进入寄存器，而不是在每次访问时取消引用它。同样，我希望优化器为您执行此操作，因此您可能还想检查程序集输出。

我在发布时查看了 Visual Studio 2008 的输出，它在代码上做得非常好。例如，比较代码如下所示：

; 30   :         if (cmpValue > 0)
test    eax, eax
jle SHORT $LN11@GetRecFrom
; 31   :         {
; omitted inner block for > case.
$LN11@GetRecFrom:
; 37   :         if (cmpValue < 0)
jge SHORT $LN2@GetRecFrom

基本上，它是一个分支到分支，无需重新测试 cmpValue。不错的触感。

将 theMap->map 放入本地有一点好处，但它很小。如果 MAX_KEY_LEN 不是 4 的好倍数并且没有填充结构，则绝对应该将 int 放在结构的首位。

c - c中的二分搜索优化？

9 回答 9

Related

Reference