Bien que Python soit un langage massivement utilisé par la communauté scientifique, la lib standard ne contient pas de fonction aussi simple que sign(). Et on voit ça et là des libs qui contiennent quelque chose comme ça:

def sign(x):
    if x > 0:
        return 1
    if x == 0:
        return 0
    return -1
 
>>> sign(3)
1
>>> sign(-3)
-1
>>> sign(0)
0

Comme d’autres de choix étonnants dans l’architecture de Python, il y a une raison raisonnablement raisonnable : il n’existe aucun standard sur ce que doit faire une telle fonction dans les cas ambigües.

En effet, que doit faire la fonction avec NaN ? Avec un complexe ?

Il y a eu un débat sur ce qu’il faut faire dans ce cas, et un consensus n’a PAS été trouvé.

Par contre, il existe un standard international définissant une autre opération : celle de copier un signe. Elle a donc été implémentée :

>>> from math import copysign
>>> copysign(10, -3)
-10.0
>>> copysign(10, 22)
10.0
>>> copysign(10, float('-NaN'))
-10
>>> copysign(10, -2j)
Traceback (most recent call last):
  File "<ipython-input-13-ece93d1317dc>", line 1, in <module>
    copysign(10, -2j)
TypeError: can't convert complex to float

Copier le signe n’est pas la même chose que de retourner quelque chose selon le signe, et donc sémantiquement, choisir quoi retourner était plus facile. Comme la plupart du temps, on veut récupérer -1 ou 1 pour le multiplier avec quelque chose et justement copier le signe, cela résolvait pas mal de problèmes.

Mais même dans le rare cas où on a besoin du résultat que renverrait sign(), il est très facile à obtenir en une ligne :

>>> mon_nombre = 3
>>> mon_nombre and copysign(1, mon_nombre)
1.0
>>> mon_nombre = -3
>>> mon_nombre and copysign(1, mon_nombre)
-1.0
>>> mon_nombre = 0
>>> mon_nombre and copysign(1, mon_nombre)
0

Et pour ce cas de figure, les retours sur des valeurs ambigües sont laissés à la charge du codeur.

P.S: je sais qu’il y a des exemples sur le net montrant cmp(0, mon_nombre) pour obtenir la même fonctionnalité. Sachez que cmp a été retirée de Python 3, donc faites attention si vous l’utilisez.

Des structures un peu imbriquées ne sont pas trop difficiles à traiter en Python.

Par exemple, avec une liste en intention imbriquée :

>>> l = [(1, 2), (3, 4), (5, 6)]
>>> [y for x in l for y in x]
[1, 2, 3, 4, 5, 6]

Mais quand on a beaucoup de niveaux, par exemple…

a = []
for i in xrange(500):
    a = [a, i]
print(a)

[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[], 0], 1], 2], 3], 4], 5], 6], 7], 8], 9], 10], 11], 12], 13], 14], 15], 16], 17], 18], 19], 20], 21], 22], 23], 24], 25], 26], 27], 28], 29], 30], 31], 32], 33], 34], 35], 36], 37], 38], 39], 40], 41], 42], 43], 44], 45], 46], 47], 48], 49], 50], 51], 52], 53], 54], 55], 56], 57], 58], 59], 60], 61], 62], 63], 64], 65], 66], 67], 68], 69], 70], 71], 72], 73], 74], 75], 76], 77], 78], 79], 80], 81], 82], 83], 84], 85], 86], 87], 88], 89], 90], 91], 92], 93], 94], 95], 96], 97], 98], 99], 100], 101], 102], 103], 104], 105], 106], 107], 108], 109], 110], 111], 112], 113], 114], 115], 116], 117], 118], 119], 120], 121], 122], 123], 124], 125], 126], 127], 128], 129], 130], 131], 132], 133], 134], 135], 136], 137], 138], 139], 140], 141], 142], 143], 144], 145], 146], 147], 148], 149], 150], 151], 152], 153], 154], 155], 156], 157], 158], 159], 160], 161], 162], 163], 164], 165], 166], 167], 168], 169], 170], 171], 172], 173], 174], 175], 176], 177], 178], 179], 180], 181], 182], 183], 184], 185], 186], 187], 188], 189], 190], 191], 192], 193], 194], 195], 196], 197], 198], 199], 200], 201], 202], 203], 204], 205], 206], 207], 208], 209], 210], 211], 212], 213], 214], 215], 216], 217], 218], 219], 220], 221], 222], 223], 224], 225], 226], 227], 228], 229], 230], 231], 232], 233], 234], 235], 236], 237], 238], 239], 240], 241], 242], 243], 244], 245], 246], 247], 248], 249], 250], 251], 252], 253], 254], 255], 256], 257], 258], 259], 260], 261], 262], 263], 264], 265], 266], 267], 268], 269], 270], 271], 272], 273], 274], 275], 276], 277], 278], 279], 280], 281], 282], 283], 284], 285], 286], 287], 288], 289], 290], 291], 292], 293], 294], 295], 296], 297], 298], 299], 300], 301], 302], 303], 304], 305], 306], 307], 308], 309], 310], 311], 312], 313], 314], 315], 316], 317], 318], 319], 320], 321], 322], 323], 324], 325], 326], 327], 328], 329], 330], 331], 332], 333], 334], 335], 336], 337], 338], 339], 340], 341], 342], 343], 344], 345], 346], 347], 348], 349], 350], 351], 352], 353], 354], 355], 356], 357], 358], 359], 360], 361], 362], 363], 364], 365], 366], 367], 368], 369], 370], 371], 372], 373], 374], 375], 376], 377], 378], 379], 380], 381], 382], 383], 384], 385], 386], 387], 388], 389], 390], 391], 392], 393], 394], 395], 396], 397], 398], 399], 400], 401], 402], 403], 404], 405], 406], 407], 408], 409], 410], 411], 412], 413], 414], 415], 416], 417], 418], 419], 420], 421], 422], 423], 424], 425], 426], 427], 428], 429], 430], 431], 432], 433], 434], 435], 436], 437], 438], 439], 440], 441], 442], 443], 444], 445], 446], 447], 448], 449], 450], 451], 452], 453], 454], 455], 456], 457], 458], 459], 460], 461], 462], 463], 464], 465], 466], 467], 468], 469], 470], 471], 472], 473], 474], 475], 476], 477], 478], 479], 480], 481], 482], 483], 484], 485], 486], 487], 488], 489], 490], 491], 492], 493], 494], 495], 496], 497], 498], 499]

Là je désactive la coloration syntaxique du blog parce que le snippet à fait planté sublime :-D Heureusement, il reste VI.

Bref, quand on a ce genre de truc, comment on fait ? Pire, comment ont traite un flux de données de types hétérogènes, et dont on ne connait pas la taille, ou de longueur infinie ? C’est une caractéristique de Python : on a des générateurs plein de duck typing partout !

Voici un petit snippet un peu tordu, mais qui fait des merveilles :

from collections import deque, OrderedDict, MutableSet, defaultdict
 
 
class Flattener(object):
 
    # les types qu'on va applatir, c'est à dire la plupart
    # des iterables sauf les hashmaps
    DEFAULT_FLATTEN_TYPES = (
        list,
        tuple,
        set,
        (x for x in ()).__class__,
        xrange,
        deque,
        MutableSet,
    )
 
    # par défaut, on utilise DEFAULT_FLATTEN_TYPES et
    # aucun iterable_getters (on verra ce que c'est plus bas)
    # puisque c'est le cas le plus courant d'utilisation
    def __init__(self, flatten_types=None, iterable_getters={}):
        self.flatten_types = flatten_types or self.DEFAULT_FLATTEN_TYPES
        self.iterable_getters = iterable_getters
 
 
    # Retourne True si on doit applatir l'objet.
    # Par défaut, vérifie dans si l'objet est d'un des types
    # DEFAULT_FLATTEN_TYPE.
    def should_flatten(self, obj):
        return isinstance(obj, self.flatten_types)
 
    # Si avant d'applatir l'objet, l'objet a besoin d'une transformation
    # (par exemple appeler items() sur un dico), on l'applique. 
    # Par défaut il n'y a aucune transformation appliquée, quelque soit le 
    # type.
    def transform_iterable(self, obj):
        if obj.__class__ in self.iterable_getters:
            return self.iterable_getters[obj.__class__](obj)
        return obj
 
 
    # Permet d'appeler une instance de Flatener, comme si c'était une fonction
    def __call__(self, iterable):
        for e in:
            # Si un élément est à applatir, on fait un appel récursif
            if self.should_flatten(e):
                # Appel récursif, et yielding du résultat de cet appel.
                for f in self(self.transform_iterable(e)):
                    yield f
            # On ne doit pas applatir l'element (genre un int, un str...)
            # donc on le yield directement
            else:
                yield e
 
 
# fabrique un flattener, ici on prend la config par défaut
flatten = Flattener()
 
# et pouf
 
a = []
for i in xrange(500):
    a = [a, i]
 
applatie = list(flatten(a))
 
print(len(applatie))
print(applatie[:10])
5500
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Ca gère une longeur infinie, et une imbrication de centaines de niveaux. Comme Python a une limite de recursions (1000 par défaut), on est quand même bridé, mais c’est une situation rare d’avoir autant de nesting. Et dans les cas extrêmes, on peut allouer une plus grande stack avec sys.setrecursionlimit().

Via flatten_types, on peut créer différentes politiques d’applatissement, bien que celle par défaut soit assez saine. Par exemple décider d’applatir les strings, ou ne pas applatir les tuples : il suffit de passer la bonne liste de types en paramètres. Comme le Flattener est une classe qui permet de créer flatten(), on peut la sous-classer et mettre à disposition plusieurs applatisseurs personnalisés dans sa lib.

La partie :

                if e.__class__ in self.iterable_getters:
                    e = self.iterable_getters[e.__class__](e)

Permet de gérer des cas ambigües, comme par exemple les dicos. Comment itérer dessus ? Par clé, par valeur ? Par défaut on ne les applatis pas

On peut par exemple choisir d’applatir complètement les dictionnaires. :

a = []
for i in xrange(2):
    a = [a, i] + [{'a': 1., 'b': {'c': 3.}}]
print(a)
 
[[[], 0, {'a': 1.0, 'b': {'c': 3.0}}], 1, {'a': 1.0, 'b': {'c': 3.0}}]
 
# on rajoute les dictionnaires aux types à applatir
new_ft = Flattener.DEFAULT_FLATTEN_TYPES + (dict,)
 
dico_flatten = Flattener(flatten_types=new_ft,
                         # on dit qu'un dico rencontré doit être transformé
                         # via items() avant iteration
                         iterable_getters={dict: lambda x: x.items()})
 
print(list(dico_flatten(a)))
 
[0, u'a', 1.0, u'b', u'c', 3.0, 1, u'a', 1.0, u'b', u'c', 3.0]

On peut même overrider should_flatten et transform_iterable si des besoins plus importants se font sentir.

Attention tout de même à ce que vous mettez dans flatten_types. Par exemple, une string d’un caractère est à la fois yieldable comme valeur et itérable, ce qui va provoquer une recursion infinie. Adaptez toujours iterable_getters en conséquence.

Hop, dans batbelt.

Ceci est un post invité de golgotha posté sous licence creative common 3.0 unported.

On peut objecter aux hommes de trop se décharger devant youjizz (il est où le rouleau de sopalin ??) mais cela a un avantage indéniable… On acquiert un bac+8 en porn à force d’étudier les arts de combat des autres mecs, on apprend des techniques plus ou moins efficaces et devenir maître dans l’art de la galipette n’est pas chose aisée ! ça ne vient pas comme ça, en claquant des doigts.

Les femmes ayant longtemps été considérée comme des objets pour les hommes, en leur inculquant une morale chrétienne et la culpabilité d’une sexualité libérée, elles doivent aujourd’hui surmonter ce passé pour apprécier une vidéo porno, qui je le rappelle n’est pas forcément vulgaire. Le truc c’est que les femmes qui s’interdisent tout accès à la pornographie pour la simple raison que ce n’est pas catholique, auront plus de mal d’une manière général à comprendre ce que désire un homme, par manque de curiosité et par manque d’expérience, expérience que l’on peux acquérir justement en allant à droite et à gauche regarder quelques vidéos amateurs. De plus, on voit maintenant fleurir sur les sites des catégories moins hard, plus pour les femmes curieuses de voir quelques vidéos soft genre dimanche soir sur M6.

Exemple n°1 : je branle mon mec comme un cheval, très vite et très fort, ça va lui faire du bien. WTF, mais arrêtez de nous prendre pour un animal quoi, déjà niveau plaisir ce n’est pas ça, pire ça peut faire mal ! Un peu de sensualité, de délicatesse, combien de femmes savent qu’on peut faire jouir un mec sans même le toucher ? Et oui… Et ça c’est vraiment un manque de culture érotique, message pour les femmes : Allez regarder du porn !!

Exemple n°2, la pipe mécanique, genre je regonfle mon pneu… Une bonne fois pour toute : un pipe comme ça, sans regard échangé, de façon mécanique, c’est ZERO sur l’échelle du plaisir pour un mec. Désolé de vous décevoir mais ça fait autant d’effet que de la crème solaire sur le dos d’une tortue. Pourtant,ce ne sont pas les idées qui manquent, encore une fois le plaisir d’une pipe sera décuplé par la sensualité, par le jeu amoureux, une femme qui masturbe lentement son mec avec sa bouche juste à coté, qui induit qu’elle pourrait le lécher sans le lécher, ça c’est l’extase pour le mec.

Les femmes : Allez voir du porn amateur (pas des gangbangs pro, ça, ça ne sert à rien), il y a pas mal de vidéos soft et sensuelles qui donnent des idées et surtout qui vous feront changer d’avis sur la manière de faire bander un mec, parce que vraiment, parfois il y a du boulot…

Si vous vous souvenez, on ne peut pas mettre un antislash à la fin d’une raw string :

>>> print(r'Moi pouvoir\\')
Moi pouvoir\\
>>> r'Moi pouvoir\\'
'Moi pouvoir\\\\'
>>> r'Moi pouvoir\'
  File "<stdin>", line 1
    r'Moi pouvoir\'
                  ^
SyntaxError: EOL while scanning string literal

La plupart du temps on s’en branle.

Mais supposons que vous vouliez créer un path pour disons, pauvre de vous, une commande DOS…

>>> print("\chemin\vers\dossier\dos\\")
\chemin
        ers\dossier\dos\
>>> print(r"\chemin\vers\dossier\dos\\")
\chemin\vers\dossier\dos\\

Ah, ah, te voilà bien baisé, cher programmeur !

Sauf que non, car une raw string n’est pas un type de string particulier, comme on l’a vu ici, donc on peut faire ça :

>>> print(r"\chemin\vers\dossier\dos" + "\\")
\chemin\vers\dossier\dos\

Zooooo !

Et même si on se sent chaud, on peut utiliser la concaténation implicite pour se la jouer mega chaud du slip :

>>> print(r"\chemin\vers\dossier\dos" "\\")
\chemin\vers\dossier\dos\

Qu’il en faut peu pour qu’un dev se sente le roi du monde…

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.