Python Cookbook

Removing Duplicates from a Sequence While Maintaining Sequence Order

Credit: Alex Martelli

Problem

You have a sequence that may include duplicates, and you need to remove the duplicates in the fastest possible way. Also, the output sequence must respect the item ordering of the input sequence.

Solution

The need to respect the item ordering of the input sequence means that picking unique items will be a very different problem than that explored in Recipe 17.4. This kind of need often arises in conjunction with a function f that defines an equivalence relation among items (i.e., x is equivalent to y if and only if f(x)==f(y)), in which case the need to remove duplicates may be better described as picking the first representative of each occurring equivalence class:

# f defines an equivalence relation among items of sequence seq, and
# f(x) must be hashable for each item x of seq (e.g., cPickle.dumps)
def uniquer(seq, f=None):
    """ Keeps earliest occurring item of each f-defined equivalence class """
    if f is None:    # f's default is the identity function
        def f(x): return x
    already_seen = {}
    result = []
    for item in seq:
        marker = f(item)
        # Python 2.2-ism; in older Pythons, use not already_seen.get(marker, 0)
        if marker not in already_seen:
            already_seen[marker] = 1
            result.append(item)
    return result

Picking the most recent (last occurring) representative of each equivalence class is a bit harder:

def uniquest(seq, f=None): """ Keeps last occurring item of each f-defined equivalence class. However, ...