My code is determining the difference between two iterables in terms of items that have been addded, removed and kept. The items are assumed to be sortable and there are no duplicates.
def diff(before, after): """Return diff between iterables of sortable items `before` and `after` as tuple of three lists of items that have been added, removed and kept. """ before_iter = iter(sorted(before)) after_iter = iter(sorted(after)) add_items =  rem_items =  keep_items =  try: new = old = None while True: if new == old: if new is not None: keep_items.append(new) new = old = None new = next(after_iter) old = next(before_iter) elif new < old: add_items.append(new) new = None new = next(after_iter) elif old < new: rem_items.append(old) old = None old = next(before_iter) except StopIteration: if new is not None: add_items.append(new) if old is not None: rem_items.append(old) add_items += list(after_iter) rem_items += list(before_iter) return add_items, rem_items, keep_items if __name__ == '__main__': assert diff(, ) == (, , ) assert diff([1, 2, 3], [4, 3, 2]) == (, , [2, 3]) assert diff(['foo', 'bar'], ['baz', 'bar']) == (['baz'], ['foo'], ['bar'])
The way I'm working with iterators seems a bit awkward and appears to unnecessarily bloat the code. I feel there must be a more elegant pattern, maybe without iterators at all?
The code should perform well on large lists. That's also why I'm not using multiple set operations instead. (
add_items = set(after) - set(before), etc.) Or can I solve this efficiently with set operations? (I'm expecting both very small and very large differences between the iterables.)
Update: Unfortunately, I failed to include a key requirement into the question which therefore couldn't be considered in the answers. But I'll state it here, just for the record:
- The algorithm needs to perform well when comparison between the items is expensive. Since an approach using set operations incorporates more comparisons than the algorithm above, it performs worse in my use case.