Формально пусть s ( U , Q ) = { V | V ∈ U и V ⊆ Q }, где U , Q и V представляют наборы, а U , более конкретно, представляет набор множеств. Для примера, U может быть набором (наборов) ингредиентов, необходимых для различных рецептов в кулинарной книге, где Q представляет набор ингредиентов, которые у меня есть, V представляет рецепт, который я мог бы сделать с этими ингредиентами. Запрос s ( U , Q) соответствует вопросу "Что все можно сделать с этими ингредиентами?"
То, что я ищу, - это представление данных, которое индексирует U таким образом, что оно поддерживает эффективные запросы s ( U , Q ), где Q и все члены U , как правило, будут небольшими по сравнению с объединением всех членов U , Кроме того, я хотел бы, чтобы он мог эффективно обновлять U (например, добавлять или удалять рецепт).
Я не могу не думать, что эта проблема должна быть хорошо понята, но я не смог найти название или ссылку на нее. Кто-нибудь знает стратегию для эффективного решения этой проблемы или место, где я могу прочитать больше об этом?
Насколько думать о решении, один думал , что я должен был построить дерево решений для множества U . На каждом узле дерева возникает вопрос "содержит ли ваш список ингредиентов х ?" будет задан вопрос с выбранным x, чтобы максимизировать количество членов U, которые будут исключены ответом. По мере обновления U это дерево решений должно быть перебалансировано, чтобы минимизировать количество вопросов, необходимых для получения правильного результата. Другая мысль состоит в том, чтобы представлять U чем-то вроде n- мерного логического «октри» (где n - число уникальных ингредиентов).
Я считаю, что «Какие рецепты можно сделать с этими ингредиентами?» можно ответить, взяв декартово произведение (наборов ингредиентов, необходимых для) рецептов в кулинарной книге с набором ингредиентов, которые у вас есть, и отфильтровав получающиеся упорядоченные пары для пар, в которых оба элемента равны, но это не эффективное решение, и я спрашиваю о том, как оптимизировать этот вид операций; как можно составить это в SQL так, чтобы оно было эффективным, и что делает SQL, чтобы это было эффективным?
Хотя я использую иллюстрацию кулинарной книги рецептов и набора ингредиентов, я ожидаю, что количество «рецептов» и количество «ингредиентов» будет очень большим (до сотен тысяч каждый), хотя количество ингредиентов в данном рецепте количество ингредиентов в данном наборе ингредиентов будет относительно небольшим (вероятно, около 10-50 для типичного «рецепта» и около 100 для типичного «набора ингредиентов»). Кроме того, наиболее распространенной операцией будет запрос s ( U , Q ), поэтому он должен быть наиболее оптимальным. Это также означает, что алгоритм грубой силы, который требует проверки каждого рецепта или действия над каждым ингредиентом, сам по себе будет нежелательно медленным. С умным кешированием,
Ответы:
Для чисел, которые вы дали, просто перебор.
Вот программа на JavaScript, которая перебирает все 10 ингредиентов в БД, 10 рецептов в БД, каждому рецепту нужно 2 ингредиента, и у меня есть 5 ингредиентов:
Это работает в 0 миллисекунд. Я выбрал эти небольшие числа, чтобы вы могли запустить его самостоятельно пару раз и убедить себя, что он делает то, что вы хотите, и относительно свободен от ошибок.
Теперь измените его так, чтобы у нас было 1 000 000 ингредиентов в БД, 1 000 000 рецептов в БД, 50 ингредиентов на рецепт и 100 ингредиентов, доступных мне. Т.е. значения, которые все равны или больше, чем самый большой вариант использования, который вы дали.
Он работает в 125 миллисекундах под nodejs, и это самая глупая реализация без каких-либо усилий по оптимизации.
источник