嵌入式系统中用C语言实现的最快数组查找算法

Question

假设我有一个定义大小为22的常量浮点数组，如下所示：

array[0]= 0;
array[1]= 0.5;
array[2]= 0.7;
array[3]= 1.8;
...
...
array[21]= 4.2;

这个数组的值是单调的，也就是说，它们总是随着索引( array<=array1<=array2<=....<=array21 )的增加而增加。

我想要一个函数，给定一个浮点数，它会找到数组的索引，该数组的值紧接在输入浮点数的下面(因此，下一个索引值就在输入浮点数的上面)

例如，在前面的示例中，如果函数的输入是值0.68，则函数的输出应为1，因为array1<=为0.68

现在，这很容易实现，但我正在处理嵌入式系统中非常关键的代码部分，我真的需要一个非常优化的算法来避免循环(以避免开销)。

我现在使用的最简单的方法就是使用if-elses展开循环，仅此而已。

示例：

if(input >= array[size-1])
    return size-1;
else if(input>= array[size-2])
    return size-2;
else if(input >= array[size-3])
    return size-3;
...
...

但这里的问题是，我会有抖动，因为不同输入的路径需要明显不同的时间。

所以我的问题是:有没有一种更快、更具确定性(抖动更小)的方法来实现这一点？

谢谢。豪尔赫。

Answer 1

如果你使用二进制搜索，你会得到O(log N)：

size_t binaryFind(double x, double *array, size_t N) {
    size_t lower = 0;
    size_t upper = N;

    while (lower + 1 < upper) {
        mid = (lower + upper) / 2;
        if (x < array[mid]) {
            upper = mid;
        } else {
            lower = mid;
        }
    }
    if (array[lower] <= x) return lower;
    return (size_t)-1;
}

备注：

N是数组中的元素数。请注意，array[N]位于数组之外。数组必须按升序排序。

如果x小于array[0]，则返回值为(size_t)-1。这是失败的等价物。

如果x大于array[N-1]，则返回值将为N-1。

Answer 2

下面发布的解决方案使用二进制搜索(对数时间复杂度)。要了解更多有关浮点数比较的信息，请参阅this answer。

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>

#define ACCURACY 0.0001

int float_cmp(const void *a, const void *b){
    float *a_f = (float *)a;
    float *b_f = (float *)b;
    float diff = *a_f - *b_f;
    if (diff > ACCURACY) return 1;
    else if (diff < -ACCURACY) return -1;
    else return 0;
}

size_t find(void *arr, size_t nitems, size_t size, void *val,  int (*compare)(const void *, const void*)){

    if (nitems < 1) return -1;
    else if (nitems == 1 && (compare(arr, val) == 0)) return 0;

    size_t lower = 0;
    size_t upper = nitems;

    while (upper - lower > 1){
        size_t id = (lower + upper) / 2;
        int cmp = compare(arr + size*id, val);
        if      (cmp == 0) return id;
        else if (cmp > 1)  upper = id;
        else               lower = id;
    }

    return -1;
}

float arr[] = {
    5.5,
    6.6,
    9.9,
    10.01,
    10.05,
    10.10,
};

int main(){
    float val = 10.10;
    size_t i = find(arr, sizeof(arr)/sizeof(arr[0]), sizeof(float), &val ,float_cmp);
    printf("index: %zu\n", i);
}

Answer 3

线性搜索实际上是无分支的(假设µC有条件移动)

int resultIdx = -1
for (size_t i = 0; i != 22; ++i)
  if (array[i] < testvalue) resultIdx = i;

您的编译器可能会展开此循环，对结果进行有条件的赋值，并可能将其赋值给一个寄存器。此外，由于它将继续迭代数组，因此它也将是无抖动的。