用于嵌入式系统的C中最快的阵列查找算法？ [英] Fastest array lookup algorithm in C for embedded system?

问题描述

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

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

这个数组的值是单调的，这是它们总是随着索引而增加（array [0 ]< = array [1]< = array [2]< = ....< = array [21]）。

给出一个float的函数，它找到数组的索引，该数组的值紧接在输入float之下（因此，下一个索引的值就在上面）

例如，在前一种情况下，如果函数的输入值为0.68，则函数的输出应为1，因为array [1]< = 0.68

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

我现在使用的最简单的方法就是用if-elses展开循环，就是这样。

示例：

  if（input> = array [ -1]）$ ​​b $ b return size-1; 
 else if（input> = array [size-2]）
 return size-2; 
 else if（input> = array [size-3]）
 return size-3; 
 ... 
 ... 
  

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

所以我的问题是：有一个最快和更确定性（更少的抖动）实现这个方法？

谢谢。
Jorge。

解决方案

你得到 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] 在数组之外。数组必须按升序排列。

返回值将为（size_t）-1 if x 小于 array [0] 。这是平等的失败。

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

Let's say I have a constant array of floats with defined size 22 that looks like this:

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

The values of this array are monotonic, this is, they always increase with the index ( array[0]<=array[1]<=array[2]<=....<=array[21] ).

And I want a function that given a float, it finds the index of the array whose value is immediately below the input float (and thus, the value of the next index is immediately above)

For example, in the previous case, if the input of the function is the value 0.68, the output of the function should be 1, since array[1]<= 0.68

Now, this is easy to implement, but i am dealing with a very time critical part of the code in an embedded system, and I really need a very optimized algorithm, that avoids loops (to avoid the overhead).

The simplest approach i am using now is just to unfold the loop with if-elses and that's it.

Example:

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

But the problem here is that then I have jitter, since the path for different inputs take significantly different time.

So my question is: is there a fastest and more deterministic (less jitter) way to implement this?

Thank you. Jorge.

解决方案

You get O(log N) if you use binary search:

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

Notes:

N is the number of elements in array. Note that array[N] is outside the array. The array must be sorted in ascending order.

Return value will be (size_t)-1 if x is smaller than array[0]. This is the equvalent of failure.

Return value will be N-1 is x is larger than array[N-1].

这篇关于用于嵌入式系统的C中最快的阵列查找算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！