Python possède-t-il un ensemble ordonné ?

Question

Python dispose d'un dictionnaire ordonné . Qu'en est-il d'un ensemble ordonné ?

Answer 1

Il existe un ensemble ordonné (possible nouveau lien ) recette pour cela qui est référencée dans le Documentation sur Python 2 . Il fonctionne sur Py2.6 ou plus et 3.0 ou plus sans aucune modification. L'interface est presque exactement la même qu'un ensemble normal, sauf que l'initialisation doit être faite avec une liste.

OrderedSet([1, 2, 3])

Il s'agit d'un MutableSet, donc la signature pour .union ne correspond pas à celle de set, mais puisqu'elle inclut __or__ quelque chose de similaire peut facilement être ajouté :

@staticmethod
def union(*sets):
    union = OrderedSet()
    union.union(*sets)
    return union

def union(self, *sets):
    for set in sets:
        self |= set

Answer 2

Mise à jour : Cette réponse est obsolète à partir de Python 3.7. Voir Réponse de jrc ci-dessus pour une meilleure solution. Je garderai cette réponse ici uniquement pour des raisons historiques.

---

Un ensemble ordonné est fonctionnellement un cas particulier d'un dictionnaire ordonné.

Les clés d'un dictionnaire sont uniques. Ainsi, si l'on ne tient pas compte des valeurs d'un dictionnaire ordonné (par exemple, en les assignant None ), alors on a essentiellement un ensemble ordonné.

A partir de Python 3.1 y 2.7 il y a collections.OrderedDict . Voici un exemple d'implémentation d'un OrderedSet. (Notez que seules quelques méthodes doivent être définies ou surchargées : collections.OrderedDict y collections.MutableSet faire le gros du travail).

import collections

class OrderedSet(collections.OrderedDict, collections.MutableSet):

    def update(self, *args, **kwargs):
        if kwargs:
            raise TypeError("update() takes no keyword arguments")

        for s in args:
            for e in s:
                 self.add(e)

    def add(self, elem):
        self[elem] = None

    def discard(self, elem):
        self.pop(elem, None)

    def __le__(self, other):
        return all(e in other for e in self)

    def __lt__(self, other):
        return self <= other and self != other

    def __ge__(self, other):
        return all(e in self for e in other)

    def __gt__(self, other):
        return self >= other and self != other

    def __repr__(self):
        return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))

    def __str__(self):
        return '{%s}' % (', '.join(map(repr, self.keys())))

    difference = property(lambda self: self.__sub__)
    difference_update = property(lambda self: self.__isub__)
    intersection = property(lambda self: self.__and__)
    intersection_update = property(lambda self: self.__iand__)
    issubset = property(lambda self: self.__le__)
    issuperset = property(lambda self: self.__ge__)
    symmetric_difference = property(lambda self: self.__xor__)
    symmetric_difference_update = property(lambda self: self.__ixor__)
    union = property(lambda self: self.__or__)

Answer 3

Implémentations sur PyPI

Alors que d'autres ont souligné qu'il n'y a pas (encore) d'implémentation intégrée d'un ensemble préservant l'ordre d'insertion en Python, j'ai le sentiment qu'il manque à cette question une réponse qui indique ce qu'il y a à trouver sur PyPI .

Il y a les paquets :

• ensemble ordonné (basé sur Python)
• orderedset (basé sur Cython)
• collections-étendues
• boltons (sous iterutils.IndexedSet (basé sur Python)
• oset (dernière mise à jour en 2012)

Certaines de ces mises en œuvre sont basées sur le recette postée par Raymond Hettinger à ActiveState qui est également mentionné dans d'autres réponses ici.

Quelques différences

• ensemble ordonné (version 1.1)
• avantage : O(1) pour les recherches par index (par ex. my_set[5] )
• oset (version 0.1.3)
• avantage : O(1) pour remove(item)
• inconvénient : apparemment O(n) pour les recherches par indice

Les deux implémentations ont O(1) pour add(item) y __contains__(item) ( item in my_set ).

Answer 4

Il existe une fonction plus simple permettant d'obtenir une OrderedList, fournie au bas de la page de l'article le lien et l'auteur de la fonction a déclaré que "la fonction plus simple suivante fonctionne 4 fois plus vite" :

def OrderedSet(alist):

    """ Creates an ordered set from a list of tuples or other hashable items """

    mmap = {} # implements hashed lookup

    oset = [] # storage for set

    for item in alist:

        #Save unique items in input order

        if item not in mmap:

                mmap[item] = 1

                oset.append(item)

    return oset

Answer 5

Pour de nombreuses raisons, il suffit d'appeler trié. Par exemple

>>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60])
>>> sorted(s)
[0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100]

Si vous utilisez cette fonction de manière répétée, l'appel de la fonction triée entraînera une surcharge de travail, et vous voudrez peut-être sauvegarder la liste résultante, tant que vous n'aurez pas modifié l'ensemble. Si vous avez besoin de maintenir des éléments uniques et triés, je suis d'accord avec la suggestion d'utiliser OrderedDict à partir de collections avec une valeur arbitraire telle que None.