Pages: [1]   Go Down
Author Topic: Quickest way to search a uint16_t array for a uint16_t value?  (Read 1127 times)
0 Members and 1 Guest are viewing this topic.
0
Offline Offline
Jr. Member
**
Karma: 0
Posts: 85
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 211
Posts: 13042
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


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".
Logged

0
Offline Offline
Jr. Member
**
Karma: 0
Posts: 85
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Global Moderator
Melbourne, Australia
Offline Offline
Brattain Member
*****
Karma: 506
Posts: 19131
Lua rocks!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Code:
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:
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:
#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:
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.
Logged

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

Please post technical questions on the forum - not to me by personal message. Thanks very muc

0
Offline Offline
Jr. Member
**
Karma: 0
Posts: 85
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks Nick I will give it a try!
Logged

Pages: [1]   Go Up
Jump to: