2 """Return a list of the elements in s, but without duplicates.
3 For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
4 unique("abcabc") some permutation of ["a", "b", "c"], and
5 unique(([1, 2], [2, 3], [1, 2])) some permutation of
7 For best speed, all sequence elements should be hashable. Then
8 unique() will usually work in linear time.
9 If not possible, the sequence elements should enjoy a total
10 ordering, and if list(s).sort() doesn't raise TypeError it's
11 assumed that they do enjoy a total ordering. Then unique() will
12 usually work in O(N*log2(N)) time.
13 If that's not possible either, the sequence elements must support
14 equality-testing. Then unique() will usually work in quadratic
22 # Try using a dict first, as that's the fastest and will usually
23 # work. If it doesn't work, it will usually fail quickly, so it
24 # usually doesn't cost much to *try* it. It requires that all the
25 # sequence elements be hashable, and support equality comparison.
31 del u # move on to the next method
34 # We can't hash all the elements. Second fastest is to sort,
35 # which brings the equal elements together; then duplicates are
36 # easy to weed out in a single pass.
37 # NOTE: Python's list.sort() was designed to be efficient in the
38 # presence of many duplicate elements. This isn't true of all
39 # sort functions in all languages or libraries, so this approach
40 # is more effective in Python than it may be elsewhere.
45 del t # move on to the next method
52 t[lasti] = last = t[i]
56 # Brute force is all that's left.