Pythonで条件付きで2つのデータベースを一致

Question

私は食品とレストランのオブジェクトのコレクションを持っており、私はすべてのオブジェクトの食品オブジェクトを対応するレストランに一致させる必要があります。 時間複雑度O（n * m）を持つ素朴な解を実装しました。ここでnとmはそれぞれ食品データベースとレストランデータベースのサイズです。

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 

レストラン、食品は次のように定義されています。

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"] 

メソッド食品（）やレストランが（）ジェネレータです。 どうすればこのアルゴリズムを高速化できますか？

Answer 1

ルックアップテーブルのハッシュ値としてidを使用します。

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()} 

などです。 O（N + M）

Answer 2

わかりましたので、私はあなたがレストランIDと食品名の最初の文字で食品を選択できるようにしたいと考えています。だから、「パパハット」は42のIDを持ち、あなたは「ピザ」を望んでいたとします。鍵でそれを見ています42p これはなぜ機能しますか？ restaurant.idフィールドが一意の識別子であり、という文字列に連結された一意の文字列は、まだ一意であると予想されるので、は一意です。したがって、restaurant.idフィールドを複雑にすると、ルックアップテーブルの検索がより具体的になります。しかし、食べ物を入手するためにはより多くのアクセスが必要になります。このトレードオフを試すことができます。 Wiki on hash tables Advantages/Drawbacks

matched_candidates = dict() 
for food in foods(): 
    if food.id not in lookup_table: 
    matched_candidates .update({''.join(food.id, food.name[0].lower()): [food]}) 
    else: 
    matched_candidates [food.id].append(food) 

    matched_candidates.update({ restaurant : [] 
          for restaurant in restaurants() 
          if restaurant not in matched_candidates.keys() 
          }) 

アップデートは、（）ジェネレータ食品中の任意の食品を持っていない可能性がありresturantsのを追加することです。これはまだO（N + M）です。

私はここで正直である必要があります、これは私に間違って感じる。テーブルにアクセスできるようにするには、食べ物とレストランの両方の特別な知識が必要です。しかし、ルックアップは速いので、多分あなたが気にしているのです。