runtimequestion 118 Collection Algorithms · medium
Join without the inner loop
attach_cities gives the right answers, but it compares every order with every customer. With 2,000 orders and 2,000 customers that is four million comparisons, and the nightly report is slow. Refactor it to build an index once and look each order up. Behaviour must not change, including two details of the original: an unknown customer gets the city "unknown", and because the inner loop never stops early, when a customer ID appears twice the last matching record wins.
Function
attach_cities(orders, customers) (same name, same result)ordersdictionaries with
order_id and customer_idcustomersdictionaries with
customer_id and cityReturnsa new list with one
{"order_id": …, "city": …} per order, in orderSpeedeach order must be found with a lookup, not by scanning the whole customer list
Examples
callattach_cities([{'order_id': 'O101219', 'customer_id': 'C00077'}, {'order_id': 'O121005', 'customer_id': 'C08398'}, {'order_id': 'O101341', 'customer_id': 'C00038'}], [{'customer_id': 'C00038', 'city': 'New York'}, {'customer_id': 'C00077', 'city': 'Houston'}, {'customer_id': 'C01338', 'city': 'New York'}])returns[{'order_id': 'O101219', 'city': 'Houston'}, {'order_id': 'O121005', 'city': 'unknown'}, {'order_id': 'O101341', 'city': 'New York'}]
callattach_cities([{'order_id': 'O1', 'customer_id': 'C01338'}, {'order_id': 'O2', 'customer_id': 'C01338'}], [{'customer_id': 'C00038', 'city': 'New York'}, {'customer_id': 'C00077', 'city': 'Houston'}, {'customer_id': 'C01338', 'city': 'New York'}])returns[{'order_id': 'O1', 'city': 'New York'}, {'order_id': 'O2', 'city': 'New York'}]
callattach_cities([], [{'customer_id': 'C00038', 'city': 'New York'}, {'customer_id': 'C00077', 'city': 'Houston'}, {'customer_id': 'C01338', 'city': 'New York'}])returns[]