What is the most efficient way to find if something is repeated in a list?

Question

Let's say I have a list:

l = ['a', 'b', 'c', 'd', 'e', 'f', 'e']

As you can see, indexes 4 and 6 are repeated. My question is: What is the most efficient way to see if the list has something repeated in it?

option 1:

output = len(set(l)) != len(l):

If output is false, then there is a value in there more than once.

option 2:

output = True
for i in l:
  if l.count(i) > 1:
    output = False

If output is false, then there is a value in there more than once.

Questions:

1. What is the most efficient way of doing this?

2. How do I calculate the O notation of these two (or more?) options?

Thanks!

Answer 1

About calculating the O() value:

Option 1 does 4 things: create a set, get its length, get the length of the list, and then compare them. Of these, creating the set must be at least O(n) and the others are at most that, so the efficiency is dominated by the set creation. I believe the implementations of sets in Python is such that insertion takes O(1) on average, and thus this should be O(n).

Option 2 contains a loop. Inside the loop, you call l.count, which iterates over the entire list to count the number of times an item occurs. So each iteration is O(n). The loop itself runs for every item in the loop, so n times. The total efficiency is O(n*n).

Whether something faster than option 1 exists depends on the characterics of your real data, its length, likelihood of a duplication, number of different items (if they are all lower case letters, then any list with length > 26 has a duplication, that's really fast to check) and so on. It can't be answered. But O(n) is really hard to beat, if duplications are rare then usually all items will have to be checked, and that is necessarily O(n) already.

Answer 2

Loop and collect seen items in a set.

Note the break as soon as the first duplicate is found. In the extrem (no duplicates) you will loop the list once and build a set containing every list item.

l = ['a', 'b', 'c', 'd', 'e', 'f', 'e']
seen = set()

for x in l:
    if x in seen:
        print("seen '{}' already, done".format(x))
        # As soon as find find the first duplicate, break.
        break
    seen.add(x)

Output:

seen 'e' already, done

Answer 3

Option 1 is fast.

Because set method uses hashing and len method takes O(1) time.

Hence it is fastest way anyone could do.

https://wiki.python.org/moin/TimeComplexity

Answer 4

Here is the simplest speed comparison I could come up with.

Option 1 essentially boils down to creating a set from a list:

(dev) go|c:\srv\tmp> python -m timeit "set(range(100))"
100000 loops, best of 3: 5.48 usec per loop

while option 2 boils down to iterating over the list and doing a membership test (and a set add that I'm skipping):

(dev) go|c:\srv\tmp> python -m timeit "for i in range(100): i in set()"
10000 loops, best of 3: 22.1 usec per loop

(dev) go|c:\srv\tmp> python -m timeit "for i in range(50): i in set()"
100000 loops, best of 3: 10 usec per loop

(dev) go|c:\srv\tmp> python -m timeit "for i in range(25): i in set()"
100000 loops, best of 3: 5.2 usec per loop

so, the first duplicate will have to be at most 25% into the list for option 2 to be faster, and adding the second set operation will make the comparison much worse for Option 2.

Answer 5

A solution which gives you all the information in a nice dictionary format would be the following:

from collections import Counter

l = ['a', 'b', 'c', 'd', 'e', 'f', 'e']

# Get how many of each exist.
counts = Counter(l)
# Looks like this:
# Counter({'e': 2, 'd': 1, 'c': 1, 'f': 1, 'a': 1, 'b': 1})

# Print letters which have 2 or more instances.
for i in counts:
    if counts[i] > 1:
        print(i, counts[i])

Once you've got this, accessing individual dictionary elements can be done in constant time. Though printing every duplicate would take O(n) time still. This, as well as the initial cost of the Counter which is also O(n) makes O(2n), approximating to O(n).