Как эффективно найти все объекты, у которых в названии есть все заданные слова?
Входные данные
Допустим у меня есть массив магазинов. Магазин это объект, где есть поле name с названием магазина, например: {name: "Строительный магазин", id: 141, ...}. Магазинов тысячи. Еще у меня есть массив, состоящий из комбинаций двух слов, например: [["строительный", "краски"], ["ремонта", "всё"], ["профессионал", "инструмент"]]. Задача
Надо найти все магазины, где в названии встречаются оба слова из какой-нибудь комбинации.
Решение в лоб - это сделать цикл по комбинациям и для каждой комбинации перебирать весь массив магазинов, но наверняка есть более оптимальное решение.
Конечно, есть. Можно увеличить скорость за счёт использования памяти.
Например, можно сделать ассоциативный массив (словарь, хеш-таблица), в котором ключами будут отдельные слова ("строительный", "ремонта" и т.д.), а значениями будут списки магазинов, в которых данный ключ встречается. Тогда при поиске очередной пары слов нужно будет выделить два коротеньких списка и перебрать их, найдя общие элементы (т.е. магазины, в названии которых сразу оба слова).
Если подумать, можно ещё что-нибудь наоптимизировать. Но это уже надо знать больше нюансов конкретно вашей задачи.
Тут же можно за один проход по магазинам. Сначала пройдитесь по вашим комбинациям и сложите слова в хешмап "слово" -> список номеров пар, в которых оно есть.
Потом для каждого магазина пометьте массив длиной сколько у вас пар тегов нулями. Потом по каждому слову пройдитесь и добавьте 1 к каждой паре в массив, в которой это слово всречается, используя мап из предыдущего пункта. Если где-то получили 2 в процессе, то этот магазин вам подходит.
Если же вы можете один раз что-то предподсчитать для всех магазинов, то потом можно выполнять "запросы" даже не проходясь по всем магазинам.
Можно по каждому тегу составить список магазинов, имеющих его в названии, упорядоченный как-то (допустим, по id магазинов). Эту структуру можно построить за один проход по всем магазинам и сохранить.
Затем ваш запрос на пар тегов можно обрабатывать объеденяя и пересекая упорядоченные списки. Эти операции, как в сортировке слиянием, делаются за один проход по списку.
В хужшем случае, где используется очень частый тег, обработка запроса будет почти как полный просмотр всех магазинов (даже если в ответ попадет их малая часть), но в среднем этот метод будет работать неплохо.
Проход по магазинам, каждое название разбивается на слова, для каждого слова находится базовая морфологическая форма. Сохраняем записи (id магазина - id слова). В поиске по парам тоже приводим оба слова к базе. Вам же все равно надо будет не "строительство, краски", а все возможные склонения этих слов. А уж выборка "найти записи, где не меньше двух строк с совпадением по ключу" - элементарно.
Средний
