Индексирование текстового файла для микроконтроллера

Question

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

Список выглядит так:

BSSID,data1,data2
001122334455,float,float
001122334466,float,float
...

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

То, что я сделал до сих пор, очень упрощено.
Я создал индекс первого байтаBSSID и указывает на первое и последнее значения с этим префиксом BSSID.

Производительность ужасная, но индексный файл очень маленький и использует очень мало оперативной памяти.Я хотел бы пойти дальше с этим методом, взглянув на первые два байта, но индексная таблица будет в 256 раз больше, в результате чего получится таблица размером 1/3 файла данных.

Этоиндекс с первым методом:

00,0000000000,0000139984
02,0000139984,0000150388
04,0000150388,0000158812
06,0000158812,0000160900
08,0000160900,0000171160

Какой алгоритм индексации вы предлагаете мне использовать?

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

Извините, я не сделал 'До этого достаточно включить фон.
Я храню данные и индексный файл на флэш-памяти чипа.На данный момент у меня есть 30000 записей, но это число может расти до тех пор, пока не будет достигнут предел мимерности фишек.Этот набор действительно статичен, когда хранится на микроконтроллере, но может быть обновлен во второй момент с помощью компьютера.
Данные не распределяются симметрично между индексами.
Моя цель - найти хороший компромиссмежду скоростью поиска, размером индекса и используемой оперативной памятью.

Answer 1

Не уверен, сколько памяти у вас есть (я не знаком с этим MCU), но не забывайте, что эти таблицы являются статическими / постоянными, поэтому они могут храниться в EEPROM вместо RAM некоторые чипы имеют довольно много EEPROM обычно намного больше чем RAM ...

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

BYTE ix, DWORD beg,DWORD end

Почему бы не это:

struct entry { DWORD beg,end };
entry ix0[256];

Где первый BYTE также является адресом в массиве индекса.Это сэкономит 1 байт на каждую запись. Теперь, как Prune предлагает вам игнорировать конечный адрес, так как вы все равно будете сканировать следующие записи в файле, пока не достигнете правильного индекса или индекса с другим первым BYTE.поэтому вы можете использовать:

DWORD ix[256];

, где у вас есть только начальный адрес beg.

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

Вы хотели сделать что-то вроде:

DWORD ix[65536];

Но недостаточно памяти для этого ... как насчет того, чтобы сделать что-то вродевместо этого:

const N=1024; // number of entries you can store
const dix=(max_index_value+1)/N;
const ix[N]={.....};

, поэтому каждая запись ix[i] будет охватывать все индексы от i*dix до ((i+1)*dix)-1.Чтобы найти index, вы делаете это:

i = ix[index/dix];
for (;i<file_size;)
 {
 read entry from file at i-th position;
 update position i;
 if (file_index==index) { do your stuff; break; }
 if (file_index> index) { index not found;  break; }
 }

Для повышения производительности вы можете переписать это линейное сканирование в двоичный поиск между адресами ix[index/dix] и ix[(index/dix)+1] или размером файла для последнего индекса.... при условии, что каждая запись в файле имеет одинаковый размер ...

Answer 2

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

Прежде всего, способ определить "лучший""метод заключается в

• определении" наилучшего "для ваших целей;
• алгоритмов индексации исследований (основные из которых были опубликованы более 50 лет);
• выберитегорстка для реализации;
• Оцените эти реализации в соответствии с вашим определением "best".

Имейте в виду ваше основное ограничение ресурсов: у вас ограничено ОЗУ.Если метод требует больше оперативной памяти, чем у вас, он не работает, и поэтому он на бесконечно медленнее, чем любой метод, который работает.

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

---

Индексированиесоображения

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

Получите ли вы более высокую производительность, если разделите файл на равные части (одинаковое количество BSSIDS для каждой строкиваша таблица), а затем сохранить весь начальный BSSID с его номером записи?Если ваши BSSID сильно сгруппированы, это может улучшить общую обработку, даже если в вашей таблице меньше строк.Вы не можете использовать прямой индекс в этом случае;вам нужно поискать в первом столбце, чтобы получить правильную отправную точку.

---

Приводит ли это вас к хорошему решению?