Официальный сайт компании Arduino по адресу arduino.cc
Быстрый поиск в текстовом массиве. ESP8266
- Войдите или зарегистрируйтесь, чтобы получить возможность отправлять комментарии
Пнд, 25/05/2020 - 02:15
Всем привет! Столкнулся с задачей и ищу вашей помощи в оптимальном ее решении.
Есть на MicroSD текстовый массив примерно такого вида:
Car,convertible
Tree,pear
Animal,horse
Phone,880075030
...
House,manor
Массив очень большой. До нескольких мегабайт может доходить. По этому считать в оперативку не получится. Слова (и их длинна) абсолютно разные. Только латиница + символы и цифры. Без пробелов. Каждая пара слов начинается с новой строки. Слова в паре разделены запятой. Необходимо имея первое слово, получить второе. Допустим, ESP получит слово "Tree", а в ответ выдаст "pear". Простым перебором это не хочется. Будет очень долго. Тем более если на запросе будет висеть сразу несколько слов...
Может есть какой-то алгоритм быстрого поиска по текстовому файлу?
Будет очень долго.
Это сколько? Ты хотя бы примерно посчитал перед тем как сказать?
В идеале, массив надо хранить сортированным.
Тогда например можно сохранить индексы, где меняется первый символ слова.
То есть будет известно, от и до какого индекса слова начинаются на символ 'Т', только там и искать слово "Tree"
Nosferatu, Так было бы идеально. Но, увы, массив не сортированный + постоянно пополняется (дописывается с конца).
А сортировать на "лету" совсем не как? Для каждого начального символа свой участок памяти.
Nosferatu, Так было бы идеально. Но, увы, массив не сортированный + постоянно пополняется (дописывается с конца).
Индексируй. Или отсортируй сразу и вставляй дописки в правильное место.
Дед всё правильно посоветовал - надо индексировать при вставке новой записи, и усё. Если серьёзно настроены на быстродействие - теории по устройству БД в сети - тонны, можно ознакомиться.
А ещё - можно ввести в гугле волшебную фразу "esp8266 sqlite" - и посмотреть, что уже всё украдено до нас. Тоисть, уже можно и под ESP работать с БД, с блекджеком и... Всяко быстрее будет работать, чем самописный поиск. Плюсом - кучу возможностей, на вырост.
Это делается хеш-таблицей. Делаем, скажем, 64 файла, каждый соответствует своему хеш-числу. Снимаем со строки хеш, пишем в конец соотвествующего файла. При выборке перебираем только файл с хешем, соответсвующим искомой строке. Получается прирост почти в 64 раза. Но, как я уже выше писал, это всё преждевременная оптимизация, так же известная как корень всех зол.