Эффективный способ хранения массива с повторяющимися значениями?

Итак, у меня есть около 2000+ значений X и Y, где я буду искать значение Y для заданного значения X. Если я храню значения наивно, они не поместятся в памяти, однако есть много повторяющихся значений, а значения X расположены в числовом порядке, поэтому мне не нужно хранить их явно.

Поэтому мой план состоит в том, чтобы использовать 3 наиболее распространенных значения Y и иметь массив для всех значений Y только с 4 возможными значениями (таким образом, используя только 2 бита с битовым полем), где 0,1 и 2 соответствуют наиболее общие значения Y и 3 сообщают программе, что нужно получить значение где-то еще, и здесь я думаю о хеш-таблице/дереве.

Прежде чем реализовать все это, я решил спросить здесь, есть ли у кого-нибудь лучший способ сделать это, например, возможно/рекомендуется ли использовать для этого флэш-память на Arduino или есть ли какой-нибудь лучший способ хранения данные. Данные Y состоят из аналоговых считанных значений, которые колеблются вокруг определенного значения (скажем, 800) и варьируются в пределах +- 20 или около того. Я думаю, что гистограмма данных Y соответствует нормальному распределению, но в настоящее время у меня недостаточно данных, чтобы что-то сказать.

, 👍0

Обсуждение

Не могли бы вы привести пример того, как будут выглядеть данные? Насколько быстрым должен быть поиск?, @Gerben


1 ответ

1

Без лучшего понимания того, что представляют собой данные или как вы собираетесь их использовать, невозможно дать вам реальные рекомендации.

Однако хранить данные во флэш-памяти достаточно просто.

Поскольку X – это просто последовательное значение, его, как вы заметили, можно игнорировать.

Для остального — простой массив во flash, который вы затем читаете с помощью pgm_read_<X>(), где <X> — размер данных, который вы используете. .

Все это можно прочитать на справочной странице Arduino PROGMEM, хотя документация не очень.

Вот небольшой пример:

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

Приведение возвращаемого значения из pgm_read_word к типу int необходимо для правильной интерпретации бита знака (по умолчанию он возвращает значение без знака).

,

Отлично, это полностью решило бы проблему с памятью :D Какова потеря скорости при хранении данных во флэш-памяти? Мне нужно читать относительно быстро, я запускаю АЦП на частоте около 30 кГц, и мне нужно читать данные между чтениями. Насколько я понимаю, флэш-память считывает фрагменты за раз, верно? Итак, я мог бы загружать части массива и хранить их в ОЗУ, используя эту часть массива?, @Beacon of Wierd

@BeaconofWierd В масштабах времени, о которых вы говорите, скорость незначительна. Нет, flash не читает кусками. Стирает по страницам, пишет по строкам, а читает по байтам. Это просто часть адресного пространства памяти инструкций. Да, это медленнее, чем чтение оперативной памяти, но лишь немного медленнее., @Majenko

А, это еще проще :) Я обновил вопрос, добавив более подробное объяснение того, как выглядят данные. Несмотря на то, что я могу хранить его во флэш-памяти, я, вероятно, все еще хочу хранить его эффективно, и вы похожи на человека, который любит думать о том, как эффективно хранить данные;), @Beacon of Wierd

@BeaconofWierd Вам придется более глубоко проанализировать данные, чтобы придумать подходящую систему хранения. И затем вы должны учитывать увеличение времени, которое требуется для декодирования ваших сжатых данных. Если все ваши значения представляют собой небольшую величину, изменяющуюся вокруг смещения, вы можете уменьшить размер хранилища вдвое, используя байт со знаком для хранения только смещения (± 127). Если бы вы могли уменьшить свои значения до 16 дискретных значений, вы могли бы сохранить их в полубайтах как 0-15 (2 значения на байт). Или вы можете упаковать 3 значения в 2 байта для 5-битных (0-31) значений (с 1 битом впустую на 2 байта)., @Majenko

@BeaconofWierd: в AVR чтение из ОЗУ занимает 2 такта ЦП на байт. Чтение из флэш-памяти занимает 3 цикла/байт. Если вы храните 16-битные значения, разница между флэш-памятью и ОЗУ составляет всего 2 цикла . Если вы сохраняете 8-битное смещение, это разница в один цикл. Незначительно в обоих случаях, если вы считываете только одно значение каждые 33 мкс., @Edgar Bonet

Смотрите также: