Take the 2-minute tour ×

What is the fasted way to get a sorted, unique list in python? (I have a list of hashable things, and want to have something I can iterate over - doesn't matter whether the list is modified in place, or I get a new list, or an iterable. In my concrete use case, I'm doing this with a throwaway list, so in place would be more memory efficient.)

I've seen solutions like

input = [5, 4, 2, 8, 4, 2, 1]

but it seems to me that first checking for uniqueness and then sorting is wasteful (since when you sort the list, you basically have to determine insertion points, and thus get the uniqueness test as a side effect). Maybe there is something more along the lines of unix's

cat list | sort | uniq

that just picks out consecutive duplications in an already sorted list?

Note in the question ' Fastest way to uniqify a list in Python ' the list is not sorted, and ' What is the cleanest way to do a sort plus uniq on a Python list? ' asks for the cleanest / most pythonic way, and the accepted answer suggests sorted(set(input)), which I'm trying to improve on.

share|improve this question
Does sorted(set(input)) not meet your speed requirements in some way? –  Aesthete Nov 28 '12 at 10:38
What does timeit tell you is fastest? –  Martijn Pieters Nov 28 '12 at 10:40
Asking for the fastest is really not very meaningful, unless you tell us about your data (how many elements in the list, what fraction are duplicates, how much does it cost to compare two elements, how good and expensive is the hash function, etc) –  NPE Nov 28 '12 at 10:42
@MartijnPieters: I haven't tested it yet. I could come up with two or three alternatives, but maybe there is a brilliant uniq-sort function in the standard library that I don't know of. That's what I'm looking for, approaches that I wouldn't think of myself. –  jdm Nov 28 '12 at 10:47
@jdm - sorted(set(input)) is pretty damn aesthetically pleasing IMHO, but I appreciate your quest, and wish you well with it. I'm interested to see the results. –  Aesthete Nov 28 '12 at 10:47

6 Answers 6

I believe sorted(set(sequence)) is the fastest way of doing it. Yes, set iterates over the sequence but that's a C-level loop, which is a lot faster than any looping you would do at python level.

Note that even with groupby you still have O(n) + O(nlogn) = O(nlogn) and what's worst is that groupby will require a python-level loop, which increases dramatically the constants in that O(n) thus in the end you obtain worst results.

When speaking of CPython the way to optimize things is to do as much as you can at C-level(see this answer to have an othre example, where an O(nlogn) C-level algorithm beats an O(n) algorithm for every reasonable input). To have a faster solution you must reimplement a sort, in a C-extensions. And even then, good luck with obtaining something as fast as python's Timsort!

A small comparison of the "canonical solution" versus the groupby solution:

>>> import timeit
>>> sequence = list(range(500)) + list(range(700)) + list(range(1000))
>>> timeit.timeit('sorted(set(sequence))', 'from __main__ import sequence', number=1000)
>>> import itertools
>>> def my_sort(seq):
...     return list(k for k,_ in itertools.groupby(sorted(seq)))
>>> timeit.timeit('my_sort(sequence)', 'from __main__ import sequence, my_sort', number=1000)

As you can see it's 3 times slower.

The version provided by jdm is actually even worse:

>>> def make_unique(lst):
...     if len(lst) <= 1:
...         return lst
...     last = lst[-1]
...     for i in range(len(lst) - 2, -1, -1):
...         item = lst[i]
...         if item == last:
...             del lst[i]
...         else:
...             last = item
>>> def my_sort2(seq):
...     make_unique(sorted(seq))
>>> timeit.timeit('my_sort2(sequence)', 'from __main__ import sequence, my_sort2', number=1000)

Almost 5 times slower. Note that using seq.sort() and then make_unique(seq) and make_unique(sorted(seq)) are actually the same thing, since Timsort uses O(n) space you always have some reallocation, so using sorted(seq) does not actually change much the timings.

The jdm's benchmarks give different results because the input he is using are way too small and thus all the time is taken by the time.clock() calls.

share|improve this answer
>>> import itertools
>>> a=[2,3,4,1,2,7,8,3]
>>> list(k for k,_ in itertools.groupby(sorted(a)))
[1, 2, 3, 4, 7, 8]
share|improve this answer
I believe sorted(set(alist)) is actually faster. –  gg.kaspersky Nov 28 '12 at 11:53

This is just something I whipped up in a couple minutes. The function modifies a list in place, and removes consecutive repeats:

def make_unique(lst):
    if len(lst) <= 1:
        return lst
    last = lst[-1]
        item = lst[i]
        if item == last:
            del lst[i]
            last = item

Some representative input data:

inp = [
(u"Tomato", "de"), (u"Cherry", "en"), (u"Watermelon", None), (u"Apple", None),
(u"Cucumber", "de"), (u"Lettuce", "de"), (u"Tomato", None), (u"Banana", None),
(u"Squash", "en"), (u"Rubarb", "de"), (u"Lemon", None),

Make sure both variants work as wanted:

print inp
print sorted(set(inp))
# copy because we want to modify it in place
inp1 = inp[:]
print inp1

Now to the testing. I'm not using timeit, since I don't want to time the copying of the list, only the sorting. time1 is sorted(set(...), time2 is list.sort() followed by make_unique, and time3 is the solution with itertools.groupby by Avinash Y.

import time
def time1(number):
    total = 0
    for i in range(number):
        start = time.clock()
        total += time.clock() - start
    return total

def time2(number):
    total = 0
    for i in range(number):
        inp1 = inp[:]
        start = time.clock()
        total += time.clock() - start
    return total

import itertools 

def time3(number): 
    total = 0 
    for i in range(number): 
        start = time.clock() 
        list(k for k,_ in itertools.groupby(sorted(inp))) 
        total += time.clock() - start 
    return total

sort + make_unique is approximately as fast as sorted(set(...)). I'd have to do a couple more iterations to see which one is potentially faster, but within the variations they are very similar. The itertools version is a bit slower.

# done each 3 times
print time1(100000)
# 2.38, 3.01, 2.59
print time2(100000)
# 2.88, 2.37, 2.6
print time3(100000)
# 4.18, 4.44, 4.67

Now with a larger list (the + str(i) is to prevent duplicates):

old_inp = inp[:]
inp = []
for i in range(100):
    for j in old_inp:
        inp.append((j[0] + str(i), j[1]))

print time1(10000)
# 40.37
print time2(10000)
# 35.09
print time3(10000)
# 40.0

Note that if there are a lot of duplicates in the list, the first version is much faster (since it does less sorting).

inp = []
for i in range(100):
    for j in old_inp:
        inp.append((j[0], j[1]))

print time1(10000)
# 3.52
print time2(10000)
# 26.33
print time3(10000)
# 20.5
share|improve this answer
Really bad example for the timings. With an input so small you have problems with granularity. –  Bakuriu Nov 28 '12 at 13:01

Maybe this is not the answer you are searching for, but anyway, you should take this into your consideration.

Basically, you have 2 operations on a list:

unique_list = set(your_list)       # O(n) complexity
sorted_list = sorted(unique_list)  # O(nlogn) complexity

Now, you say "it seems to me that first checking for uniqueness and then sorting is wasteful", and you are right. But, how bad really is that redundant step? Take n = 1000000:

# sorted(set(a_list))
O(n) => 1000000
o(nlogn) => 1000000 * 20 = 20000000
Total => 21000000

# Your fastest way
O(nlogn) => 20000000
Total: 20000000

Speed gain: (1 - 20000000/21000000) * 100 = 4.76 %

For n = 5000000, speed gain: ~1.6 %

Now, is that optimization worth it?

share|improve this answer
I would not actually substitute numbers into an O(n) expression. The results are largely meaningless. –  Waleed Khan Nov 28 '12 at 11:38
Ideally, it is not meaningless, but in most cases, you are right. I just intended to make some comparisons. I wanted to show that the bottleneck here was sort, not the set creation, so optimizing the sort function would be much more productive than getting rid of eliminating the set creation redundance. –  gg.kaspersky Nov 28 '12 at 11:46
You could demonstrate it without the numbers as well: O(n) + O(nlogn) = O(n+nlogn) = O(n(1+logn)) = O(nlogn) which means that the complexity remains the same. –  GaretJax Nov 28 '12 at 11:57
import numpy as np

it returns an array unique and sorted.

share|improve this answer
Does this work for any objects providing method __cmp__(self, other)? –  wberry Nov 4 '13 at 18:46

since you already have a full understanding of what is involved, i will not bore you with simply reciting sorted(list(set(input))) - and you might not even need the list part.

but, if you want to make this fast and efficient, you need to understand why it would NOT be fast and efficient.

between sorting items and making them unique, what takes longer?

both involve iterating over the whole list and doing multiple checks.

doing this twice, once for unique and once for sort, is even longer.

not to mention, in python the sort and unique function are very generic, and can be implemented over many data container types, and many object types.

if you really want to make a fast sort/uniq method, you should write one yourself. which deals explicitly in your data container, and your object types. also, combining the sort and unique at the same time.

this is very possible to do, but it will take a little bit of cleverness. if this is something you want, you should make a new question IMHO or edit this one to reflect, leave a comment on my answer, and i can help you with it.

you could also create a new data container to hold your data which already implements a sort/uniq interface builtin. but that might be ill suited for your program, depending on how you populate your data containers.

share|improve this answer
is there a constructive reason as to why i was downvoted? it would help me improve if i could know why. i really don't understand how my answer is having a detrimental affect, as to be downvoted... ? –  Inbar Rose Nov 28 '12 at 13:08

Your Answer


