Hello forum.
I do have a small project, there is two arrays. Array no#1 holding ascending sorted values. This table is the input data
Array no#2 is the output data. It contains other values that are not linear but corresponds to Array no#1 index position.
Unfortunately Array no#2 is not possible to calculate with the microprocessor, so I have to use arrays for the moment.
The code example below is only showing test data and not real values. Worth to mention the arrays only hold around 60-80 values each.
So by timer 1, I find a value that is equal or greater in the Array no#1, we save the position (index) of found value. Then apply the output data from Array #2 with the corresponding index found in Array no#1. Very easy… but there is a BUT, it has to go lightning fast. need the result within 2-3 uSec. Below I have made some tests, with different negative results
1. I have following result normal ‘for loop’. Result to slow for values in the end of the array
Result: // 4uS beginning of array, 24uS middle, 44uS end of array
int array [60] = {
10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,
250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,
470,480,490,500,510,520,530,540,550,560,570,580,590,600};
int index;
int x=600;
unsigned long start = 0;
unsigned long longest = 0;
void setup ()
{
Serial.begin (115200);
unsigned long start = micros ();
for (index = 0; x > array[index]; index++){}
unsigned long finish = micros ();
Serial.print("Search Value :");
Serial.println(x);
Serial.print("Index Value :");
Serial.println(index);
Serial.print("Array Value Found :");
Serial.println(array[index]);
longest = max (longest, finish - start);
Serial.print ("Time taken = ");
Serial.print (longest);
Serial.println (" uS");
}
void loop () {}
2. Binary search made with a while for loop, strange result, cannot really say if it is ok or not. It can be so that I have made fault in the code., Result: end of array = 88 uS, middle of array = 4 uS, beginning of array= 72 uS
int first, last, middle;
int array [] = {
10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,
250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,
470,480,490,500,510,520,530,540,550,560,570,580,590,600};
int search=600; // search value
unsigned long finish = 0;
unsigned long start = 0;
unsigned long longest = 0;
void setup(){
Serial.begin (115200);
unsigned long start = micros ();
first = 0;
last = 60 - 1;
middle = (first+last)/2;
while( first <= last )
{
if ( array[middle] < search )
first = middle + 1;
else if ( array[middle] == search )
{
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
unsigned long finish = micros ();
Serial.print ("Time taken = ");
Serial.print("Search Value :");
Serial.println(search);
longest = max (longest, finish - start);
Serial.print ("Time taken = ");
Serial.print (longest);
Serial.println (" uS");
}
void loop (){
}
3. some kind of prediction, looking at previous input data value and then jump into the array at best possible location. It is expected that the sensor do not swing in value so much. This code is not written yet, I think this is the only solution.
4. using STL Binary Search. Maybe better for big arrays but on problem with binary search only looking for exact match, and output is either TRUE or FALSE. So this method cannot be used, very long search result worthless because i do not really understand how to use it, and yes I have used the "google" to find some code example, no way for Arduino.
#include <iterator>
#include <algorithm>
const int NUMBERS = 60;
int array [] = {
10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,
250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,
470,480,490,500,510,520,530,540,550,560,570,580,590,600};
int outdata [] = {
11,21,31,41,51,61,71,81,91,111,111,121,131,141,151,161,171,181,191,211,211,221,231,241,
251,261,271,281,291,311,311,321,331,341,351,361,371,381,391,411,411,421,431,441,451,461,
471,481,491,511,511,521,531,541,551,561,571,581,591,611};
int index;
int x=150;
boolean z;
unsigned long start = 0;
unsigned long longest = 0;
void setup ()
{
Serial.begin (115200);
unsigned long start = micros ();
for ( index=1 ; z == false ; index++ ){
z = std::binary_search(array, &array[index], x);
}
index = index -2;
unsigned long finish = micros ();
Serial.print("Search Value :");
Serial.println(x);
Serial.print("Index Value :");
Serial.println(index);
Serial.print("Array Value Found :");
Serial.println(outdata[index]);
longest = max (longest, finish - start);
Serial.print ("Time taken = ");
Serial.print (longest);
Serial.println (" uS");
}
void loop () {}
5.
My humble question to you experts out there,
Is it practically possible to improve any of the above methods? Or have I reached the limits of Arduino C++. If limits reached, can I improve with AVR code, meaning combine C and assembly? But it looks sooooo darn difficult avr-libc: Combining C and assembly source files. There is a function with the [bsearch avr-libc: <stdlib.h>: General utilities](http://bsearch avr-libc: <stdlib.h>: General utilities) looks interesting but need examples.
Best Regards
Mikael