CODEWITHSUNDEEP
carraysalgorithmembedded
Jorge S
Jorge S

Reputation: 81

Fastest array lookup algorithm in C for embedded system?

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.

Upvotes: 2

Views: 2856

Answers (4)

jeb
jeb

Reputation: 82237

If it's extreme time critical then you could build it completly with IF/ELSE for the fixed 22 elements.
You only have to unroll the sample of Klas Lindbäck.

But it seems more important to avoid the floats.
Use integers instead, the conversion rule could be (int)(floatValue*1000), but this depends of your required precision and number range.

Upvotes: 0

Lanting
Lanting

Reputation: 3068

A linear search would actually be branchless (provided your µC has a conditional move)

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

Your compiler will probably unroll this loop, make the assignment of the result conditional, and probably to a register. Furthermore, as it will continue iterating over the array, it will also be jitter free.

Upvotes: 0

Klas Lindb&#228;ck
Klas Lindb&#228;ck

Reputation: 33273

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

Upvotes: 7

pbn
pbn

Reputation: 2706

The solution posted below uses binary search (logarithmic time complexity). To learn more about floating point numbers comparison please see 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);
}

Upvotes: 3

Related Questions