嵌入式系统C中最快的arrays查找算法?

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

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

这个数组的值是单调的,也就是说,它们总是随索引而增加(array [0] <= array [1] <= array [2] <= …. <= array [21])。

我想要一个给定一个浮点数的函数,它找到数组的索引,其值正好在输入浮点数之下(因此,下一个索引的值紧接在上面)

例如,在前一种情况下,如果函数的输入值为0.68,则函数的输出应为1,因为数组[1] <= 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; ... ... 

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

所以我的问题是:是否有最快,更确定(更少抖动)的方式来实现它?

谢谢。 乔治。

如果使用二进制搜索,则得到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 。 这是失败的等价物。

返回值为N-1x大于array[N-1]

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

 #include  #include  #include  #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); } 

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

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

您的编译器可能会展开此循环,将结果的赋值设置为条件,也可能是寄存器。 此外,由于它将继续迭代arrays,因此它也将无抖动。

如果它是极端时间关键,那么你可以使用IF/ELSE为固定的22个元素完全构建它。
您只需要展开KlasLindbäck的样本 。

但是避免漂浮似乎更重要。
使用整数,转换规则可以是(int)(floatValue*1000) ,但这取决于您所需的精度和数字范围。