Быстрый поиск в текстовом массиве. ESP8266

forfrends
Offline
Зарегистрирован: 24.02.2015

Всем привет! Столкнулся с задачей и ищу вашей помощи в оптимальном ее решении.

Есть на MicroSD текстовый массив примерно такого вида:

Car,convertible
Tree,pear
Animal,horse
Phone,880075030
...
House,manor

Массив очень большой. До нескольких мегабайт может доходить. По этому считать в оперативку не получится. Слова (и их длинна) абсолютно разные. Только латиница + символы и цифры. Без пробелов. Каждая пара слов начинается с новой строки. Слова в паре разделены запятой. Необходимо имея первое слово, получить второе. Допустим, ESP получит слово "Tree", а в ответ выдаст "pear". Простым перебором это не хочется. Будет очень долго. Тем более если на запросе будет висеть сразу несколько слов...

Может есть какой-то алгоритм быстрого поиска по текстовому файлу?

rkit
Offline
Зарегистрирован: 23.11.2016

forfrends пишет:

Будет очень долго.

Это сколько? Ты хотя бы примерно посчитал перед тем как сказать?

Nosferatu
Offline
Зарегистрирован: 04.11.2012

В идеале, массив надо хранить сортированным.

Тогда например можно сохранить индексы, где меняется первый символ слова.

То есть будет известно, от и до какого индекса слова начинаются на символ 'Т', только там и искать слово "Tree"

forfrends
Offline
Зарегистрирован: 24.02.2015

Nosferatu, Так было бы идеально. Но, увы, массив не сортированный + постоянно пополняется (дописывается с конца). 

Nosferatu
Offline
Зарегистрирован: 04.11.2012

А сортировать на "лету" совсем не как? Для каждого начального символа свой участок памяти.

DetSimen
DetSimen аватар
Offline
Зарегистрирован: 25.01.2017

forfrends пишет:

Nosferatu, Так было бы идеально. Но, увы, массив не сортированный + постоянно пополняется (дописывается с конца). 

Индексируй.  Или отсортируй сразу и вставляй дописки в правильное место. 

DIYMan
DIYMan аватар
Offline
Зарегистрирован: 23.11.2015

Дед всё правильно посоветовал - надо индексировать при вставке новой записи, и усё. Если серьёзно настроены на быстродействие - теории по устройству БД в сети - тонны, можно ознакомиться.

А ещё - можно ввести в гугле волшебную фразу "esp8266 sqlite" - и посмотреть, что уже всё украдено до нас. Тоисть, уже можно и под ESP работать с БД, с блекджеком и... Всяко быстрее будет работать, чем самописный поиск. Плюсом - кучу возможностей, на вырост.

rkit
Offline
Зарегистрирован: 23.11.2016

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