I l@ve RuBoard |

## 17.4 Removing Duplicates from a SequenceCredit: Tim Peters ## 17.4.1 ProblemYou 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. ## 17.4.2 SolutionThe key is to try several approaches, fastest first, and use
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 ## 17.4.3 DiscussionThe purpose of this recipe's
The fastest way to remove duplicates from a sequence depends on some
pretty subtle properties of the sequence elements, such as whether
they're hashable and whether they support full
comparisons. The For best speed, all sequence elements should be hashable. When they
are, the If it turns out that hashing the elements (using them as dictionary
keys) is not possible, the next best thing is that the elements enjoy
a total ordering. If If sorting also turns out to be impossible, the sequence elements
must at least support equality testing, or else the very concept of
duplicates can't really be meaningful for them. In
this case, This is a pure example of how algorithm efficiency depends on the strength of the assumptions you can make about the data. Of course, you could split this into three distinct functions and directly call the one that best meets your needs. In practice, however, the brute-force method is so slow for large sequences that nothing measurable is lost by simply letting the function as written try the faster methods first. If you need to preserve the same order of items in the output sequence as in the input sequence, see Recipe 17.5. ## 17.4.4 See Also |

I l@ve RuBoard |