Lookup Table vs. Arrays

Projects Programming
1

So, i propose to traverse an array of structs to find out if today is a holiday, and then execute some code accordingly. I create an array of structs with the Month, Day and a pointer to a function for that day...

struct Date {
  int month, day;
  void(*holidayFunction)();
};

Date holidays[] = {
  {1, 1, newYear},
  {2, 14, valentine},
  {7, 4, fourthOfJuly}
};

Date today = {13, 32, everyday};

void setup()
{
  Serial.begin(9600);
  today.month = 1;
  today.day = 2;
  bool holiday = false;
  for (int i = 0; i < sizeof(holidays)/sizeof(holidays[0]); i++)
  {
    if (holidays[i].month == today.month && holidays[i].day == today.day)
    {
      holidays[i].holidayFunction();
      holiday = true;
      break;
    }
  }
  if (!holiday)
  {
    today.holidayFunction();
  }
  Serial.println("finished setup");
}

void loop()
{

}

void newYear(void)
{
  Serial.println("Happy New Year!!");
}

void valentine(void)
{
  Serial.println("Happy St Valentines Day!!");
}

void fourthOfJuly(void)
{
  Serial.println("Happy Birthday USA!!");
}

void everyday()
{
  Serial.println("Just any old day");
}

So (and assume for the sake of argument we are dealing with a much larger array) it was proposed to me that it may be more efficient to use a look-up table. Searching the internet, I am unable to locate an example that would correspond to my specific example (a two dimensional array, essentially with a finite number of possible intersections of Month and Day. Further, if I could sequence the table such that the entire table does not have to be traversed in order to see that the day is not special...

Anyone have a recommendation on how to create what I request?

2

I had to go through this exercise recently for a more complicated data structure. I'm a hack C++ programmer and figured out what would work largely through trial and error. So my solution (below) is probably not the most elegant one. I hope someone else responds with something better so that I can learn from them.

struct Date {
  uint8_t month, day;
  void(*holidayFunction)();
};

const Date holidays[] PROGMEM = {
  {1, 1, newYear},
  {2, 14, valentine},
  {7, 4, fourthOfJuly}
};

Date today = {13, 32, everyday};

void setup()
{
  Serial.begin(9600);
  Serial.println("\n");
  today.month = 2;
  today.day = 14;
  bool holiday = false;
  for (int i = 0; i < sizeof(holidays)/sizeof(holidays[0]); i++)
  {
    if (pgm_read_byte(&holidays[i].month) == today.month && pgm_read_byte(&holidays[i].day) == today.day)
    {
      Serial.println("\nGot it\n");
      void (*funcP)() = (void (*)())(pgm_read_word(&holidays[i].holidayFunction));
      funcP();
      holiday = true;
      break;
    }
  }
  if (!holiday)
  {
    today.holidayFunction();
  }
  Serial.println("finished setup");
}

void loop()
{

}

void newYear(void)
{
  Serial.println("Happy New Year!!");
}

void valentine(void)
{
  Serial.println("Happy St Valentines Day!!");
}

void fourthOfJuly(void)
{
  Serial.println("Happy Birthday USA!!");
}

void everyday()
{
  Serial.println("Just any old day");
}
3

If you convert month/day to day of the year, you could use Huffmann coding. Well, the binary tree search part of it anyway.

4

It was proposed to me that it may be more efficient to use a look-up table.

As far as I know, "lookup tables" are a higher-level language feature that you don't have access to in Arduino's subset of C++. And while it might be nice to say "function = holidays["2/14"];", it probably wouldn't be much more efficient than manually iterating through the array that you have now (depending on the number of holidays you plan to have!) (if you keep your holiday table sorted by date, then you can do a binary search through it instead of linear, which will result in a pretty significant improvement. But probably not a RELEVANT improvement.)

5

An array is a look up table.

6

(For example, here's some python!)

>>> holidays = {'1/1': 'newyears', '2/14': 'valentines', '3/12': 'st patricks', '7/4': 'Independence day'}
>>> print holidays['1/1']
newyears
>>> print holidays['3/12']
st patricks
>>> print holidays['3/13']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: '3/13'
>>> print holidays.get('3/13')
None
>>> print holidays.get('3/12')
st patricks
7

Yeah, considering the small number of holidays, a brute force comparison of all of them against a candidate is not really that bad.

8

BulldogLowell:
So (and assume for the sake of argument we are dealing with a much larger array) it was proposed to me that it may be more efficient to use a look-up table. Searching the internet, I am unable to locate an example that would correspond to my specific example (a two dimensional array, essentially with a finite number of possible intersections of Month and Day. Further, if I could sequence the table such that the entire table does not have to be traversed in order to see that the day is not special...

Anyone have a recommendation on how to create what I request?

I'd like to recommend to do a "binary search" within a "sorted holidays array".

For faster comparison I have changed your struct a bit to get a "compareDay" as a virtual daynumber within the year for comparison reasons. The "compareDay" is just created by multiplying the month with 31 (maximum number days in a month) and adding the day.

Example code:

struct Date {
  int compareDay;
  void(*holidayFunction)();
};

// The holidays array must be sorted ascending by date
Date holidays[] = {
  {1*31+1, newYear},
  {2*31+14, valentine},
  {7*31+4, fourthOfJuly}
};


void doHoliday(int key)
{ // do a binary Search of key 'compareDay' in holidays
  int lowerbound= 0;
  int upperbound= sizeof(holidays)/sizeof(Date)-1;
  int pos= ( lowerbound + upperbound) / 2;
  while((holidays[pos].compareDay != key) && (lowerbound <= upperbound))
  {
    if (holidays[pos].compareDay > key) upperbound = pos - 1; 
    else lowerbound = pos + 1;
    pos = (lowerbound + upperbound) / 2;
  }
  if (lowerbound <= upperbound) holidays[pos].holidayFunction();
  else everyday();
}

void setup()
{
  Serial.begin(9600);
  Serial.println("Holidays of the year");
  for (int i=1; i<=12; i++)
  {
    for (int j=1; j<=28; j++)
    {
      char buf[15];
      sprintf(buf,"%02d/%02d = ",j,i);
      Serial.print(buf);
      doHoliday(i*31+j);
    }
  }
}

void loop()
{
}

void newYear(void)
{
  Serial.println("Happy New Year!!");
}

void valentine(void)
{
  Serial.println("Happy St Valentines Day!!");
}

void fourthOfJuly(void)
{
  Serial.println("Happy Birthday USA!!");
}

void everyday()
{
  Serial.println("Just any old day");
}

Give it a try. The binary search within a sorted array reduces the number of comparisons needed dramatically.

Perhaps you know implementations of "guess the number game", the same binary search is used with that type of number guessing. The more entries your (sorted) array of holidays contains, the more you will profit from binary search.

9

You could even use bsearch() instead of reinventing the binary-search wheel.

1 Like
10

aarg:
Yeah, considering the small number of holidays, a brute force comparison of all of them against a candidate is not really that bad.

I appreciate what you are saying, but for the sake of learning through this exercise, I am using this array. For the sake of examples, let's assume that the amount of data is non-trivial.

11

jurs:
I'd like to recommend to do a "binary search" within a "sorted holidays array".

For faster comparison I have changed your struct a bit to get a "compareDay" as a virtual daynumber within the year for comparison reasons. The "compareDay" is just created by multiplying the month with 31 (maximum number days in a month) and adding the day.

Give it a try. The binary search within a sorted array reduces the number of comparisons needed dramatically.

Perhaps you know implementations of "guess the number game", the same binary search is used with that type of number guessing. The more entries your (sorted) array of holidays contains, the more you will profit from binary search.

+1 for this great example... easy to understand! thanks.

christop:
You could even use bsearch() instead of reinventing the binary-search wheel.

I appreciate that... I've not learned this method (yet).

jboyton:
I had to go through this exercise recently for a more complicated data structure. I'm a hack C++ programmer and figured out what would work largely through trial and error. So my solution (below) is probably not the most elegant one. I hope someone else responds with something better so that I can learn from them.

Pretty nice, and also easy to follow. Thanks!

12

I just assumed you meant RAM efficiency, silly me. Many Arduinos are quite limited in that respect whereas determining if today is a holiday is usually a very infrequent comparison. That's the problem with assuming though.

13

How is the data being prepared?

Is this for/on an Arduino class device?

14

westfw:
As far as I know, "lookup tables" are a higher-level language feature that you don't have access to in Arduino's subset of C++.

Where on earth do you get that from? The "Arduino language" IS c++, and gives you access to EVERY feature of full ANSI c++. It is in any way, shape or form a "subset of C++", and it is more than capable of implementing absolutely any data structure you can possibly imagine.

Regards,
Ray L.

15

A slightly different take on it, again using binary search.

This way you can keep your month and day except given most arduinos are little-endian, reversed the order of day/month in the class itself while still using your order in instance construction.

Makes use of union for quicker comparision.

The class overloads some operators to take advanges of the union in logical comparisions.

Makes the client code easier to write, read and understand.

If a match is found the local 'date' object is overwritten with the matching holidays allowing for 'date' 'print' mothod to print the found or unfound message.

#define COUNT_ENTRIES(ARRAY)    (sizeof(ARRAY) / sizeof(ARRAY[0]))

class date_entry_t
{
    union
    {
        struct
        {
            uint8_t _month;
            uint8_t _day;
        };
        uint16_t    _combined;
    };

    void (*_funct)();

public:
    date_entry_t(uint8_t month, uint8_t day, void (*func)() = 0)
        : _month(month)
        , _day(day)
        , _funct(func)
    {   }

    void print()
    {
        _funct();
    }

    date_entry_t& operator= (const date_entry_t& rhs)
    {
        _combined   = rhs._combined;
        _funct      = rhs._funct;
        
        return *this;
    }

    friend bool operator== (const date_entry_t& lhs, const date_entry_t& rhs)
    {
        return lhs._combined == rhs._combined;
    }
    friend bool operator!= (const date_entry_t& lhs, const date_entry_t& rhs)
    {
        return ! (lhs._combined == rhs._combined);
    }
    friend bool operator< (const date_entry_t& lhs, const date_entry_t& rhs)
    {
        return lhs._combined < rhs._combined;
    }
    friend bool operator> (const date_entry_t& lhs, const date_entry_t& rhs)   { return   rhs < lhs;  }
    friend bool operator<=(const date_entry_t& lhs, const date_entry_t& rhs)   { return !(lhs > rhs); }
    friend bool operator>=(const date_entry_t& lhs, const date_entry_t& rhs)   { return !(lhs < rhs); }
};

void newYear(void)      { Serial.println("Happy New Year!!"); }
void valentine(void)    { Serial.println("Happy St Valentines Day!!"); }
void fourthOfJuly(void) { Serial.println("Happy Birthday USA!!"); }
void everyday()         { Serial.println("Just any old day"); }

date_entry_t holidays[] =
{
      date_entry_t( 1,  1, newYear)
    , date_entry_t( 2, 14, valentine)
    , date_entry_t( 7,  4, fourthOfJuly)
};

void loop()
{   }

void setup()
{
    Serial.begin(9600);

    date_entry_t date(1, 2, everyday);

    size_t  indexLHS    = 0;
    size_t  indexRHS    = COUNT_ENTRIES(holidays);
    size_t  index       = indexRHS / 2;
    while ( indexLHS <= indexRHS )
    {
        if ( holidays[index] == date )
        {
            date = holidays[index];
            break;
        }

        if ( holidays[index] > date )
        {
            indexRHS = index - 1;
        }
        else
        {
            indexLHS = index + 1;
        }
    
        index = ((indexLHS + indexRHS) / 2);
    }

    date.print();

    Serial.println("finished setup");
}
16

A lookup table for the year should be like lookUp[ 12 ][ 31 ] where the values would give a holiday number or NULL. One fetch from lookUp[ month ][ day ] and you know if it's a holiday or not.
That would need an extra array of holiday names by number if you want the names but it would be fast.

The main table would be 372 bytes, the holiday names may take more space and all of it should be kept in PROGMEM.

17

There are a variety of ways to implement a "lookup table" in a lower-level language like C. You can binary-chop-search, you can use a hash table, you can use a tree, you can use various ways of doing sparse arrays.

To convert our date into a number, you can multiply month by 31 and add the day - or to make life even easier, multiply by 100. Valentine's day becomes 214. Christmas 1225. Easy.

To make a hash table, pick a prime number (or a number that is relatively prime to 32 - any odd number will do) big enough to hold all of your dates. To find a holiday, check (datenum % table size). If that record isn't the date you need add 32 to datenum and look there (mod table size). Why 32? because it's greater than 31. Because your table size is relatively prime compared to 32, doing this will eventually try every entry. But because the modulus scatters the entries over the table, you will mostly find the holiday you are looking for after a few tries.

This is an oft-travelled road, and there's a great deal of both theoretical and practical material on the subject.

18

As far as I know, "lookup tables" are a higher-level language feature that you don't have access to in Arduino's subset of C++.

Where on earth do you get that from? The "Arduino language" IS c++, and gives you access to EVERY feature of full ANSI c++.

The C++ "lookup table" would be (I think) one of the 'containers' in the Standard Template Library (STL) (probably "map"?), not part of the C++ "language" itself (in the same way that printf() is not really part of the C language. Both arguable, I guess.) The STL is not included with the Arduino distribution, and while there have been people who have added it, I would expect that the class itself would 1) be substantially large, for an Arduino. 2) Make extensive use of Dynamic Memory Allocation. 3) Not understand AVR constant PROGMEM arrays at all.
C++ aficionados seem to regard the STL as fundamentally part of and required of C++; Arduino and other embedded C++ users... no so much. (I've quoted this discussion before: Learning C++ properly (not C with classes) - Software Engineering Stack Exchange )

19

Yes, map. You are probably right about it not understanding PROGMEM.

20

This is my attempt to use bsearch. It works fine, however my attempts to modify it to use an array in PROGMEM have so far been unsuccessful.

struct Date {
  int compareDay;
  void(*holidayFunction)();
};

void newYear () 
  {
  Serial.println (F("New Year"));
  }
void valentine () 
  {
  Serial.println (F("Valentine"));
  }
void fourthOfJuly ()
  {
  Serial.println (F("Fourth of July"));
  }
void xmasDay ()
  {
  Serial.println (F("Xmas Day"));
  }
void boxingDay ()
  {
  Serial.println (F("Boxing Day"));
  }
  
#define MAKE_DATE(month, day) (month*31) + day

// The holidays array must be sorted ascending by date
Date holidays[] = {
  {MAKE_DATE (1, 1),    newYear},
  {MAKE_DATE (2, 14),   valentine},
  {MAKE_DATE (7, 4),    fourthOfJuly},
  {MAKE_DATE (12, 25),  xmasDay},
  {MAKE_DATE (12, 26),  boxingDay},
};

// number of items in an array
#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))

int compareDates (const void * a, const void * b)
{
  Date * date1 = (Date *) a;
  Date * date2 = (Date *) b;
  
  return date1->compareDay - date2->compareDay;
  
} // end of compareDates

void printResult (Date * pItem);  // prototype
void printResult (Date * pItem)
  {
  if (pItem)
    {
    Serial.print (F("  Found "));
    pItem->holidayFunction ();
    }
  else
   Serial.println (F("  ** Not found"));
  } // end of printResult

void lookupDate (const int month, const int day)
  {
  Date * pItem;    
  int key = MAKE_DATE (month, day); 
  unsigned long start = micros ();
  pItem = (Date *) bsearch (&key, holidays, ARRAY_SIZE (holidays), sizeof (Date), compareDates);
  unsigned long finish = micros ();
  Serial.println ();
  Serial.print (F("Month = "));
  Serial.print (month);
  Serial.print (F(", day = "));
  Serial.print (day);
  
  Serial.print (F(", time taken = "));
  Serial.println (micros () - start);
  printResult (pItem);
  Serial.flush ();
  } // end of lookupDate
  
void setup ()
  {
  Serial.begin (115200);
  Serial.println (F("----- Starting -----"));  
  lookupDate (2, 14);  // valentine
  lookupDate (1, 1);   // new year's day
  lookupDate (7, 4);   // 4th of July
  lookupDate (2, 2);   // not in table
  lookupDate (12, 25);   // Xmas day
  lookupDate (12, 26);   // Boxing Day
  }  // end of setup

void loop ()
  {
  }  // end of loop

Output:

----- Starting -----

Month = 2, day = 14, time taken = 532
  Found Valentine

Month = 1, day = 1, time taken = 488
  Found New Year

Month = 7, day = 4, time taken = 480
  Found Fourth of July

Month = 2, day = 2, time taken = 480
  ** Not found

Month = 12, day = 25, time taken = 584
  Found Xmas Day

Month = 12, day = 26, time taken = 584
  Found Boxing Day