Conditionally matching two databases in python

Question

I have a collection of objects of foods and restaurant and I need to match all object food object to the corresponding restaurant. I implemented a naive solution that has time complexity O(n*m), where n and m size of the food and restaurant database respectively.

def match_products(self):
   self._restaurant_dict= self._init_restaurant_dict()
   for food in foods():
        for restaurant in self._restaurant_dict.keys():
            if self._matched(restaurant , food ):
                self.mached_candidates[restaurant].append(food)

def _init_restaurant_dict(self):
    res_dict= {}
    for product in restaurants():
        res_dict[restaurant] = []
    return res_dict

def _matched(self, restaurant , food ):
    return restaurant.id == food.id 

The restaurant and food are defined as follow:

class Structure:
    _fields = []
    def __init__(self, *args):
        if len(args) != len(self._fields):
            raise TypeError("Wrong args number")
        for name, val in zip(self._fields,args):
            setattr(self, name, val)

    def __repr__(self):
        return ', '.join("%s: %s" % item for item in vars(self).items())

class Restaurant(Structure):
    _fields = ["id","name","owner"]

class Food(Structure):
    _fields = ["id","descriptions","calories"]

Methods foods() and restaurants() are generators. So how can I speed up this algorithm?

Answer 1

use the id as the hash value for a lookup table.

lookup_table = dict()
for food in foods():
  if food.id not in lookup_table:
    lookup_table.update({food.id: [food]})
  else:
    lookup_table[food.id].append(food)
matched_candidates = {restaurant : lookup_table.get(resturant.id, []) for restaurant in restaurants()}

Or something like that. O(N+M)