python get non repeating items - fastest method

Question

I am searching for items that are not repeated in a list in python. The current way I do it is,

python -mtimeit -s'l=[1,2,3,4,5,6,7,8,9]*99' '[x for x in l if l.count(x) == 1]'
100 loops, best of 3: 12.9 msec per loop

Is it possible to do it faster?

This is the output.

>>> l = [1,2,3,4,5,6,7,8,9]*99+[10,11]
>>> [x for x in l if l.count(x) == 1]
[10, 11]

This is something like `O(n^2)`. Using a hash set can give you `O(nlogn)`. — BartoszKP, Sep 21 '13 at 20:08
How would you expect l to have non-repeating items when you are repeating itself? — Srinivas Reddy Thatiparthy, Sep 21 '13 at 20:08
BartoszKP, I'll lookup what you said, but an example would help. Srinivas, that's not the point of the question. It's about speed. — Omair ., Sep 21 '13 at 20:10
@Omair.: If speed is a concern, don't implement it in Python. Write a C extension. — Blender, Sep 21 '13 at 20:15

score 3 · Accepted Answer · answered Sep 21 '13 at 20:10

You can use the Counter class from collections:

from collections import Counter
...
[item for item, count in Counter(l).items() if count == 1]

My results:

$ python -m timeit -s 'from collections import Counter; l = [1, 2, 3, 4, 5, 6, 7, 8, 9] * 99' '[item for item, count in Counter(l).items() if count == 1]'
1000 loops, best of 3: 366 usec per loop
$ python -mtimeit -s'l=[1,2,3,4,5,6,7,8,9]*99' '[x for x in l if l.count(x) == 1]'
10 loops, best of 3: 23.4 msec per loop

Awesome! Speed increases, 457usec. – Omair . Sep 21 '13 at 20:13 — Omair ., Sep 21 '13 at 20:13

score 0 · Answer 2 · edited May 23 '17 at 10:29

0

Basically you want to remove duplicate entries, so there are some answers here:

Using in as opposed to count() should be a little quicker because the query is done once it finds the first instance.

edited May 23 '17 at 10:29

Community

1
1

answered Sep 21 '13 at 20:13

eacousineau

3,327
2
32
37

3

These are different problems. – Blender Sep 21 '13 at 20:13
Hmm... How so? Would the `f7()` function not address that, using a `set()`? – eacousineau Sep 21 '13 at 20:16
1

`f([1, 2, 3, 3])` should return `[1, 2]`, not `[1, 2, 3]`, as `3` appeared more than once. – Blender Sep 21 '13 at 20:17
Ah, I think I get it now. OP wants to count the number of non-unique elements. My bad. – eacousineau Sep 21 '13 at 20:17

python get non repeating items - fastest method

2 Answers2

Related