SQL для расчета коэффициента Tanimoto нескольких векторов

Question

Я думаю, что легче объяснить мою проблему на примере.

У меня есть один стол с ингредиентами для рецептов, и я внедрил функцию для вычисления Tanimoto coefficient между ингредиентами. Это достаточно быстро, чтобы вычислить коэффициент между двумя ингредиентами (требуется 3 sql-запроса), но он недостаточно масштабируется. Чтобы вычислить коэффициент между комбинацией всех возможных ингредиентов, ему нужны N + (N * (N-1))/2 запроса или 500500 запросов всего за 1 000 ингредиентов. Есть ли более быстрый способ сделать это? Вот что я получил до сих пор:

class Filtering(): 
    def __init__(self): 
    self._connection=sqlite.connect('database.db') 

    def n_recipes(self, ingredient_id): 
    cursor = self._connection.cursor() 
    cursor.execute('''select count(recipe_id) from recipe_ingredient 
     where ingredient_id = ? ''', (ingredient_id,)) 
    return cursor.fetchone()[0] 

    def n_recipes_intersection(self, ingredient_a, ingredient_b): 
    cursor = self._connection.cursor() 
    cursor.execute('''select count(drink_id) from recipe_ingredient where 
     ingredient_id = ? and recipe_id in (
     select recipe_id from recipe_ingredient 
     where ingredient_id = ?) ''', (ingredient_a, ingredient_b)) 
    return cursor.fetchone()[0] 

    def tanimoto(self, ingredient_a, ingredient_b): 
    n_a, n_b = map(self.n_recipes, (ingredient_a, ingredient_b)) 
    n_ab = self.n_recipes_intersection(ingredient_a, ingredient_b) 
    return float(n_ab)/(n_a + n_b - n_ab) 

Answer 1

Почему вы не просто извлечение всех рецептов в память, а затем вычисления коэффициентов Танимото в памяти?

Это проще, и это намного, намного быстрее.

Answer 2

Я думаю, что это сократит вас до 2 выборок на пару для пересечения и 4 запросов на общую пару. Вы не можете уйти от O (N^2), так как вы пытаетесь использовать все пары - N * (N-1)/2 - это просто количество пар.

def n_recipes_intersection(self, ingredient_a, ingredient_b): 
    cursor = self._cur 
    cursor.execute(''' 
    select count(recipe_id) 
     from recipe_ingredient as A 
     join recipe_ingredient as B using (recipe_id) 
     where A.ingredient_id = ? 
     and B.ingredient_id = ?; 
     ''', (ingredient_a, ingredient_b)) 
    return cursor.fetchone()[0] 

Answer 3

Если у вас есть 1000 ингредиентов, 1000 запросов будет достаточно, чтобы сопоставить каждый ингредиент с набором рецептов в памяти. Если (скажем) ингредиент, как правило, составляет около 100 рецептов, каждый набор будет занимать несколько килобайт, поэтому весь словарь займет всего несколько МБ - абсолютно никакой проблемы, чтобы сохранить все это в памяти (и все еще не серьезное проблема памяти, если среднее количество рецептов на ингредиент растет на порядок).

result = dict() 
for ing_id in all_ingredient_ids: 
    cursor.execute('''select recipe_id from recipe_ingredient 
     where ingredient_id = ?''', (ing_id,)) 
    result[ing_id] = set(r[0] for r in cursor.fetchall()) 
return result 

После этих 1000 запросов, каждый из необходимых 500.000 расчетов парных коэффициентов Танимото затем, очевидно, сделан в памяти - вы можете предвычисление квадратов длин различных наборов в качестве дальнейшего ускорения (и парковать их в другом dict), а ключом «dotproduct B» для каждой пары является, конечно, длина пересечения множеств.

Answer 4

Если кому-то интересно, это код, который я придумал после предложений Алекса и С.Лоттса. Спасибо вам, ребята.

def __init__(self): 
    self._connection=sqlite.connect('database.db') 
    self._counts = None 
    self._intersections = {} 

def inc_intersections(self, ingredients): 
    ingredients.sort() 
    lenght = len(ingredients) 
    for i in xrange(1, lenght): 
     a = ingredients[i] 
     for j in xrange(0, i): 
      b = ingredients[j] 
      if a not in self._intersections: 
       self._intersections[a] = {b: 1} 
      elif b not in self._intersections[a]: 
       self._intersections[a][b] = 1 
      else: 
       self._intersections[a][b] += 1 


def precompute_tanimoto(self): 
    counts = {} 
    self._intersections = {} 

    cursor = self._connection.cursor() 
    cursor.execute('''select recipe_id, ingredient_id 
     from recipe_ingredient 
     order by recipe_id, ingredient_id''') 
    rows = cursor.fetchall()    

    print len(rows) 

    last_recipe = None 
    for recipe, ingredient in rows: 
     if recipe != last_recipe: 
      if last_recipe != None: 
       self.inc_intersections(ingredients) 
      last_recipe = recipe 
      ingredients = [ingredient] 
     else: 
      ingredients.append(ingredient) 

     if ingredient not in counts: 
      counts[ingredient] = 1 
     else: 
      counts[ingredient] += 1 

    self.inc_intersections(ingredients) 

    self._counts = counts 

def tanimoto(self, ingredient_a, ingredient_b): 
    if self._counts == None: 
     self.precompute_tanimoto() 

    if ingredient_b > ingredient_a: 
     ingredient_b, ingredient_a = ingredient_a, ingredient_b 

    n_a, n_b = self._counts[ingredient_a], self._counts[ingredient_b] 
    n_ab = self._intersections[ingredient_a][ingredient_b] 

    print n_a, n_b, n_ab 

    return float(n_ab)/(n_a + n_b - n_ab)