Fastest way to find max value in a C++ array

Question

I am trying to find the max value in a C++ array (Arduino). Is there a faster way to do this, than how I have tried below?

const int arraySize = 5;
float currentLargest;

void setup() {
  Serial.begin(115200);
}

void loop() {
  float accelVals[arraySize] = {-1.0,-2.0,-10.0,-10.0,-2.2}; //X, Y, Z
  Serial.println(findLargest(accelVals));
}

float findLargest(float arr[arraySize])
{
  for (int i = 0; i < arraySize; i++)
  {
    if (i == 0)
    {
      currentLargest = max(arr[i], arr[i+1]);
    }else{
      currentLargest = max(arr[i], currentLargest);
    }
  }
  return currentLargest;
}

The actual array I am trying to solve is much larger, approximately 2000 values, and I need to solve them dynamically as quickly as possible. This method is slow, and I am hoping there is a better way.

Thanks!

If the array isn't sorted, there's not going to be anything better than linear scan. You can hoist the `if(i == 0)` out of the `for` loop by initializing `currentLargest` to `arr[0]` but that probably won't make much of a difference. Also note that you get UB by trying to access `arr[arraySize]` when `i = arraySize - 1`. — Nathan Pierson, Aug 24 '21 at 00:07
Does this answer your question? [How can I get the maximum (or minimum) value in a vector?](https://stackoverflow.com/questions/9874802/how-can-i-get-the-maximum-or-minimum-value-in-a-vector) — msquared, Aug 24 '21 at 00:11
I would just start at `int max = arr[0]`, and loop from 1 till n - 1. and `if (max < arr[i]) max = arr[i]` — , Aug 24 '21 at 00:12
A mere 2000 elements is nothing in today's world. If you had 20 million elements, that may be a different story. — PaulMcKenzie, Aug 24 '21 at 00:13
But for 2000 elements? Are we talking about a modern microprocessor, or a pet mouse running in a wheel being the processor? — PaulMcKenzie, Aug 24 '21 at 00:17
I've closed this question as a duplicate of a canonical. If none of the solutions on the target work on arduino, please edit the question to say so, and feel free to ping me after doing that, and I'll reevaluate the closure. — cigien, Aug 24 '21 at 00:26
@PaulMcKenzie I guess it depends on the rest of the system. Since it is single core 16Mhz chip, if you are searching 2000 elements that come out of a sensor, while handling serial comms and responding to hardware interrupts. I am sure the 10ms to search an array of that size starts to look quite big. Also solid chance that there is either static, or no branch prediction. — Fantastic Mr Fox, Aug 24 '21 at 00:35
if the array is updated dynamically a lot, it may be a viable option to keep track of the maximum dynamically too: when a value is changed -- if it's greater than the current max, update the current max. otherwise don't. this behavior could (and in my opinion, should) be abstracted into a class that wraps the array. — aradarbel10, Aug 24 '21 at 00:54
On the adafruit M0, I need to evaluate packets of accelerometer data as quickly as possible, but this method is slower than I would like, was hoping for something faster. Looks like the linear scan is the fastest — MattG, Aug 24 '21 at 00:58

score 0 · Answer 1 · answered Aug 24 '21 at 00:15

If the array were sorted (which yours is not), then you could simply return the last element in the array, as it would already be the largest. But your array is not sorted, so you will have to resort to a linear scan.

Have a look at std::max_element(), if Arduino has it, eg:

#include <algorithm>

float findLargest(float arr[]) {
    return *std::max_element(arr, arr+arraySize);
}

Or, using std::begin()/std::end() in C++11 and later:

template<size_t N>
float findLargest(float (&arr)[N]) {
    return *std::max_element(std::begin(arr), std::end(arr));
}

Otherwise, if you want to search manually, then at least simplify your loop a little:

void loop() {
  float accelVals[arraySize] = {-1.0,-2.0,-10.0,-10.0,-2.2}; //X, Y, Z
  currentLargest = findLargest(accelVals);
  Serial.println(currentLargest);
}

float findLargest(float arr[]) {
    float largest = arr[0];
    for (int i = 1; i < arraySize; ++i) {
        largest = max(arr[i], largest);
    }
    return largest;
}

Fastest way to find max value in a C++ array

1 Answers1