Go Down

Topic: Quickest way to search a uint16_t array for a uint16_t value? (Read 1 time) previous topic - next topic

renasis

Hello,

I have an array of uint16_t values. What would be the quickest way to identify if the array contained a particular uint16_t value? I have been reading about memchr, but it only appears to compare 1 byte. My code is basically the following.

uint16_t myarray[10];
//put values in myarray
uint16_t somevalue =62000;

Now, I need to search "myarray" to determine if it contains "somevalue", need a function to return true or false. Any assistance would be appreciated.

Thanks,

-ren

Coding Badly


Given the details you've provided the quickest way# is to sort the array and perform a binary search.


# Assuming "quickest way" means "the way that uses the least amount of CPU time".

renasis

CodingBadly,

Yes, least amount of cpu time is what I am looking for. Not sure how to sort and perform binary search, maybe I could just do a for loop and compare each value. Or I was thinking that I could use memchr, find 1st byte, then test for 2nd byte.

Thanks,

-ren

Nick Gammon

A straight linear search isn't that slow, for the number of items you can fit into memory. For example, worst-case:

Code: [Select]
const int MAX_ITEMS = 800;

int array [MAX_ITEMS];

void setup ()
  {
  array [MAX_ITEMS - 1] = 42;
 
  Serial.begin (115200);
  unsigned long start = micros ();
  boolean found = false;
 
  for (int i = 0; i < MAX_ITEMS; i++)
    if (array [i] == 42)
      {
      found = true;
      break;
      }
     
  unsigned long finish = micros ();
 
  Serial.print ("Time taken = ");
  Serial.print (finish - start);
  Serial.println (" uS");
 
  Serial.print ("Found = ");
  Serial.println (found); 
  }  // end of setup
 
void loop () {}


Output:

Code: [Select]
Time taken = 752 uS
Found = 1


That's under a millisecond. But if you want to better that, and the data is in sequence, you could use a binary search...

Code: [Select]
#include <iterator>
#include <algorithm>

const int MAX_ITEMS = 800;

int array [MAX_ITEMS];

void setup ()
  {
  unsigned long longest = 0;
 
  Serial.begin (115200);
 
  // each array element is its own position (this puts them in sequence)
  for (int i = 0; i < MAX_ITEMS; i++)
    array [i] = i;
 
  // try each one, see which is longest
  for (int i = 0; i < MAX_ITEMS; i++)
    {
    unsigned long start = micros ();
    bool found = std::binary_search(array, &array [MAX_ITEMS], i);
    unsigned long finish = micros ();
   
    if (!found)
      {
      Serial.print ("At position ");
      Serial.print (i);
      Serial.println (", not found, strange.");
      }
     
    longest = max (longest, finish - start);
    }
   
  Serial.print ("Time taken = ");
  Serial.print (longest);
  Serial.println (" uS");

  } // end of setup
 
void loop () {}


Output:

Code: [Select]
Time taken = 28 uS

That's somewhat faster. That algorithm is in the STL (Standard Template Library) although you could no doubt find your own by a Google search if you didn't want all of the STL.
Please post technical questions on the forum, not by personal message. Thanks!

More info:
http://www.gammon.com.au/electronics

renasis


Go Up
 


Please enter a valid email to subscribe

Confirm your email address

We need to confirm your email address.
To complete the subscription, please click the link in the email we just sent you.

Thank you for subscribing!

Arduino
via Egeo 16
Torino, 10131
Italy