Efficient way to store array with repeating values?

Question

So I have about 2000+ X and Y values where I will look up the Y value for a given X value. If I store the values naively they won’t fit in memory, however there are a lot of repeating values and the X values are arranged in numerical order so I don’t really need to store them explicitly.

So my plan is to use the 3 most common Y values and have an array for all the Y values with only 4 possible values (So using only 2 bits with a bitfield), where 0,1 and 2 corresponds to the most common Y values and 3 tells the program to go fetch the value somewhere else, and here I am thinking a hash table/tree.

Before implementing all this stuff I thought I would ask here if anyone has a better way of doing this, such as if it’s possible/recommended to use the flash memory on the arduino for this or if there’s some better way to store the data. The Y data consists of analog read values which hover around a specific value (say 800) and vary +- 20 or so. I think a histogram of the Y data follows a normal distribution, but I currently do not have enough data to tell.

Answer 1

Without a better understanding of what the data is or how you intend to use it it's impossible to give you real recommendations.

However it is simple enough to store your data in flash memory.

Since X is just a sequential value it can, as you have noted, be ignored.

For the rest, a simple array in flash which you then read with pgm_read_<X>() where <X> is the data size that you are using.

All this can be read on the Arduino PROGMEM Reference Page although the documentation is not great.

So here's a little example:

const int values[] PROGMEM = {
   100, 399, 2847, 1, -497, 32, 4370
};

void setup() {
    Serial.begin(115200);
    for (int i = 0; i < 7; i++) {
        Serial.println((int)pgm_read_word(&values[i]));
    }
}

void loop() {
}

The casting of the return from pgm_read_word as an int is needed to interpret the sign bit properly (it returns unsigned by default).