O'Reilly logo

Python Cookbook, 2nd Edition by David Ascher, Anna Ravenscroft, Alex Martelli

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

18.2. Removing Duplicates from a Sequence While Maintaining Sequence Order

Credit: Alex Martelli

Problem

You have a sequence that may include duplicates, and you want to remove the duplicates in the fastest possible way. Moreover, 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 becomes a problem quite different from that explored previously in Recipe 18.1. This requirement often arises in conjunction with a function f that defines an equivalence relation among items: x is equivalent to y if and only if f ( x )== f ( y ). In this case, the task of removing duplicates may often be better described as picking the first representative of each resulting equivalence class. Here is a function to perform this task:

# support 2.3 as well as 2.4
try: set
except NameError: from sets import Set as set
# f defines an equivalence relation among items of sequence seq, and
# f(x) must be hashable for each item x of seq
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 f(x) -> x
        def f(x): return x
    already_seen = set( )
    result = [  ]
    for item in seq:
        marker = f(item)if marker not in already_seen:
             already_seen.add(marker)
               result.append(item)
    return result

Discussion

The previous Recipe 18.1 is applicable only if you are not concerned about item ordering or, in other words, if the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required