Замена большой таблицы поиска оператором switch

Моей Arduino нужно взять 14-битное число и преобразовать его в 10-битное число. Не могу использовать формулу для этого, так как данные довольно случайны. Поэтому я создал таблицу поиска с 2^14 элементами, каждый из которых содержит 10-битное значение. Но он слишком большой для ардуино. Поэтому я подумал об использовании вместо этого оператора switch. Приведет ли это к значительному снижению скорости?

Скажем, например, что входное значение равно 16383. Сколько времени потребуется Arduino для перебора 16384 случаев по сравнению с доступом к индексу № 16383 массива?

EDIT: этот код компилируется нормально и сообщает об использовании программной памяти 1000 байт.

int xval;
int yval;

void setup() {
  // put your setup code here, to run once:
}

void loop() {
  xval = random(0,16383);
  switch (xval) {
  case 0:
  yval = 0;
  break;
  case 1:
  yval = 4;
  break;
  case 2:
  yval = 4;
  break;
  case 3:
  yval = -60;
  ...
  case 16383:
  yval = 1023;
  break;
}
}

Однако я не пробовал, действительно ли это работает, так что, возможно, компилятор слишком много оптимизирует.

EDIT 2: добавлена строка Serial.println(yval);, чтобы я действительно что-то делал с yval, как прокомментировал Маженко. А теперь не компилируется :'( :'( :'(

Поэтому я решу свою проблему другим способом.

, 👍0

Обсуждение

Если у вас нет места для массива, почему вы думаете, что сможете хранить те же (или больше) данные в том же пространстве?, @Majenko

Итак, если у вас нет какой-то формулы или алгоритма, вы действительно написали 16384 числа от руки? Обычно существует какой-то алгоритм, который также может быть реализован в Arduino., @chrisl

Ха-ха, нет, я не писал их вручную, я собирал данные с помощью автоматизированного процесса., @user2268171

Вы говорите, что не можете использовать формулу. Так что означает случайный вход и случайный выход? Хорошо, нет, в этом случае вы просто можете сократить размер. Если нет, вы должны быть в состоянии использовать формуляр. В противном случае это вообще не имеет никакого смысла. Не могли бы вы подробнее объяснить, чего именно нужно добиться? Что это за 14-битные числа и как они связаны с 10-битным выводом?, @Wolfram

Вы можете хранить эту таблицу во внешнем хранилище. Что-то вроде EEPROM или SD-карты., @Gerben


2 ответа


Лучший ответ:

2

214 — 16 384 записи. Каждая запись занимает 2 байта. Это 32768 байт. Это все флэш-память ATMega328P.

Наиболее эффективным хранилищем будет массив во флэш-памяти, который займет все 100 %. Использование переключателя займет больше места.

Итак, вкратце: нет. Просто нет. Это не сработает, что бы вы ни пытались. Вам нужно придумать радикально другое решение для хранения (внешняя флэш-память?) или использовать более крупный чип.


Кроме того, с помощью "битовой упаковки" вы можете уменьшить объем хранилища до 20 480 байт, но поиск данных в этих упакованных данных (4 10-битных записи, занимающих 5 байтов) будет медленным, поскольку вы нужно точно определить, какая комбинация битов и байтов вам нужна для восстановления вашего 10-битного значения.

,

Я мог бы каким-то образом сжать массив. В массиве много дубликатов, поэтому количество уникальных значений намного меньше 16384., @user2268171

Что вы делаете, что нуждается в такой огромной таблице поиска?, @Majenko

Короче говоря, адаптер, который обращает некоторое преобразование значений, происходящее в программном обеспечении., @user2268171

Почему Arduino отлично компилирует код? Я протестировал длинный оператор switch из 16384 случаев, и он говорит, что использует только 1000 байтов. Я отредактирую свой вопрос, чтобы включить это., @user2268171

Если вы на самом деле ничего не делаете с yval, компилятор оптимизирует весь этот код., @Majenko

Черт возьми, ты абсолютно прав! :'(, @user2268171

Всегда можно перейти на плату на основе 1284P с флэш-памятью 128K, которая легко будет содержать большую таблицу поиска в PROGMEM., @CrossRoads


0

Почти наверняка нет

Компиляторы часто оптимизируют операторы switch, используя таблицы перехода. Однако записи в таблице переходов в основном составляют справочную таблицу с 214 записями! Так что вы ничего не получаете.

Некоторые идеи по сжатию

  • Вы можете использовать битовую упаковку

Если ваши числа не имеют 8-битного размера, вы можете упаковать их вместе. Например, если вам удалось закодировать что-то в 6-байтовых фрагментах, вы можете сжать 4 из этих фрагментов в 3 байта, чтобы уменьшить таблицу на 25% (за счет некоторых битовых сдвигов при извлечении записей).

  • Используйте частоту дубликатов

Вы говорите, что у вас есть дубликаты. Но сколько «очень распространенных» дубликаты есть?

Если, скажем, 90 % ваших значений поступают из группы из 15 возможных значений, вы можете упаковать 2 записи на байт, каждая из которых представлена значением от 0 до 14. Если одна из записей равна 15, то это значение является "исключением". и выполняется бинарным поиском во второй таблице.

В результате получится таблица размером 8 КБ плюс размер другой таблицы (скажем, 4 КБ, если вы упаковываете 14-битный индекс и 10-битное значение в 3 байта).

Если вместо этого у вас есть набор из 254 возможных "общих" значения, то ваша основная таблица будет больше похожа на 16 КБ. Это может быть выполнимым.

  • Существует ли какая-либо связь между вводом и выводом?

Возможно, формулы нет, но могут быть свойства входных данных, влияющие на свойства выходных данных. (Например, большинство входных значений от 0 до 1024 имеют выходные значения, аналогичные плюс-минус 30.)

  • Напишите программу для поиска закономерностей в ваших данных.

Не используйте только глаза. Напишите скрипт (на Python?) для подсчета частоты каждого выходного значения, или сравнения входных данных с выходными, или оценки ваших подозрений относительно данных. График ввода и вывода.

,