lesson 59 Collection Algorithms · intermediate

Look up and merge by key

Orders hold a customer ID; customers hold the name and city. Index one collection by ID once, and every record in the other finds its match in one lookup.

You'll be able to

Build an index: a dictionary from ID to the whole record
Join a second collection through the index, checking in when a key can be missing
Merge two dictionaries with update, knowing which value wins and which dictionary changes

The idea

Data is usually split across tables. An order says customer_id: C00077, and that customer's city is in a different list. To show each order with its city you join the two on the shared key.

You could search the whole customer list for every order, a loop inside a loop. Instead, walk the customers once and build an index: a dictionary from ID to the whole customer record. After that, each order needs one lookup.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Index, then look up

customers = [
    {"customer_id": "C00038", "name": "Nora Garcia", "city": "New York"},
    {"customer_id": "C00077", "name": "Jamal Walker", "city": "Houston"},
]
by_id = {}
for customer in customers:
    by_id[customer["customer_id"]] = customer

orders = [
    {"order_id": "O101219", "customer_id": "C00077"},
    {"order_id": "O101341", "customer_id": "C00038"},
    {"order_id": "O108858", "customer_id": "C00077"},
]
for order in orders:
    customer = by_id[order["customer_id"]]
    print(order["order_id"], customer["name"], customer["city"])

Real data has gaps. An order can point at a customer who isn't in the list you were given, and looking up a key that isn't there stops the program.

example-2.py · A customer missing from the index

by_id = {"C00077": {"name": "Jamal Walker"}}
orders = [{"order_id": "O101219", "customer_id": "C00077"}, {"order_id": "O121005", "customer_id": "C08398"}]
for order in orders:
    customer = by_id[order["customer_id"]]
    print(order["order_id"], customer["name"])

Sometimes both sides are already dictionaries with the same kind of key, such as a price list and a file of price changes. prices.update(changes) copies every pair from changes into prices: a key that already exists gets the new value, and a new key is added at the end.

update changes the dictionary before the dot and returns None. When the original must survive, copy() it first; copy works on dictionaries the same way it does on lists.

example-3.py · Apply price changes to a copy

prices = {"SPO-11681": 7.49, "HOM-22847": 31.0, "ELE-24781": 171.99}
changes = {"HOM-22847": 27.5, "TOY-54564": 26.99}
new_prices = prices.copy()
new_prices.update(changes)
print(new_prices)
print(prices["HOM-22847"])

Review

Index one collection once: by_id[record["customer_id"]] = record.
Look up each record from the other; test with in first when a key can be missing, and decide: skip it or use a placeholder.
a.update(b) copies b's pairs into a; on a shared key b's value wins. It changes a and returns None.
Next: the same "have I seen this key?" test removes duplicates.

Practise this