这个插值查找实现有什么问题？

Question

这个插值查找实现有什么问题？

4

这是一个常见的在互联网上找到的Interpolation Search算法的C/C++实现。然而，当与一组大约100000个整数的排序数组一起使用时，mid变量开始生成负数组索引，导致分段错误。问题可能是什么？

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int interpolationSearch(int sortedArray[], int toFind, int len) {
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = len - 1;
    int mid;

    while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
        mid = low + ((toFind - sortedArray[low]) * (high - low)) /
              (sortedArray[high] - sortedArray[low]);

        if (sortedArray[mid] < toFind) {
            low = mid + 1;
        } else if (sortedArray[mid] > toFind) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    if (sortedArray[low] == toFind)
        return low;
    else
        return -1; // Not found
}

int main(void) {
    srand(time(0));
    int arr[100000];
    for (int i=0; i<100000; i++) {
        arr[i] = rand()%100000;
    }

    int length = sizeof(arr)/sizeof(int);
    qsort(arr,length,sizeof(int),order);

    for (int j=0; j<10000; j++) {
        interpolationSearch(arr,rand()%100000,length);
    }
}

- Gorkamorka

3个回答

4

子表达式：((toFind - sortedArray [low]) * (high - low))

... 可以轻松计算出类似于：((99999-0) * (99999-0)) == 99999^2

... 这比2^31（32位有符号整数范围）大得多。

一旦超过2^31-1，整数将溢出为负数，因此您会得到负索引。如果超过2^32（也可能会这样做），则（很可能是技术上未定义的）您将丢失高阶位，并且最终会得到有效的随机偏移量，既正又负。

为避免所有这些问题，您需要仔细计算数学运算，以确保没有子表达式产生整数溢出。通常，最简单的方法是转换为浮点数，其范围比32位整数大得多。

最后分析，这种二分查找插值通常不值得——计算插值的开销通常大于它“节省”的几个额外迭代。

- mcmcc

浮点数计算甚至会让情况变得更糟，因为它比整数计算要耗费更多的资源。 - kriss

@kriss：注意我说的是“最简单的方法”，而不是“最有效的方法”。 - mcmcc

插值法大获成功的一个应用场景是在未索引、压缩视频（特别是大型视频文件）中搜索目标位置。这是因为您无法直接读取给定字节位置处的时间戳 - 您必须向前或向后扫描，读取数据以找到它。 - caf

4

正如其他答案所解释的那样，您正在尝试计算形式为

A * B / C

但是这会出现问题，因为A * B会溢出。建议将表达式修改为

A * (B / C)

这段代码无法正常工作，因为通常情况下B小于C，所以整数除法会截断为零。

建议切换到浮点运算，但代价很高。但是你可以通过将表达式转换为定点数来解决问题：

A * ((B * F) / C) / F

（其中F是精心选择的2的幂次方。）

- Gareth Rees

通常情况下，在现代处理器上，浮点数除法比整数或定点数除法更便宜/更快。然而，转换可能会使转换+浮点数除法总体变慢。 - Chris Dodd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kriss · Accepted Answer

问题出在计算mid的表达式上。即使使用32位整数，乘积也很容易溢出。然后它变成负数。最好先进行除法运算再进行乘法运算。

将mid计算更改为使用64位整数（至少用于中间计算）可以解决问题。

下面是我修改后的版本（int64_t 在<stdint.h>中定义）：

int interpolationSearch(int sortedArray[], int toFind, int len) {
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = len - 1;
    int mid;

    int l = sortedArray[low];
    int h = sortedArray[high];

    while (l <= toFind && h >= toFind) {
        int64_t high_low = (high - low);
        int64_t toFind_l = (toFind - l);
        int64_t product = high_low*toFind_l;
        int64_t h_l = h-l;
        int64_t step = product / h_l;
        mid = low + step;

/*        mid = (low + high)/2;*/
        int m = sortedArray[mid];

        if (m < toFind) {
            l = sortedArray[low = mid + 1];
        } else if (m > toFind) {
            h = sortedArray[high = mid - 1];
        } else {
            return mid;
        }
    }

    if (sortedArray[low] == toFind)
        return low;
    else
        return -1; // Not found
}

一个更简单的解决方法是将差值搜索改为二分搜索，只需使用：mid = (low + high) / 2即可。即使它的收敛速度稍慢于差值搜索，但它避免了几次操作，包括一个乘法和一个除法，从而使内部循环更快。不确定差值搜索的潜在更快收敛是否弥补了这种简单性的损失。

我进行了一些性能测试。我的测试程序来源于这个问题

令人惊讶的是（对我来说），使用浮点数比使用大整数更有效率。在我的系统上，二分搜索在数组中有大约1000项时变得更快。对于大小为100000的数组，插值搜索几乎比简单的二分搜索快两倍。