有條件地匹配python中的兩個數據庫

我有一個食物和餐廳的對象集合，我需要匹配所有對象食物對象到相應的餐廳。我實現了一個天真的解決方案，其時間複雜度爲O（n * m），其中分別是食物和餐館數據庫的n和m大小。有條件地匹配python中的兩個數據庫

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

方法食品（）和餐館（）是發電機。那麼我該如何加快這個算法呢？

來源

2017-10-10 user1877600

「食物（）」和「餐館（）」是否以任何特定的順序產生其內容？也許使用將'id'映射到'Structure'的字典，所以你只需要遍歷其中一個列表。 –

這真棒！謝謝。所以解決方案非常簡單。我是個傻瓜！ – user1877600

使用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）

來源

2017-10-10 16:04:17 VoNWooDSoN

謝謝。我還有一個問題。任何想法如何使用一點點複雜的條件進行類似的匹配，例如，相同的id和相同的名字的字符？ – user1877600

當然，但我會鼓勵你考慮一下什麼能產生好的散列值。使這項工作成功的原因是食物ID和餐廳ID之間存在良好的「一對多」關係。如果你使它複雜化，它可能不會那麼快。我將在這裏添加一個例子，它在名稱的第一個字母上進一步分組，但考慮一下數據庫何時比嘗試在代碼中執行這些關係更合適。 – VoNWooDSoN

好的，爲了澄清一下，我假設您希望能夠通過餐廳ID和食物名稱的第一個字符來選擇食物。所以，說「爸爸小屋」的ID爲42，你想要一個「比薩餅」，你可以用鑰匙查找它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）。

我必須誠實地說，這對我來說是不對的。這種類型需要食品和餐館的特殊知識才能訪問桌子。但是，查找速度很快，所以也許這就是你所關心的。

來源

2017-10-11 15:49:48 VoNWooDSoN

有條件地匹配python中的兩個數據庫

回答

相關問題