# Efficient way to store array with repeating values?

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.

• Could you give an example of how the data would look? How fast would lookup need to be? Jun 10, 2020 at 18:56

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++) {
}
}

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).

• Nice, that would completely solve the memory issue :D What’s the speed penalty for storing the data in flash memory? I need to read relatively fast, I’m running the ADC at around 30 kHz and need to read data inbetween reads. From my understanding of flash memory it reads chunks at a time, right? So I could load parts of the array and store that in RAM while using that part of the array? Jun 10, 2020 at 18:54
• @BeaconofWierd At the time scales you are talking about the speed is negligible. No, flash does not read in chunks. It erases in pages, and writes in rows, but reads in bytes. It's just part of the instruction memory address space. Yes, it's slower than reading RAM, but only very slightly slower. Jun 10, 2020 at 19:12
• Ah, that makes it even simpler :) I updated the question with a more detailed explanation of how the data looks like. Even though I can store it in flash memory I probably still want to store it efficiently and you seem like the type of person who likes to think about how to store data efficiently ;) Jun 10, 2020 at 22:10
• @BeaconofWierd You would have to analyse the data more deeply to come up with some suitable storage system. And then you have to consider the increased time taken to decode your compressed data. If all your values are a small amount varying around an offset you can reduce your storage size by half by using a signed byte to store just the offset (±127). If you could reduce your values to just a selection of 16 discrete values you could store them in nibbles as 0-15 (2 values per byte). Or you could pack 3 values into 2 bytes for 5-bit (0-31) values (with 1 bit wasted per 2 bytes). Jun 10, 2020 at 22:26
• @BeaconofWierd: On AVR, reading from RAM takes 2 CPU cycles per byte. Reading from flash takes 3 cycles/byte. If you store 16-bit values, flash vs RAM is only 2 cycles difference. If you store an 8-bit offset, it's one cycle difference. Negligible in both cases if you only read one value every 33 µs. Jun 10, 2020 at 22:28