Sam & Max: Python, Django, Git et du cul

S’affranchir des doublons d’un itérable en Python

mardi 20 août 2013 à 12:10

Supprimer ou ignorer les doublons d’un itérable tel qu’une liste ou un array est un challenge dans tous les langages. Il faut se poser les questions suivantes :

Qu’est-ce qu’un doublon ?
Quels types d’itérables traite-t-on ?
Quel est la taille de l’itérable ?
Et niveau perfs ?

En Python, on a des structures de données qui suppriment automatiquement les doublons : les sets et les dictionnaires. Mais elles ne conservent pas l’ordre des élements.

Il y a aussi le fait qu’un itérable en Python peut avoir une taille inconnue, ou infinie.

Le post est long, donc…

Solution 1 : générateur et hashing

En utilisant conjointement les générateurs, les sets et une petite injection de dépendance, on peut trouver un compromis entre flexibilité et performances :

def skip_duplicates(iterable, key=lambda x: x):
 
    # on va mettre l’empreinte unique de chaque élément dans ce set
    fingerprints = set()
 
    for x in iterable:
        # chaque élement voit son emprunte calculée. Par défaut l’empreinte
        # est l'élément lui même, ce qui fait qu'il n'y a pas besoin de
        # spécifier 'key' pour des primitives comme les ints ou les strings.
        fingerprint = key(x)
 
        # On vérifie que l'empreinte est dans la liste des empreintes  des
        # éléments précédents. Si ce n'est pas le cas, on yield l'élément, et on
        # rajoute sont empreinte ans la liste de ceux trouvés, donc il ne sera
        # pas yieldé si on ne le yieldera pas une seconde fois si on le
        # rencontre à nouveau
        if fingerprint not in fingerprints:
            yield x
            fingerprints.add(fingerprint)

La fonction s’appelle skip_duplicates car c’est ce qu’elle fait. Elle ne retire pas vraiment les doublons, elle produit un flux de d’éléments qui ne comporte pas de doublons en ignorant tout doublons présent dans l’itérable initial.

Cette approche a plusieurs avantages :

Les doublons sont bien retirés, et l’ordre est conservé.
La complexité est de 0(n).
L’utilisateur peut choisir ce qui fait qu’un élément est unique : un attribut, un sous-élément, l’affichage sous forme de string…
C’est un générateur, est cela fonctionne donc avec des itérables de toute taille, même inconnue ou infinie.

Il faut néanmoins que l’ensemble des éléments uniques tiennent au moins une fois en mémoire en plus de l’itérable initial, et potentiellement d’un stockage à la sortie du générateur. On fait donc un trade-off sur la mémoire.

Comme la valeur de key par défaut est une valeur saine, ça fonctionne comme on s’y attend pour les cas simples :

>>> list(skip_duplicates([1, 2, 3, 4, 4, 2, 1, 3 , 4]))
[1, 2, 3, 4]
>>> list(skip_duplicates('fjsqlkdmfjsklqmdfjdmsl'))
[u'f', u'j', u's', u'q', u'l', u'k', u'd', u'm']
>>> list(skip_duplicates(((1, 2), (2, 1), (1, 2), (1, 1))))
[(1, 2), (2, 1), (1, 1)]

Pourvoir spécifier ‘key’ permet de faire des choix dans ce qu’est un doublon :

>>> list(skip_duplicates((1, 2, '1', '1', 2, 3, '3')))
[1, 2, u'1', 3, u'3']
>>> list(skip_duplicates((1, 2, '1', '1', 2, 3, '3'), key=lambda x: str(x)))
[1, 2, 3]

Et si on s’attaque à des cas plus complexes, le fonction vous force à préciser votre pensée :

>>> list(skip_duplicates(([], [], (), [1, 2], (1, 2)))
... )
Traceback (most recent call last):
  File "<ipython-input-20-ed44f170c634>", line 1, in <module>
    list(skip_duplicates(([], [], (), [1, 2], (1, 2)))
  File "<ipython-input-18-42dbb94f03f8>", line 7, in skip_duplicates
    if fingerprint not in fingerprints:
TypeError: unhashable type: 'list'

En effet les listes ne sont pas des types hashables en Python, on ne peut donc pas les stocker dans un set.

Mais on peut caster la liste, et faire ainsi le choix de savoir sur quel critère on base notre égalité. Par exemle, considère-t-on que deux itérables ayant le même contenu sont égaux, où alors doivent-ils avoir le même type ?

>>> list(skip_duplicates(([], [], (), [1, 2], (1, 2)), lambda x: tuple(x)))
[[], [1, 2]]
>>> list(skip_duplicates(([], [], (), [1, 2], (1, 2)), lambda x: (type(x), tuple(x))))
[[], (), [1, 2], (1, 2)]

Nous utilisons le fait que :

>>> tuple([1, 2]) == (1, 2)
True
>>> (type([1, 2]), tuple([1, 2])) == (type((1, 2)), (1, 2))
False

Puisque :

>>> (type([1, 2]), tuple([1, 2]))
(<type 'list'>, (1, 2))
>>> (type((1, 2)), (1, 2))
(<type 'tuple'>, (1, 2))

Dans le cas où nous ne sommes pas capables de déterminer ce qu’est un doublon, la fonction ne retire simplement rien :

class Test(object):
    def __init__(self, foo='bar'):
        self.foo = foo
    def __repr__(self):
        return "Test('%s')" % self.foo
 
>>> list(skip_duplicates([Test(), Test(), Test('other')]))
[Test('bar'), Test('bar'), Test('other')]

Mais permet encore une fois de faire le choix de quoi retirer :

>>> list(skip_duplicates([Test(), Test(), Test('other')], key=lambda x: x.foo))
[Test('bar'), Test('other')]

Ce principe de la fonction key, on le retrouve dans sorted(), donc les habitués seront déjà à l’aise. Et j’aime beaucoup ce pattern, car il est très puissant. On peut avoir la fonction key qui renvoit des choses très simples :

Un attribut.
Un element (x[2], x['cle']…)
Une version castée avec int(), str(), tuple(), etc

Mais on peut aussi faire des choses très complexes. En effet, rien ne nous oblige à utiliser une lambda, on peut mettre une fonction complète et lui faire retourner :

Un hash md5.
Une entrée en base de données.
Un nouvel objet customisé.
Un tuple de tuples d’objets custos avec des dictionnaires en attributs…
Le contenu d’un fichier.

Python sait naturellement comparer tout ça.

Notez que nous trichons un peu, puisque nous retirons les doublons en nous basant sur un set qui va calculer un hash de l’objet, et pas véritablement vérifier l’égalité. La fonction en fonctionnera donc pas si l’utilisateur définie __eq__ et s’attend à ce que les doublons soient retirés. Ce qui nous amène à …

Solution 2 : iterateur et comparaison

Pour ce genre de chose, un autre algo, qui ne fontionerait que sur les itérables de taille finie, et qui serait bien plus lent (complexité n log(n)), peut être utilisé :

def strip_duplicates(iterable, equals=lambda x, y: x == y):
 
    # On transforme l'itérable en iterateur sur lui même, cela va nous
    # permettre d'appeler next() dessus et récupérer le premier élément,
    # même sur un objet non indexable (sur lequel on ne peut utiliser [0])
    iterable = iter(iterable)
 
    res = []
    # Une petite boucle infinie est nécessaire car la boucle 'for' ne nous
    # permet pas de récupérer le premier élément indépendamment des autres,
    # et la boucle 'while' attend une condition de sortie, ce que nous n'avons
    # pas forcément (il n'est pas possible de vérifier le nombre d'éléments
    # restant dans un générateur).
    while True:
 
        # on récupère le premier élément de l'iterable restant, si il n'y en
        # a plus, on sort de la boucle.
        try:
            elem = next(iterable)
        except StopIteration:
            break
 
        # Le premier élément est ajouté au résultat sans doublons. Maintenant
        # on va recréer l'itérable, mais en retirant tout ce qui était égal
        # au premier élément. Notez que 'être égal' est une condition modifiable
        # en passant une fonction en paramètre, comme l'était 'key' précédemment.
        res.append(elem)
 
        iterable = iter([x for x in iterable if not equals(elem, x)])
 
    return res

La fonction s’appelle strip_duplicates car elle produit une nouvelle liste, mais sans les éléments indésirables, comme le fait strip() sur une chaîne (produit une nouvelle chaîne, sans les éléments indésirables).

Ce type de fonction peut être utile dans plusieurs cas :

On a pas envie de se poser la question de savoir si nos types à comparer sont hashable ou pas, et on est prêt à payer un peu de CPU pour cela.
On a besoin de retirer les doublons sur la base d’une égalité, par exemple sur l’existence de la méthode __eq__.
On a besoin de retirer les doublons sur la base d’une logique complexe qui dépend du contexte.

A première vu cela fonctionne presque de la même manière que skip_duplicates, mais en retournant une liste plutôt qu’un générateur :

>>> strip_duplicates('fdjqkslfjdmkfdsqjkfmjqsdmlkfjqslkmfjsdklfl')
['f', 'd', 'j', 'q', 'k', 's', 'l', 'm']

Mais déjà il n’y a pas à se soucier de savoir si une structure de données est hashable :

>>> strip_duplicates(([], [], (), [1, 2], (1, 2)))
[[], (), [1, 2], (1, 2)]

Même si on garde la même flexibilité, bien que la fonction à passer ait une signature légèrement différente :

>>> strip_duplicates(([], [], (), [1, 2], (1, 2)), lambda x, y: tuple(x) == tuple(y))
[[], [1, 2]]

Le plus interessant reste que cela fonctionne sur l’égalité, et donc cela marche d’office avec les objets qui déclarent __eq__ ce qui est le cas dans de nombreuses libs, comme les ORM :

class Test(object):
    def __init__(self, foo='bar'):
        self.foo = foo
    def __repr__(self):
        return "Test('%s')" % self.foo
    def __eq__(self, other):
        return self.foo == other.foo
 
>>> strip_duplicates([Test(), Test(), Test('other')])
[Test('bar'), Test('other')]

Dans certains cas, notamment dans le cas où le point de comparaison est un object non hashable de très grosse taille (par exemple un dico très long), on peut espérer aussi pas mal économiser en mémoire. Mais on est qu’en est-il des besoins en mémoire et en CPU ?

Solution 3 : retirer les doublons, in place

Enfin, pour ceux qui ont de grosses contraintes de mémoire et qui veulent un algo rapide au prix de la flexibilité du code, voici une solution qui oblige à travailler sur des listes et à modifier la liste sur place :

def remove_duplicates(lst, equals=lambda x, y: x == y):
 
    # Normalement en Python on adore le duck typing, mais là cet algo suppose
    # l'usage d'une liste, donc on met un gardefou.
    if not isinstance(lst, list):
        raise TypeError('This function works only with lists.')
 
    # là on est sur quelque chose qui ressemble vachement plus à du code C ^^
    i1 = 0
    l = (len(lst) - 1)
 
    # on itère mécaniquement sur la liste, à l'ancienne, avec nos petites
    # mains potelées.
    while i1 < l:
 
        # on récupère chaque élément de la liste, sauf le dernier
        elem = lst[i1]
 
        # on le compare à l'élément suivant, et chaque élément après
        # l'élément suivant
        i2 = i1 + 1
        while i2 <= l:
            # en cas d'égalité, on retire l'élément de la liste, et on
            # décrément la longueur de la liste ainsi amputée
            if equals(elem, lst[i2]):
                del lst[i2]
                l -= 1
            i2 += 1
 
        i1 += 1
 
    return lst

Et là on est bien dans de la modification sur place :

>>> lst = list('fjdsklmqfjskdfjmld')
>>> lst
[u'f', u'j', u'd', u's', u'k', u'l', u'm', u'q', u'f', u'j', u's', u'k', u'd', u'f', u'j', u'm', u'l', u'd']
>>> remove_duplicates(lst)
[u'f', u'j', u'd', u's', u'k', u'l', u'm', u'q']
>>> lst
[u'f', u'j', u'd', u's', u'k', u'l', u'm', u'q']

La fonction s’appelle cette fois bien remove_duplicates puisque c’est ce qu’elle fait : retirer les doublons de la liste originale.

Et maintenant, c’est l’heure du benchmark à deux balles !

skip_duplicates :

setup = """
def skip_duplicates(iterable, key=lambda x: x):
        fingerprints = set()
        for x in iterable:
                fingerprint = key(x)
                if fingerprint not in fingerprints:
                        yield x
                        fingerprints.add(fingerprint)
import string
lst = list(string.ascii_letters * 100)"""
>>> timeit.timeit('list(skip_duplicates(lst))', setup=setup, number=1000)
0.9810519218444824

strip_duplicates :

>>> setup = """
def strip_duplicates(iterable, equals=lambda x, y: x == y):
    iterable = iter(iterable)
    res = []
    while True:
        try:
            elem = next(iterable)
        except StopIteration:
            break
        res.append(elem)
 
        iterable = iter([x for x in iterable if not equals(elem, x)])
 
    return res
 
import string
lst = list(string.ascii_letters * 100)"""
>>> timeit.timeit('list(strip_duplicates(lst))', setup=setup, number=1000)
41.462974071502686

remove_duplicates :

setup = """
def remove_duplicates(lst, equals=lambda x, y: x == y):
    if not isinstance(lst, list):
        raise TypeError('This function works only with lists.')
    i1 = 0
    l = (len(lst) - 1)
    while i1 < l:
        elem = lst[i1]
        i2 = i1 + 1
        while i2 <= l:
            if equals(elem, lst[i2]):
                del lst[i2]
                l -= 1
            i2 += 1
        i1 += 1
    return lst
 
import string
lst = list(string.ascii_letters * 100)"""
>>> timeit.timeit('list(remove_duplicates(lst))', setup=setup, number=1000)
0.37493896484375

Sans surprise, la version inplace est la plus rapide puisque la plus restrictive. En second vient notre strip_duplicates, beaucoup fois plus lente. Et en dernier, 50 fois plus lente, le compromis entre les deux : souple, consomme moins de mémoire que skip, mais plus que remove.

Mais ce n’est pas très juste pour strip, puisque que skip n’a pas à faire un gros travail de conversion. Essayons avec des clés plus grosses :

skip_duplicates :

setup = """
def skip_duplicates(iterable, key=lambda x: x):
        fingerprints = set()
        for x in iterable:
                fingerprint = key(x)
                if fingerprint not in fingerprints:
                        yield x
                        fingerprints.add(fingerprint)
import string, random
lst = [list(string.ascii_letters * 100) for x in xrange(100)]
for x in lst:
    x.pop(random.randint(0, len(x) - 1))"""
>>> timeit.timeit('list(skip_duplicates(lst, lambda x: tuple(x)))', setup=setup, number=1000)
15.516181945800781

strip_duplicates :

>>> setup = """
def strip_duplicates(iterable, equals=lambda x, y: x == y):
    iterable = iter(iterable)
    res = []
    while True:
        try:
            elem = next(iterable)
        except StopIteration:
            break
        res.append(elem)
 
        iterable = iter([x for x in iterable if not equals(elem, x)])
 
    return res
 
import string, random
lst = [list(string.ascii_letters * 100) for x in xrange(100)]
for x in lst:
    x.pop(random.randint(0, len(x) - 1))"""
>>> timeit.timeit('list(strip_duplicates(lst))', setup=setup, number=1000)
22.047110080718994

remove_duplicates :

setup = """
def remove_duplicates(lst, equals=lambda x, y: x == y):
    if not isinstance(lst, list):
        raise TypeError('This function works only with lists.')
    i1 = 0
    l = (len(lst) - 1)
    while i1 < l:
        elem = lst[i1]
        i2 = i1 + 1
        while i2 <= l:
            if equals(elem, lst[i2]):
                del lst[i2]
                l -= 1
            i2 += 1
        i1 += 1
    return lst
 
import string, random
lst = [list(string.ascii_letters * 100) for x in xrange(100)]
for x in lst:
    x.pop(random.randint(0, len(x) - 1))"""
>>> timeit.timeit('list(remove_duplicates(lst))', setup=setup, number=1000)
14.763166904449463

Comme souvent les résultats sont contre untuitifs, car bien que remove garde son avance, elle s’est largement réduite. A l’inverse, skip n’est pas tant à la ramasse que ça, et strip reste le plus lent.

Il faudrait aussi mesurer la consommation mémoire, je suis certain que ce serait interessant.

Bon, il est temps de mettre tout ça dans batbelt.