python - Filter a list to only leave objects that occur once

Question

I would like to filter this list,

[0, 1, 1, 2, 2]

to only leave

[0]

I'm struggling to do it in a 'pythonic' way. 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;-).