Expert Python Programming - Third Edition

Using sets

When you need to build a sequence of distinct values from a given sequence, the first algorithm that might come to mind is as follows:

>>> sequence = ['a', 'a', 'b', 'c', 'c', 'd']
>>> result = []
>>> for element in sequence:
...     if element not in result:
...         result.append(element)
... 
>>> result
['a', 'b', 'c', 'd']  

In the preceding example, the complexity is introduced by the lookup in the result list with the in operator has a time complexity of O(n). It is then used in the loop, which costs O(n). So, the overall complexity is quadratic, that is, O(n²).

Using a set type for the same work will be faster because the stored values are looked up using hashes, as in dict. set also ensures the uniqueness of elements, so we don't ...