嵌入式系统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-1
, x
大于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)
,但这取决于您所需的精度和数字范围。