Python Cookbook

Removing Duplicates from a Sequence

Credit: Tim Peters

Problem

You have a sequence that may include duplicates, and you need to remove the duplicates in the fastest possible way without knowing much about the properties of the items in the sequence. You do not care about the order of items in the resulting sequence.

Solution

The key is to try several approaches, fastest first, and use try/except to handle the failing cases of the fastest approaches:

def unique(s):
    """ Return a list of the elements in s in arbitrary order, but without
    duplicates. """

    # Get the special case of an empty s out of the way very rapidly
    n = len(s)
    if n == 0:
        return []

    # Try using a dict first, because it's the fastest and will usually work
    u = {}
    try:
        for x in s:
            u[x] = 1
    except TypeError:
        del u  # Move on to the next method
    else:
        return u.keys(  )

    # Since you can't hash all elements, try sorting, to bring equal items
    # together and weed them out in a single pass
    try:
        t = list(s)
        t.sort(  )
    except TypeError:
        del t  # Move on to the next method
    else:
        assert n > 0
        last = t[0]
        lasti = i = 1
        while i < n:
            if t[i] != last:
                t[lasti] = last = t[i]
                lasti += 1
            i += 1
        return t[:lasti]

    # Brute force is all that's left
    u = []
    for x in s:
        if x not in u:
            u.append(x)
    return u

Discussion

The purpose of this recipe’s unique function is to take a sequence s as an argument and return a list of the items in s in arbitrary order, but without duplicates. For example, calling unique([1, 2, 3, 1, 2, 3]) returns an arbitrary permutation ...