Python filter a list to only leave objects that occur once

Question

Hello,

I would like to filter this list,

l = [0,1,1,2,2]

to only leave,

[0].

I'm struggling to do it in a 'pythonic' way :o) Is it possible without nested loops?

Answer 1

You'll need two loops (or equivalently a loop and a listcomp, like below), but not nested ones:

import collections
d = collections.defaultdict(int)
for x in L: d[x] += 1
L[:] = [x for x in L if d[x] == 1]

This solution assumes that the list items are hashable, that is, that they're usable as indices into dicts, members of sets, etc.

The OP indicates they care about object IDENTITY and not VALUE (so for example two sublists both worth [1,2,3 which are equal but may not be identical would not be considered duplicates). If that's indeed the case then this code is usable, just replace d[x] with d[id(x)] in both occurrences and it will work for ANY types of objects in list L.

Mutable objects (lists, dicts, sets, ...) are typically not hashable and therefore cannot be used in such ways. User-defined objects are by default hashable (with hash(x) == id(x)) unless their class defines comparison special methods (__eq__, __cmp__, ...) in which case they're hashable if and only if their class also defines a __hash__ method.

If list L's items are not hashable, but are comparable for inequality (and therefore sortable), and you don't care about their order within the list, you can perform the task in time O(N log N) by first sorting the list and then applying itertools.groupby (almost but not quite in the way another answer suggested).

Other approaches, of gradually decreasing perfomance and increasing generality, can deal with unhashable sortables when you DO care about the list's original order (make a sorted copy and in a second loop check out repetitions on it with the help of bisect -- also O(N log N) but a tad slower), and with objects whose only applicable property is that they're comparable for equality (no way to avoid the dreaded O(N**2) performance in that maximally general case).

If the OP can clarify which case applies to his specific problem I'll be glad to help (and in particular, if the objects in his are ARE hashable, the code I've already given above should suffice;-).

Answer 2

[x for x in the_list if the_list.count(x)==1]

Though that's still a nested loop behind the scenes.

Answer 3

>>> l = [0,1,1,2,2]
>>> [x for x in l if l.count(x) is 1]
[0]

Answer 4

Something like

import itertool
res = [elem[0] for elem in itertools.groupby(l) if elem[1].next() == 0]

should work. I do not know about its complexity, though.

Answer 5

l = [0,1,2,1,2]
def justonce( l ):
    once = set()
    more = set()
    for x in l:
        if x not in more:
            if x in once:
                more.add(x)
                once.remove( x )
            else:
                once.add( x )
    return once

print justonce( l )

Answer 6

Here's another dictionary oriented way:

l = [0, 1, 1, 2, 2]
d = {}
for i in l: d[i] = d.has_key(i)

[k for k in d.keys() if not d[k]]

Answer 7

In the same spirit as Alex's solution you can use a Counter/multiset (built in 2.7, recipe compatible from 2.5 and above) to do the same thing:

In [1]: from counter import Counter

In [2]: L = [0, 1, 1, 2, 2]

In [3]: multiset = Counter(L)

In [4]: [x for x in L if multiset[x] == 1]
Out[4]: [0]

Answer 8

I think the actual timings are kind of interesting:

Alex' answer:

python -m timeit -s "l = range(1,1000,2) + range(1,1000,3); import collections" "d = collections.defaultdict(int)" "for x in l: d[x] += 1" "l[:] = [x for x in l if d[x] == 1]"
1000 loops, best of 3: 370 usec per loop

Mine:

python -m timeit -s "l = range(1,1000,2) + range(1,1000,3)" "once = set()" "more = set()" "for x in l:" " if x not in more:" "  if x in once:" "   more.add(x)" "   once.remove( x )" "  else:" "   once.add( x )"
1000 loops, best of 3: 275 usec per loop

sepp2k's O(n**2) version, to demonstrate why compexity matters ;-)

python -m timeit -s "l = range(1,1000,2) + range(1,1000,3)" "[x for x in l if l.count(x)==1]"
100 loops, best of 3: 16 msec per loop

Roberto's + sorted:

python -m timeit -s "l = range(1,1000,2) + range(1,1000,3); import itertools" "[elem[0] for elem in itertools.groupby(sorted(l)) if elem[1].next()== 0]"
1000 loops, best of 3: 316 usec per loop

mhawke's:

python -m timeit -s "l = range(1,1000,2) + range(1,1000,3)" "d = {}" "for i in l: d[i] = d.has_key(i)" "[k for k in d.keys() if not d[k]]"
1000 loops, best of 3: 251 usec per loop

I like the last, clever and fast ;-)

Answer 9

>>> l = [0,1,1,2,2]
>>> [x for x in l if l.count(x) == 1]
[0]