Algorytm / struktura danych pozwalająca odpowiedzieć „jakie przepisy mogę przygotować przy użyciu tego zestawu składników?”

Formalnie niech s ( U , Q ) = { V | V ∈ U i V ⊆ Q }, gdzie U , Q i V wszystkie reprezentują zbiory, a U , a dokładniej, reprezentuje zbiór zbiorów. Na przykład, U może być zestawem (zestawów) składników wymaganych dla różnych przepisów w książce kucharskiej, przy czym Q reprezentuje zestaw składników, które mam V reprezentuje przepis, który mógłbym przygotować z tych składników. Zapytanie s ( U , Q) odpowiada pytaniu „Co mogę zrobić z tymi składnikami?”

To, czego szukam, to reprezentacja danych, która indeksuje U w taki sposób, że obsługuje wydajne zapytania s ( U , Q ), w których Q i wszyscy członkowie U będą ogólnie mali w porównaniu do unii wszystkich członków U . Ponadto chciałbym, aby był w stanie skutecznie aktualizować U (np. Dodawać lub usuwać przepis).

Nie mogę nie myśleć, że ten problem musi być dobrze zrozumiany, ale nie byłem w stanie znaleźć nazwy ani odniesienia do niego. Czy ktoś zna strategię skutecznego rozwiązania tego problemu lub miejsce, w którym mogę przeczytać więcej na ten temat?

Jeśli chodzi o myślenie o rozwiązaniu jedna myśl miałem było zbudować drzewo decyzyjne dla zbioru U . W każdym węźle drzewa pytanie „czy lista składników zawiera x ?” zostanie poproszony o x, aby zmaksymalizować liczbę członków U, którzy zostaną wyeliminowani przez odpowiedź. Gdy U zostanie zaktualizowany, drzewo decyzyjne musiałoby zostać ponownie zrównoważone, aby zminimalizować liczbę pytań wymaganych do znalezienia prawidłowego wyniku. Inną myślą jest reprezentowanie U za pomocą n- wymiarowej boolean „oktree” (gdzie n jest liczbą unikalnych składników).

Uważam, że „Jakie przepisy można przygotować z tych składników?” można na nie odpowiedzieć, pobierając iloczyn kartezjański (zestaw składników wymaganych do) przepisów z książki kucharskiej z zestawem energetycznym składników, które posiada, i filtrując otrzymane pary uporządkowane dla par, w których oba elementy są równe, ale to nie jest wydajne rozwiązanie, a pytam o to, jak zoptymalizować ten rodzaj operacji; jak można to skomponować w języku SQL, aby był wydajny i co robi SQL, aby to było skuteczne?

Chociaż korzystam z ilustracji książki kucharskiej z przepisami i zestawu składników, przewiduję, że liczba „przepisów” i liczba „składników” będą bardzo duże (do setek tysięcy każdy), choć liczba składników w danym przepisie, a liczba składników w danym zestawie składników będzie względnie mała (prawdopodobnie około 10-50 dla typowego „przepisu” i około 100 dla typowego „zestawu składników”). Ponadto, najczęściej operacja będzie zapytanie a ( U , P ), więc powinien on być najbardziej optymalne. Oznacza to również, że algorytm brutalnej siły, który wymaga sprawdzenia każdego przepisu lub działania nad każdym składnikiem, sam byłby niepożądanie powolny. Dzięki sprytnemu buforowaniu

Jeśli chodzi o liczby, które podałeś, po prostu brutalnie to wymuś.

Oto program JavaScript, który brutalnie zmusza go do 10 składników w DB, 10 przepisów w DB, każdy przepis potrzebuje 2 składników, a ja mam 5 składników dostępnych:

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);

Działa w 0 milisekundach. Wybrałem te małe liczby, abyś mógł uruchomić je sam kilka razy i przekonać się, że robi to, co chcesz i jest względnie wolne od błędów.

Teraz zmień to, abyśmy mieli 1 000 000 składników w DB, 1 000 000 przepisów w DB, 50 składników na przepis i 100 składników dostępnych dla mnie. To znaczy wartości, które są równe lub większe niż największy podany przypadek użycia.

Działa w 125 milisekundach pod nodejs, i to z najgłupszą implementacją bez absolutnie żadnego wysiłku w celu optymalizacji.