Алгоритм / структура данных, чтобы ответить «какие рецепты я могу сделать с этим набором ингредиентов?»

11

Формально пусть s ( U , Q ) = { V | VU и VQ }, где 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 ), поэтому он должен быть наиболее оптимальным. Это также означает, что алгоритм грубой силы, который требует проверки каждого рецепта или действия над каждым ингредиентом, сам по себе будет нежелательно медленным. С умным кешированием,

nben
источник
1
Проблема, которая должна быть легко решаема с базой данных SQL.
Роберт Харви
1
Исходя из вашего дополнительного описания, это звучит как проблема масштаба Орбитца. Поисковая система Orbitz использует движок Lisp, который просматривает около миллиарда точек данных, чтобы получить список рейсов, которые подойдут для вашего конкретного маршрута. Нефункциональным требованием является то, что оно должно вернуть решение в течение 10 секунд или меньше. Смотрите здесь paulgraham.com/carl.html , хотя обратите внимание, что информация довольно старая.
Роберт Харви
Этот вопрос довольно широкий и состоит из двух частей: структуры данных и алгоритма поиска существующих рецептов, которые являются подмножествами ингредиентов, и того, как масштабировать их для больших данных. Я считаю, что это должно быть два вопроса. Вы не можете реально обратиться к большой части данных, пока не сузите часть алгоритма. user16054 уже получил справку о том, как таблицы соединений используются в представлении реляционной базы данных. Если этот вопрос сужен до части алгоритма / структуры данных или был задан другой независимый вопрос, я мог бы предложить свои предложения.
скалистая

Ответы:

4

Для чисел, которые вы дали, просто перебор.

Вот программа на JavaScript, которая перебирает все 10 ингредиентов в БД, 10 рецептов в БД, каждому рецепту нужно 2 ингредиента, и у меня есть 5 ингредиентов:

var i, j;
var numIngredients = 10;
var numRecipes = 10;
var numIngredientsPerRecipe = 2;
var numIngredientsInQuery = 5;

function containsAll(needles, haystack){ 
  var i, len;
  for(i = 0 , len = needles.length; i < len; i++){
      if(haystack.indexOf(needles[i]) == -1) {
          return false;
      }
  }
  return true;
}

// Set up a fake DB of recipes
var ingredients = [];
for (i = 0; i < numIngredients; i++) {
    ingredients.push(i);
}
console.log('Here are the ingredients:', ingredients);

var recipes = [];
for (i = 0; i < numRecipes; i++) {
    var neededIngredients = [];
    for (j = 0; j < numIngredientsPerRecipe; j++) {
        neededIngredients.push(Math.floor(Math.random() * numRecipes));
    }
    recipes.push({ recipeId: i, needed: neededIngredients});
}
console.log('Here are the recipes:', recipes);

// Set up a fake query
var ingredientsAvailable = [];
for (i = 0; i < numIngredientsInQuery; i++) {
    ingredientsAvailable.push(Math.floor(Math.random() * numRecipes));
}

console.log("Here's a query:", ingredientsAvailable);

//Time how long brute force takes
var start = Date.now();
var result = [];
for (i = 0; i < numRecipes; i++) {
    var candidateRecipe = recipes[i];
    if (containsAll(candidateRecipe.needed, ingredientsAvailable)) {
        result.push(candidateRecipe);
    }
}
var end = Date.now();
console.log('Found ' + result.length + ' recipes in ' + (end - start) + ' milliseconds.');
console.log(result);

Это работает в 0 миллисекунд. Я выбрал эти небольшие числа, чтобы вы могли запустить его самостоятельно пару раз и убедить себя, что он делает то, что вы хотите, и относительно свободен от ошибок.

Теперь измените его так, чтобы у нас было 1 000 000 ингредиентов в БД, 1 000 000 рецептов в БД, 50 ингредиентов на рецепт и 100 ингредиентов, доступных мне. Т.е. значения, которые все равны или больше, чем самый большой вариант использования, который вы дали.

Он работает в 125 миллисекундах под nodejs, и это самая глупая реализация без каких-либо усилий по оптимизации.

Небу Покинс
источник
1
Если требования ОП не изменятся, нет причин не использовать такой подход. Умная структура данных? Достаточно быстро? Да. Ремонтопригоден и прост для понимания? Вероятнее всего.
J Trana