# Increasing the efficiency of a python code.

1. Sep 8, 2014

Here is a python function to check whether a given list or string contains duplicate values:
Code (Text):

def has_duplicates(x):
t = []
for i in x:
if i not in t:
t.append(i)
if t != list(x):
return True
else:
return False

But I am sure this approach will be slow for large lists. Is there any other, faster way to do this?

2. Sep 8, 2014

### Integrand

You could use something like this:

Code (Text):

def has_duplicates(seq):
return len(seq) != len(set(seq))

3. Sep 8, 2014

### AlephZero

If Python has a simple-minded implementation of lists, that will take n/2 comparisons on average for each "i not in t" test, if the list has n elements. So the total time will be proportional to n2. You could check that out experimentally.

It might be faster to use a dictionary instead of a list. There is an OrderedDict that remembers the order you added the elements, if that ordering is important for some reason. That should give you a time roughly proportional to n.

Another idea would be to sort the lists first and then check for duplicates. The time to do that should be proportional to n log n.

The "best" option to choose depends on what the whole application needs to do, not necessarily on optimizing just one function.

Last edited: Sep 8, 2014
4. Sep 8, 2014

### Daverz

There are a zillion answers for this on stackoverflow. Integrand has a good solution if you are only interested in whether there are duplicates.

For the efficiency of the built-ins, see https://wiki.python.org/moin/TimeComplexity.

To estimate the efficiency of your routine, think about the worst case scenario: two duplicates at the end of the list. "i not in t" looks simple, but each check requires a complete traversal of t (it's an O(n) operation). If n=len(x), there are (n-1) append calls and (n-1) * ( 1 + 2 + ... + n-1) comparisons. That's (n-1)*(n-1)/2*n comparisons. Our complexity is O(n**3). Ouch.

If we use a set for t instead of a list, and t.add(i) instead of append, then "i not in t" is O(1) instead of O(n), so the algorithm is O(n). For that matter, you don't need the if statement, just add() the value to the set, and duplicates are squashed for you. Then you can see that

Code (Text):
t = set()
for i in x:

is the same as t = set(x), though set(x) is about twice as fast. Which is the method Integrand gave.

So...TIP: when using the "in" operator on a longish collection of items in an inner loop, convert the collection to a set first.

Last edited: Sep 8, 2014
5. Sep 9, 2014

Thanks guys. I haven't studied sets yet. I will try that method when I study it.

6. Sep 9, 2014

### Daverz

Try it with a dictionary, which is how one would have done it before Python had sets. The "in" operator is O(1) for dictionaries.

7. Sep 10, 2014