基于多值和的字典匹配

Question

我有两本字典如下。一个用于服务，另一个用于能够提供服务的供应商。每个服务可以由多个供应商提供。你知道吗

service = {'service1': {'serviceId': 's0001', 'cost': 220},
           'service2': {'serviceId': 's0002', 'cost': 130}....}

supplier = {'supplier1': {'supplierId': 'sup1', 'bid': 30},
           'supplier2': {'supplierId': 'sup2', 'bid': 12},
            'supplier3': {'supplierId': 'sup3', 'bid': 30}....}

我想有一个新的字典匹配服务供应商的基础上，多个出价的总和是大于或等于服务成本。比如：

matched = {'service1': [sup1, sup2, sup100],
'service2': [sup20, sup64, sup200, sup224]....}

假设我们在两个词典中都有大量的条目，那么对于这种必需的匹配，什么是一种好的方法呢？对能够提供单一服务的供应商数量没有限制。 我累了，但没有工作。你知道吗

match = {}

for key, value in service.items():
        if service[key]['cost'] >= supplier[key]['bid']:
            match[key] = [sup for sup in supplier[key]['supplierID']]

以下是预期输出：

matched = {'service1': [sup1, sup2, sup100], 'service2': [sup20, sup64, sup200, sup224]....}

Answer 1

我假设we have huge number of entries in both dictionaries。这就是我解决问题的方法：

import numpy as np

# data
service = {'service1': {'serviceId': 's0001', 'cost': 12},
           'service2': {'serviceId': 's0002', 'cost': 30}}
supplier = {'supplier1': {'supplierId': 'sup1', 'bid': 30},
            'supplier2': {'supplierId': 'sup2', 'bid': 12},
            'supplier3': {'supplierId': 'sup3', 'bid': 30}}

# lists of suppliers' IDs and bids
sups, bids = list(), list()
for key, info in supplier.items():
    sups.append(info['supplierId'])
    bids.append(info['bid'])

# sorted lists of suppliers' IDs and bids to allow binary search
bids, sups = zip(*sorted(zip(bids, sups)))

# main loop
matched = dict()
for key, info in service.items():
    matched[key] = sups[:np.searchsorted(bids, info['cost'], side='right')]

matched：

{'service1': ('sup2',), 'service2': ('sup2', 'sup1', 'sup3')}

这段代码不能实现对新条目的简单处理，但允许这样做。对于每一个新的service_record我们必须执行一个二进制搜索，对于每一个新的supplier_record我们必须执行一个二进制搜索和一个循环service来更新matched。你知道吗

根据具体的要求和存储数据的方式，代码可能会改进，也应该改进。你知道吗