runtimequestion 460 Reliable Data Pipelines · hard
Deduplicate a day of events quickly
The feed redelivers events, so the loader keeps only the first copy of each event ID. The current first_copies compares every event's ID with every ID kept so far, which takes minutes on a full day. Make it fast without changing what it returns.
Function
first_copies(events)Returnsa new list with the first event for each
id, in the order those first copies appear; the input is not changedConstraintfor 800 events with 400 different IDs, the function may compare IDs with
== at most 1,600 times (the current version needs 160,000; on a full day of events the gap is minutes against milliseconds)Examples
callfirst_copies([{'id': '48000000581', 'type': 'PushEvent', 'delivery': 1}, {'id': '48000007504', 'type': 'WatchEvent', 'delivery': 1}, {'id': '48000000581', 'type': 'PushEvent', 'delivery': 2}])returns[{'id': '48000000581', 'type': 'PushEvent', 'delivery': 1}, {'id': '48000007504', 'type': 'WatchEvent', 'delivery': 1}]
callfirst_copies([{'id': 'a', 'delivery': 1}, {'id': 'b', 'delivery': 1}])returns[{'id': 'a', 'delivery': 1}, {'id': 'b', 'delivery': 1}]
callfirst_copies([{'id': 'c', 'delivery': 1}, {'id': 'c', 'delivery': 2}, {'id': 'c', 'delivery': 3}])returns[{'id': 'c', 'delivery': 1}]