Fla sh строка поиска в памяти - PullRequest
Новая
       96

Fla sh строка поиска в памяти

0 голосов
/ 27 апреля 2020

Fla sh память используется для регистрации кадра: данные $ D, ошибка $ E и отчет $ R и еще немного. Каждый кадр имеет метку времени после типа кадра: $ D, Метка времени ......... $ E. Все данные в шестнадцатеричном формате и переменной длины, ie 0 = 0, 1587912486 = 5EA59F26, это не фиксированная длина кадра. Отметка времени - UDT1970.

Примечание: в Fla sh каждая страница имеет размер 256 байт.

До сих пор я начинал с центральной страницы между начальной и конечной страницами, где на этой странице он ищет (с помощью совпадения $ D) ) и считывает метку времени (читая fla sh byte byte byte в массив до тех пор, пока не будет обнаружено ',') в начале каждой страницы. если временная метка меньше или превышает целевую временную метку, она переходит на следующую половину номера страницы (шаг) и повторяется до тех пор, пока шаг не переходит к 1. Затем я возвращаюсь на одну страницу назад и выполняю байтовый поиск для временной метки вверх, пока не будет найдено фактическое соответствие. Это два процесса: поиск с переходом по страницам и затем побайтовый поиск.

Мне любопытно, существует ли подобный алгоритм с указанным именем c или более лучший алгоритм, оптимизированный для поиска в памяти Fla sh. NB. У меня есть ограничение в использовании SRAM, ie передача в большой буфер невозможна.

1 Ответ

1 голос
/ 01 мая 2020

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

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

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

Например, вы можете сохранить индекс с быстрым поиском, хранящий отметку времени + index (просто массив для бинарного или интерполяционного поиска, или дерево, или список пропусков, или что-то еще). Затем у вас будет быстрый поиск с фиксированными смещениями и косвенное обращение к данным переменного размера.

...