Я довольно плохо знаком со структурами данных, но я пытался реализовать эффективную функцию поиска города / автозаполнения города на серверной части моего приложения (экспресс-сервер nodeJS).
Первоначально я был толькозагрузка в память множества городов (которых было около 20 000 городов);Я бы позволил своему клиентскому приложению искать город через конечную точку /search и возвращать им список городов, которые соответствовали бы поиску пользователя:
import cities from './cities.json';
// Search endpoint
app.get('/search', (req, res) => {
const results = [];
const searchKey = req.body.key.toLowerCase();
for (let city of cities) {
if (city.toLowerCase().contains(searchKey)) {
results.push(city);
// Max 10 cities
if (results.length > 10) {
break;
}
}
}
res.json(cities);
});
Хотя это работает быстро, потому что у меня только 20 000 городовЯ предполагаю, что это довольно плохо с точки зрения сложности времени, поскольку сложность наихудшего случая равна O(n).
Так что я думал о реализации словаря на основе суффиксного дерева, чтобы поиск ключа имел сложностьO(m), m длина ключа (поправьте меня, если я ошибаюсь) за счет более высокой сложности пространства.
Но, как я уже сказал, я немного новичок во всехвот мои вопросы:
1) Что обычно делается для реализации функции быстрого автозаполнения?
2) Было бы лучше, еслиЯ храню мои города в базе данных SQL?Есть ли способ эффективно настроить таблицу базы данных для быстрого поиска на основе суффиксов?
Заранее спасибо!