Быстро определить, присутствует ли значение в массиве C?

У меня есть встроенное приложение с критичным по времени ISR, которое должно перебирать массив размером 256 (предпочтительно 1024, но 256 - минимум) и проверять, соответствует ли значение содержимому массивов. В этом boolслучае A будет установлено значение true.

Микроконтроллер - это NXP LPC4357, ядро ​​ARM Cortex M4, а компилятор - GCC. Я уже объединил уровень оптимизации 2 (3 медленнее) и поместил функцию в ОЗУ вместо флэш-памяти. Я также использую арифметику с указателями и forцикл, который выполняет обратный счет вместо увеличения (проверка i!=0выполняется быстрее, чем проверка i<256). В целом, у меня получается длительность 12,5 мкс, которую нужно резко сократить, чтобы это стало возможным. Это (псевдо) код, который я использую сейчас:

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

Каким будет самый быстрый способ сделать это? Допускается использование встроенной сборки. Допускаются и другие «менее элегантные» приемы.

В ситуациях, когда производительность имеет первостепенное значение, компилятор C, скорее всего, не создаст самый быстрый код по сравнению с тем, что вы можете сделать с помощью настроенного вручную языка ассемблера. Я предпочитаю идти по пути наименьшего сопротивления - для таких небольших подпрограмм я просто пишу asm-код и хорошо представляю, сколько циклов потребуется для выполнения. Вы можете повозиться с кодом C и заставить компилятор генерировать хороший вывод, но в конечном итоге вы можете потратить много времени на настройку вывода таким образом. Компиляторы (особенно от Microsoft) прошли долгий путь за последние несколько лет, но они все еще не так умны, как компилятор между вашими ушами, потому что вы работаете над своей конкретной ситуацией, а не только с общим случаем. Компилятор может не использовать определенные инструкции (например, LDM), которые могут ускорить это, и это ' s вряд ли будет достаточно умен, чтобы развернуть петлю. Вот способ сделать это, который включает в себя 3 идеи, которые я упомянул в моем комментарии: разворачивание цикла, предварительная выборка кеша и использование инструкции множественной загрузки (ldm). Счетчик командных циклов составляет примерно 3 такта на элемент массива, но это не учитывает задержки памяти.

Теория работы: ЦП ARM выполняет большинство инструкций за один такт, но инструкции выполняются в конвейере. Компиляторы C попытаются устранить задержки конвейера, перемежая между ними другие инструкции. При представлении жесткого цикла, такого как исходный код C, компилятору будет трудно скрыть задержки, потому что значение, считанное из памяти, должно быть немедленно сравнено. В приведенном ниже коде чередуются 2 набора из 4 регистров, чтобы значительно уменьшить задержки самой памяти и конвейера, получающего данные. В общем, при работе с большими наборами данных, когда ваш код не использует большинство или все доступные регистры, вы не получаете максимальной производительности.

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

Обновление: в комментариях есть много скептиков, которые думают, что мой опыт анекдотичен / бесполезен и требует доказательств. Я использовал GCC 4.8 (из Android NDK 9C) для генерации следующего вывода с оптимизацией -O2 (все оптимизации включены, включая разворачивание цикла ). Я скомпилировал исходный код C, представленный в вопросе выше. Вот что произвел GCC:

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

Вывод GCC не только не разворачивает цикл, но и тратит время на остановку после LDR. Для каждого элемента массива требуется не менее 8 тактов. Он хорошо использует адрес, чтобы знать, когда нужно выйти из цикла, но все волшебные вещи, которые могут делать компиляторы, в этом коде не встречаются. Я не запускал код на целевой платформе (у меня ее нет), но любой, кто имеет опыт работы с кодом ARM, может увидеть, что мой код работает быстрее.

Обновление 2: я дал Microsoft Visual Studio 2013 SP2 шанс улучшить код. Он смог использовать инструкции NEON для векторизации инициализации моего массива, но поиск линейного значения, записанный OP, получился аналогичным тому, что сгенерировал GCC (я переименовал метки, чтобы сделать его более читаемым):

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

Как я уже сказал, у меня нет точного оборудования OP, но я буду тестировать производительность на nVidia Tegra 3 и Tegra 4 из трех разных версий и вскоре опубликую здесь результаты.

Обновление 3: я запустил свой код и скомпилированный Microsoft код ARM на Tegra 3 и Tegra 4 (Surface RT, Surface RT 2). Я выполнил 1000000 итераций цикла, который не смог найти совпадение, так что все было в кеше и его легко измерить.

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns  

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

Есть трюк для его оптимизации (меня однажды спросили об этом на собеседовании):

• Если последняя запись в массиве содержит искомое значение, верните true.
• Запишите значение, которое вы ищете, в последнюю запись в массиве
• Итерируйте по массиву, пока не найдете искомое значение.
• Если вы столкнулись с ним перед последней записью в массиве, верните true
• Вернуть ложь

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

Это дает одну ветвь на итерацию вместо двух ветвей на итерацию.

ОБНОВИТЬ:

Если вам разрешено выделить массив SIZE+1, то вы можете избавиться от части «подкачки последней записи»:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

Вы также можете избавиться от дополнительной встроенной арифметики theArray[i], используя вместо этого следующее:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

Если компилятор еще не применил его, то эта функция обязательно сделает это. С другой стороны, это может усложнить оптимизатору развертывание цикла, поэтому вам придется проверить, что в сгенерированном коде сборки ...

Вы просите помощи в оптимизации вашего алгоритма, что может подтолкнуть вас к ассемблеру. Но ваш алгоритм (линейный поиск) не такой умный, поэтому вам следует подумать об изменении своего алгоритма. Например:

• идеальная хеш-функция
• бинарный поиск

Идеальная хеш-функция

Если ваши 256 "действительных" значений статичны и известны во время компиляции, вы можете использовать идеальную хеш-функцию . Вам нужно найти хеш-функцию, которая сопоставляет ваше входное значение со значением в диапазоне 0..n , где нет конфликтов для всех допустимых значений, которые вам нужны . То есть нет двух "действительных" значений хеширования с одним и тем же выходным значением. При поиске хорошей хеш-функции вы стремитесь:

• Держите хэш-функцию достаточно быстрой.
• Свернуть n . Наименьшее, что вы можете получить, - это 256 (минимальная идеальная хеш-функция), но этого, вероятно, трудно достичь, в зависимости от данных.

Обратите внимание, что для эффективных хэш-функций n часто является степенью 2, что эквивалентно побитовой маске младших битов (операция И). Примеры хэш-функций:

• CRC входных байтов по модулю n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(сбор , как многие i, j, k, ... по мере необходимости, с левыми или правыми сдвигами)

Затем вы составляете фиксированную таблицу из n записей, в которой хэш сопоставляет входные значения с индексом i в таблице. Для допустимых значений запись таблицы i содержит допустимое значение. Для всех остальных записей в таблице, убедитесь , что каждая запись индекса я содержит некоторые другие недопустимое значение , которое не делает хэш I .

Затем в вашей программе прерывания с вводом x :

1. Хешировать x до индекса i (который находится в диапазоне 0..n)
2. Найдите запись i в таблице и посмотрите, содержит ли она значение x .

Это будет намного быстрее, чем линейный поиск 256 или 1024 значений.

Я написал код Python, чтобы найти разумные хеш-функции.

Бинарный поиск

Если вы отсортируете массив из 256 «допустимых» значений, то вы сможете выполнять двоичный поиск , а не линейный поиск. Это означает, что вы сможете выполнить поиск в таблице из 256 записей всего за 8 шагов ( log2(256)) или в таблице из 1024 записей за 10 шагов. Опять же, это будет намного быстрее, чем линейный поиск 256 или 1024 значений.

Сохраняйте таблицу в отсортированном порядке и используйте развернутый двоичный поиск Bentley:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

Дело в том,

• если вы знаете, насколько велика таблица, значит, вы знаете, сколько итераций будет, поэтому вы можете полностью развернуть ее.
• Тогда нет смысла тестировать == случай на каждой итерации, потому что, за исключением последней итерации, вероятность этого случая слишком мала, чтобы оправдать затраты времени на его тестирование. **
• Наконец, расширяя таблицу до степени 2, вы добавляете не более одного сравнения и не более двух хранилищ.

** Если вы не привыкли думать в терминах вероятностей, каждая точка принятия решения имеет энтропию , которая представляет собой среднюю информацию, которую вы получаете, выполняя ее. Для >=тестов вероятность каждой ветви составляет около 0,5, а -log2 (0,5) - 1, это означает, что если вы возьмете одну ветвь, вы изучите 1 бит, а если вы выберете другую ветвь, вы изучите один бит, а средний это просто сумма того, что вы узнали по каждой ветке, умноженная на вероятность этой ветки. Итак 1*0.5 + 1*0.5 = 1, энтропия >=теста равна 1. Поскольку вам нужно изучить 10 бит, потребуется 10 ветвей. Вот почему это быстро!

С другой стороны, что если ваш первый тест if (key == a[i+512)? Вероятность того, что это правда, составляет 1/1024, а вероятность ложной - 1023/1024. Так что, если это правда, вы выучите все 10 бит! Но если это неверно, вы узнаете -log2 (1023/1024) = 0,00141 бит, практически ничего! Так что в среднем вы узнаете из этого теста 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112биты. Примерно сотую долю бита. Этот тест не выдерживает критики!

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

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

Идеальное хеширование - это схема «максимум 1 зонд». Можно обобщить эту идею, полагая, что нужно обменять простоту вычисления хэш-кода на время, необходимое для создания k зондов. В конце концов, цель - «наименьшее общее время для поиска», а не наименьшее количество проб или простейшая хеш-функция. Однако я никогда не видел, чтобы кто-нибудь создавал алгоритм хеширования k-probes-max. Я подозреваю, что это можно сделать, но это скорее всего исследование.

Еще одна мысль: если ваш процессор чрезвычайно быстр, одна проба в память с идеальным хешем, вероятно, доминирует во времени выполнения. Если процессор не очень быстрый, можно использовать k> 1 зондов.

Используйте хеш-набор. Это даст время поиска O (1).

В следующем коде предполагается, что вы можете зарезервировать значение 0как «пустое» значение, то есть не встречающееся в реальных данных. Решение может быть расширено для ситуации, когда это не так.

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

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

В этом случае, возможно, стоит изучить фильтры Блума . Они способны быстро установить, что значение отсутствует, и это хорошо, поскольку большинство из 2 ^ 32 возможных значений не входят в этот массив из 1024 элементов. Однако есть некоторые ложные срабатывания, которые потребуют дополнительной проверки.

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

Предполагая, что ваш процессор работает на частоте 204 МГц, что кажется максимумом для LPC4357, а также предполагая, что ваш результат синхронизации отражает средний случай (половина пройденного массива), мы получаем:

• Частота процессора: 204 МГц
• Период цикла: 4,9 нс
• Продолжительность в циклах: 12,5 мкс / 4,9 нс = 2551 цикл
• Циклов на итерацию: 2551/128 = 19,9

Итак, цикл поиска тратит около 20 циклов на итерацию. Звучит не ужасно, но я думаю, что для того, чтобы ускорить работу, нужно посмотреть на сборку.

Я бы порекомендовал отбросить индекс и вместо этого использовать сравнение указателей и создать все указатели const.

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

По крайней мере, это стоит проверить.

Другие предлагали реорганизовать вашу таблицу, добавить в конце контрольное значение или отсортировать ее, чтобы обеспечить бинарный поиск.

Вы заявляете: «Я также использую арифметику с указателями и цикл for, который выполняет обратный счет вместо увеличения (проверка i != 0выполняется ли быстрее, чем проверка i < 256)».

Мой первый совет: избавьтесь от арифметики указателя и обратного счета. Такие вещи как

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

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

Например, приведенный выше код может быть скомпилирован в цикл, идущий от нуля -256или -255до нуля, без индексации &the_array[256]. Возможно, что-то, что даже не может быть выражено на действительном языке C, но соответствует архитектуре машины, для которой вы создаете.

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

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

Здесь можно использовать векторизацию, как это часто бывает в реализациях memchr. Вы используете следующий алгоритм:

1. Создайте маску повторения вашего запроса, равную по длине количеству бит вашей ОС (64-битная, 32-битная и т. Д.). В 64-битной системе вы должны повторить 32-битный запрос дважды.

2. Обработайте список как список из нескольких частей данных одновременно, просто преобразовав список в список большего типа данных и вытащив значения. Для каждого фрагмента выполните XOR с маской, затем XOR с 0b0111 ... 1, затем добавьте 1, затем & с маской 0b1000 ... 0, повторяя. Если результат равен 0, совпадения точно нет. В противном случае (обычно с очень высокой вероятностью) совпадение может быть, поэтому ищите фрагмент обычным образом.

Пример реализации: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

Если вы можете вместить область своих значений с объемом памяти, доступной вашему приложению, то самым быстрым решением было бы представить ваш массив как массив бит:

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

РЕДАКТИРОВАТЬ

Я поражен количеством критиков. Заголовок этой темы: «Как мне быстро определить, присутствует ли значение в массиве C?» на что я буду стоять на своем ответе, потому что он отвечает именно на это. Я могу утверждать, что это самая эффективная хэш-функция по скорости (поскольку значение address ===). Я прочитал комментарии и осознаю очевидные предостережения. Несомненно, эти предостережения ограничивают круг проблем, которые можно использовать для решения, но те проблемы, которые он решает, он решает очень эффективно.

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

Убедитесь, что инструкции («псевдокод») и данные («theArray») находятся в отдельных (RAM) памяти, чтобы архитектура CM4 Harvard использовалась в полной мере. Из руководства пользователя:

Для оптимизации производительности процессора ARM Cortex-M4 имеет три шины для доступа к инструкциям (код) (I), доступа к данным (D) и доступа к системе (S). Когда инструкции и данные хранятся в отдельных запоминающих устройствах, тогда доступ к коду и данным может выполняться параллельно в одном цикле. Когда код и данные хранятся в одной и той же памяти, инструкции по загрузке или сохранению данных могут занять два цикла.

Извините, если на мой ответ уже был дан ответ - просто я ленивый читатель. Тогда не стесняйтесь голосовать против))

1) вы можете вообще удалить счетчик i - просто сравните указатели, т.е.

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

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

2) Как уже упоминалось в других ответах, почти все современные процессоры основаны на RISC, например ARM. Насколько мне известно, даже современные процессоры Intel X86 используют внутри ядра RISC (компиляция из X86 на лету). Основная оптимизация для RISC - это оптимизация конвейера (а также для Intel и других ЦП), сводящая к минимуму скачки кода. Один из видов такой оптимизации (возможно, основной) - это «откат цикла». Это невероятно глупо и эффективно, даже компилятор Intel может сделать это AFAIK. Это выглядит как:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

Таким образом, оптимизация заключается в том, что конвейер не нарушается в худшем случае (если compareVal отсутствует в массиве), поэтому он выполняется как можно быстрее (конечно, не считая оптимизаций алгоритмов, таких как хэш-таблицы, отсортированные массивы и т. Д., упомянутые в других ответах, которые могут дать лучшие результаты в зависимости от размера массива. Кстати, там также может применяться подход Cycles Rollback. Я пишу здесь об этом, я думаю, что не видел в других)

Вторая часть этой оптимизации заключается в том, что этот элемент массива берется по прямому адресу (вычисленному на этапе компиляции, убедитесь, что вы используете статический массив), и не требует дополнительной операции ADD для вычисления указателя из базового адреса массива. Эта оптимизация может не иметь значительного эффекта, поскольку архитектура AFAIK ARM имеет специальные функции для ускорения адресации массивов. Но в любом случае всегда лучше знать, что вы сделали все самое лучшее непосредственно в коде на C, верно?

Cycle Rollback может выглядеть неудобно из-за траты ПЗУ (да, вы правильно разместили его в быстрой части ОЗУ, если ваша плата поддерживает эту функцию), но на самом деле это честная плата за скорость, поскольку она основана на концепции RISC. Это всего лишь общий момент оптимизации вычислений - вы жертвуете пространством ради скорости и наоборот, в зависимости от ваших требований.

Если вы считаете, что откат для массива из 1024 элементов - слишком большая жертва для вашего случая, вы можете рассмотреть вариант «частичного отката», например разделение массива на 2 части по 512 элементов каждая или 4x256 и т. Д.

3) современные CPU часто поддерживают SIMD-операции, например, набор инструкций ARM NEON - это позволяет выполнять одни и те же операции параллельно. Честно говоря, я не помню, подходит ли он для сравнения, но чувствую, что может, вы должны это проверить. Поиск в Google показывает, что для получения максимальной скорости также могут быть некоторые уловки, см. Https://stackoverflow.com/a/5734019/1028256

Я надеюсь, что это может дать вам новые идеи.

Я большой поклонник хеширования. Проблема, конечно, заключается в том, чтобы найти эффективный алгоритм, который был бы быстрым и потреблял бы минимальный объем памяти (особенно на встроенном процессоре).

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

Я создал такую ​​программу, о которой вы можете прочитать в этом посте, и добился очень быстрых результатов. 16000 записей переводятся примерно в 2 ^ 14 или в среднем 14 сравнений, чтобы найти значение с помощью двоичного поиска. Я явно стремился к очень быстрому поиску - в среднем нахождение значения в <= 1,5 поисков - что привело к большим требованиям к ОЗУ. Я считаю, что при более консервативном среднем значении (скажем, <= 3) можно сэкономить много памяти. Для сравнения, средний случай двоичного поиска по вашим 256 или 1024 записям приведет к среднему количеству сравнений 8 и 10 соответственно.

Мой средний поиск требовал около 60 циклов (на ноутбуке с Intel i5) с общим алгоритмом (с использованием одного деления на переменную) и 40-45 циклов со специализированным (возможно, с использованием умножения). Это должно привести к субмикросекундному времени поиска на вашем MCU, конечно, в зависимости от тактовой частоты, на которой он работает.

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

Это больше похоже на дополнение, чем на ответ.

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

В половине из них искомое значение НЕ присутствовало в массиве. Тогда я понял, что могу применить «фильтр» перед любым поиском.

Этот «фильтр» представляет собой простое целое число, которое рассчитывается ОДИН РАЗ и используется при каждом поиске.

Это на Java, но довольно просто:

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i];
}

Итак, перед бинарным поиском я проверяю бинарный фильтр:

// Check binaryfilter vs value with a "Binary AND Operator"
if ((binaryfilter & valuetosearch) != valuetosearch)
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

Вы можете использовать «лучший» алгоритм хеширования, но он может быть очень быстрым, особенно для больших чисел. Может быть, это поможет вам сэкономить еще больше циклов.