Python a-t-il un ensemble ordonné?

477

Python a un dictionnaire ordonné . Et un ensemble commandé?

Casebash
la source
18
et l'inverse, un sac de choses? (non ordonné et non unique)
wim
19
@wim collections.Counterest le sac de Python.
flornquake du
1
Et si quelque chose est ajouté deux fois? Quelle devrait être la position?
McKay
2
@McKay - s'il devait suivre le comportement des collections, OrderDict serait toujours dans la position de l'ajout initial
wojtow

Réponses:

206

Il existe une recette d' ensemble ordonné ( nouveau lien possible ) pour cela, à laquelle se réfère la documentation Python 2 . Cela fonctionne sur Py2.6 ou version ultérieure et 3.0 ou version ultérieure sans aucune modification. L'interface est presque exactement la même qu'un ensemble normal, sauf que l'initialisation doit être effectuée avec une liste.

OrderedSet([1, 2, 3])

Il s'agit d'un MutableSet, donc la signature de .unionne correspond pas à celle de set, mais comme il inclut __or__quelque chose de similaire, il 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
Casebash
la source
6
J'ai choisi ma propre réponse parce que la référence de la documentation le rapproche d'une réponse officielle
Casebash
49
L'interface est pas exactement le même que l'objet de consigne normal, de nombreuses méthodes essentielles manquent, comme update, union, intersection.
xApple
5
Pour info, j'ai remarqué qu'une version légèrement modifiée de la recette citée dans cette réponse a été ajoutée à PyPi en tant que "set ordonné"
Geoffrey Hing
7
Je suis sûr que vous n'êtes pas autorisé à avoir deux méthodes appelées uniondans la même classe. Le dernier "gagnera" et le premier n'existera pas lors de l'exécution. C'est parce que OrderedSet.union(pas de parens) doit se référer à un seul objet.
Kevin
3
Il existe également un package "orderset "qui est basé sur la même recette mais implémenté dans Cython - pypi.python.org/pypi/orderedset .
mbdevpl
149

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

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

Depuis Python 3.1 il y en a collections.OrderedDict. Voici un exemple d'implémentation d'un OrderedSet. (Notez que seules quelques méthodes doivent être définies ou remplacées: collections.OrderedDictet collections.MutableSetfaites 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 = __sub__ 
    difference_update = __isub__
    intersection = __and__
    intersection_update = __iand__
    issubset = __le__
    issuperset = __ge__
    symmetric_difference = __xor__
    symmetric_difference_update = __ixor__
    union = __or__
Stephan202
la source
1
@Casebash: oui, on peut vouloir définir une classe OrderedSetqui sous OrderedDict- classe abc.Setet puis définir __len__, __iter__et __contains__.
Stephan202
1
@ Stephan202: Malheureusement, la collection ABCs vit collections, mais sinon une bonne suggestion
u0b34a0f6ae
4
C'est vrai, mais vous avez en conséquence beaucoup d'espace perdu, ce qui conduit à des performances sous-optimales.
Daniel Kats
3
Une addition; collections.OrderedDict est également disponible en python 2.7.
Nurbldoff
2
Faire OrderedSet([1,2,3])déclenche une TypeError. Comment fonctionne même le constructeur? Exemple d'utilisation manquant.
xApple
90

La réponse est non, mais vous pouvez utiliser collections.OrderedDictla bibliothèque standard Python avec juste des clés (et des valeurs comme None) dans le même but.

Mise à jour : à partir de Python 3.7 (et CPython 3.6), le standard dictest garanti pour préserver l'ordre et est plus performant que OrderedDict. (Pour des raisons de compatibilité descendante et surtout de lisibilité, cependant, vous pouvez continuer à utiliser OrderedDict.)

Voici un exemple d'utilisation à utiliser dictcomme ensemble ordonné pour filtrer les éléments en double tout en préservant l'ordre, émulant ainsi un ensemble ordonné. Utilisez la dictméthode de classe fromkeys()pour créer un dict, puis demandez simplement le keys()verso.

>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']

>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']
jrc
la source
4
Il convient peut-être de mentionner que cela fonctionne également (plus rapidement) avec la vanille dict.fromkeys(). Mais dans ce cas, l'ordre des clés n'est conservé que dans les implémentations de CPython 3.6+, donc OrderedDictc'est une solution plus portable lorsque l'ordre est important.
Jez
1
ne fonctionnera pas si les valeurs ne sont pas des chaînes
Anwar Hossain
4
@AnwarHossain keys = (1,2,3,1,2,1) list(OrderedDict.fromkeys(keys).keys())-> [1, 2, 3], python-3.7. Ça marche.
raratiru
1
Pouvons-nous en déduire que Set in Python 3.7+ préserve également l'ordre?
user474491
2
@ user474491 Contrairement à dict, setdans Python 3.7+, malheureusement, ne conserve pas l'ordre.
cz
39

Je peux vous faire mieux qu'un OrderedSet: boltons a un IndexedSettype compatible Python pur, 2/3 qui n'est pas seulement un ensemble ordonné, mais prend également en charge l'indexation (comme avec les listes).

Simplement pip install boltons(ou copiez setutils.pydans votre base de code), importez le IndexedSetet:

>>> from boltons.setutils import IndexedSet
>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'

Tout est unique et conservé dans l'ordre. Divulgation complète: j'ai écrit le IndexedSet, mais cela signifie également que vous pouvez me bogue s'il y a des problèmes . :)

Mahmoud Hashemi
la source
39

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 de préservation de l'ordre d'insertion en Python, j'ai le sentiment qu'il manque une réponse à cette question qui indique ce qu'il y a à trouver sur PyPI .

Il y a les packages:

Certaines de ces implémentations sont basées sur la recette publiée par Raymond Hettinger sur ActiveState, qui est également mentionnée dans d'autres réponses ici.

Quelques différences

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

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

Daniel K
la source
2
Un nouveau concurrent est collections_extended.setlist . Les fonctions comme set.unionne fonctionnent pas dessus, même si elles héritent collections.abc.Set.
timdiels
3
OrderedSetprend désormais en chargeremove
warvariuc
17

Si vous utilisez l'ensemble ordonné pour maintenir un ordre trié, envisagez d'utiliser une implémentation d'ensemble trié de PyPI. Le module sortedcontainers fournit un SortedSet à cet effet. Quelques avantages: pure Python, implémentations rapides comme C, couverture de tests unitaires à 100%, heures de tests de stress.

L'installation à partir de PyPI est facile avec pip:

pip install sortedcontainers

Notez que si vous ne le pouvez pas pip install, déroulez simplement les fichiers sortedlist.py et sortedset.py du référentiel open-source .

Une fois installé, vous pouvez simplement:

from sortedcontainers import SortedSet
help(SortedSet)

Le module sortedcontainers maintient également une comparaison des performances avec plusieurs implémentations alternatives.

Pour le commentaire qui a posé une question sur le type de données de sac de Python, il existe également un type de données SortedList qui peut être utilisé pour implémenter efficacement un sac.

GrantJ
la source
Notez que la SortedSetclasse exige que les membres soient comparables et lavables.
gsnedders
4
@gsnedders Les builtins setet frozensetnécessitent également que les éléments soient lavables. La contrainte comparable est l'addition pour SortedSet, mais c'est aussi une contrainte évidente.
gotgenes
2
Comme son nom l'indique, cela ne maintient pas l'ordre. Ce n'est que trié (set ([séquence])) qui fait mieux?
ldmtwo
@ldmtwo Je ne sais pas de quoi vous parlez mais juste pour être clair, SortedSet dans le cadre des conteneurs triés maintient l'ordre de tri.
GrantJ
2
@GrantJ - C'est la différence entre le maintien de l' ordre d' insertion ou de l' ordre de tri . La plupart des autres réponses concernent l'ordre d'insertion. Je pense que vous en êtes déjà conscient sur la base de votre première phrase, mais c'est probablement ce que dit ldmtwo.
Justin
9

Si vous utilisez déjà des pandas dans votre code, son Indexobjet se comporte à peu près comme un ensemble ordonné, comme indiqué dans cet article .

Exemples tirés de l'article:

indA = pd.Index([1, 3, 5, 7, 9])
indB = pd.Index([2, 3, 5, 7, 11])

indA & indB  # intersection
indA | indB  # union
indA - indB  # difference
indA ^ indB  # symmetric difference
Berislav Lopac
la source
Pouvez-vous inclure un exemple dans cette réponse? Les liens ont tendance à être rompus après un certain temps.
Alechan
1
pour la différence entre les ensembles, vous devez réellement utiliser indA.difference(indB), le signe moins effectue une soustraction standard
gg349
7

Un peu tard pour le jeu, mais je l' ai écrit une classe setlistdans le cadre de collections-extendedce que met en œuvre à la fois pleinement SequenceetSet

>>> from collections_extended import setlist
>>> sl = setlist('abracadabra')
>>> sl
setlist(('a', 'b', 'r', 'c', 'd'))
>>> sl[3]
'c'
>>> sl[-1]
'd'
>>> 'r' in sl  # testing for inclusion is fast
True
>>> sl.index('d')  # so is finding the index of an element
4
>>> sl.insert(1, 'd')  # inserting an element already in raises a ValueError
ValueError
>>> sl.index('d')
4

GitHub: https://github.com/mlenzen/collections-extended

Documentation: http://collections-extended.lenzm.net/en/latest/

PyPI: https://pypi.python.org/pypi/collections-extended

Michael Lenzen
la source
7

Il n'y OrderedSeten a pas dans la bibliothèque officielle. Je fais une feuille de triche exhaustive de toute la structure de données pour votre référence.

DataStructure = {
    'Collections': {
        'Map': [
            ('dict', 'OrderDict', 'defaultdict'),
            ('chainmap', 'types.MappingProxyType')
        ],
        'Set': [('set', 'frozenset'), {'multiset': 'collection.Counter'}]
    },
    'Sequence': {
        'Basic': ['list', 'tuple', 'iterator']
    },
    'Algorithm': {
        'Priority': ['heapq', 'queue.PriorityQueue'],
        'Queue': ['queue.Queue', 'multiprocessing.Queue'],
        'Stack': ['collection.deque', 'queue.LifeQueue']
        },
    'text_sequence': ['str', 'byte', 'bytearray']
}
Calcul
la source
3

Le package ParallelRegression fournit une classe d'ensemble ordonnée setList () qui est plus complète en termes de méthode que les options basées sur la recette ActiveState. Il prend en charge toutes les méthodes disponibles pour les listes et la plupart sinon toutes les méthodes disponibles pour les ensembles.

RichardB
la source
2

Comme d'autres réponses le mentionnent, comme pour python 3.7+, le dict est ordonné par définition. Au lieu de sous-classer, OrderedDictnous pouvons sous abc.collections.MutableSet- classer ou typing.MutableSetutiliser les clés du dict pour stocker nos valeurs.

class OrderedSet(typing.MutableSet[T]):
    """A set that preserves insertion order by internally using a dict."""

    def __init__(self, iterable: t.Iterator[T]):
        self._d = dict.fromkeys(iterable)

    def add(self, x: T) -> None:
        self._d[x] = None

    def discard(self, x: T) -> None:
        self._d.pop(x)

    def __contains__(self, x: object) -> bool:
        return self._d.__contains__(x)

    def __len__(self) -> int:
        return self._d.__len__()

    def __iter__(self) -> t.Iterator[T]:
        return self._d.__iter__()

Alors juste:

x = OrderedSet([1, 2, -1, "bar"])
x.add(0)
assert list(x) == [1, 2, -1, "bar", 0]

J'ai mis ce code dans une petite bibliothèque , donc tout le monde peut le faire pip install.

bustawin
la source
-4

À de nombreuses fins, un simple appel trié suffit. 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 comptez utiliser ceci à plusieurs reprises, il y aura des frais généraux encourus en appelant la fonction triée afin que vous souhaitiez peut-être enregistrer la liste résultante, tant que vous avez terminé de modifier l'ensemble. Si vous devez conserver 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.

hwrd
la source
43
Le but de OrderedSet est de pouvoir obtenir les articles dans l'ordre où ils ont été ajoutés à l'ensemble. Votre exemple pourrait peut-être s'appeler SortedSet ...
Maintenance périodique
-4

J'ai donc également eu une petite liste où j'avais clairement la possibilité d'introduire des valeurs non uniques.

J'ai cherché l'existence d'une liste unique, mais j'ai réalisé que tester l'existence de l'élément avant de l'ajouter fonctionne très bien.

if(not new_element in my_list):
    my_list.append(new_element)

Je ne sais pas s'il y a des mises en garde à cette approche simple, mais cela résout mon problème.

Loïc N.
la source
Le principal problème avec cette approche est que l'ajout de pistes dans O (n). Cela signifie qu'il ralentit avec de grandes listes. Les ensembles intégrés de Python sont très efficaces pour accélérer l'ajout d'éléments. Mais pour les cas d'utilisation simples, cela fonctionne certainement!
Draconis