Ensemble Python avec la possibilité de faire apparaître un élément aléatoire
J'ai besoin d'un objet Python (2.7) qui fonctionne comme un ensemble (insertion rapide, suppression et vérification d'appartenance) mais qui a la capacité de renvoyer une valeur aléatoire. Les questions précédentes posées sur stackoverflow ont des réponses comme:
import random
random.sample(mySet, 1)
Mais c'est assez lent pour les grands ensembles (il s'exécute en temps O (N)).
Les autres solutions ne sont pas assez aléatoires (elles dépendent de la représentation interne des ensembles python, ce qui produit des résultats très non aléatoire):
for e in mySet:
break
# e is now an element from mySet
J'ai codé ma propre classe rudimentaire qui a une recherche en temps constant, une suppression et des valeurs aléatoires.
class randomSet:
def __init__(self):
self.dict = {}
self.list = []
def add(self, item):
if item not in self.dict:
self.dict[item] = len(self.list)
self.list.append(item)
def addIterable(self, item):
for a in item:
self.add(a)
def delete(self, item):
if item in self.dict:
index = self.dict[item]
if index == len(self.list)-1:
del self.dict[self.list[index]]
del self.list[index]
else:
self.list[index] = self.list.pop()
self.dict[self.list[index]] = index
del self.dict[item]
def getRandom(self):
if self.list:
return self.list[random.randomint(0,len(self.list)-1)]
def popRandom(self):
if self.list:
index = random.randint(0,len(self.list)-1)
if index == len(self.list)-1:
del self.dict[self.list[index]]
return self.list.pop()
returnValue = self.list[index]
self.list[index] = self.list.pop()
self.dict[self.list[index]] = index
del self.dict[returnValue]
return returnValue
Y a-t-il de meilleures implémentations pour cela, ou de grandes améliorations à apporter à ce code?
6 réponses
Je pense que la meilleure façon de le faire serait d'utiliser l'MutableSet classe de base abstraite dans collections. Hériter de MutableSet, puis définir add, discard, __len__, __iter__, et __contains__; également réécrire __init__ pour éventuellement accepter une séquence, tout comme les set constructeur n'. MutableSet fournit des définitions intégrées de toutes les autres méthodes set basées sur ces méthodes. De cette façon, vous obtenez l'interface set complète à moindre coût. (Et si vous faites cela, addIterable est défini pour vous, sous le nom de extend.)
discard dans la norme set interface semble être ce que vous avez appelé delete ici. Alors renommez delete en discard. De plus, au lieu d'avoir une méthode popRandom séparée, Vous pouvez simplement définir popRandom comme ceci:
def popRandom(self):
item = self.getRandom()
self.discard(item)
return item
De cette façon, vous n'avez pas à maintenir deux méthodes de suppression d'éléments distinctes.
Enfin, dans votre élément méthode de suppression (delete maintenant, discard selon la norme de l'interface), vous n'avez pas besoin d'une instruction if. Au lieu de tester si index == len(self.list) - 1, échangez simplement l'élément final de la liste avec l'élément à l'index de la liste à sauter, et apporter la modification nécessaire au dictionnaire d'indexation inverse. Puis pop le dernier élément de la liste et le supprimer du dictionnaire. Cela fonctionne si index == len(self.list) - 1 ou non:
def discard(self, item):
if item in self.dict:
index = self.dict[item]
self.list[index], self.list[-1] = self.list[-1], self.list[index]
self.dict[self.list[index]] = index
del self.list[-1] # or in one line:
del self.dict[item] # del self.dict[self.list.pop()]
Une approche que vous pourriez prendre est de dériver une nouvelle classe de {[0] } qui se salit avec des objets aléatoires d'un type dérivé de int.
Vous pouvez ensuite utiliser pop pour sélectionner un élément aléatoire, et s'il n'est pas du type salt, réinsérez-le et renvoyez-le, mais s'il est du type salt, insérez un nouvel objet salt généré aléatoirement (et pop pour sélectionner un nouvel objet).
Cela aura tendance à modifier l'ordre dans lequel les objets sont sélectionnés. En moyenne, le nombre de tentatives dépendra de la proportion d'éléments de salage, c'est-à-dire amortis O(K) performance.
Ne Pouvons-nous pas implémenter une nouvelle classe héritant de set avec quelques modifications (hackish) qui nous permettent de récupérer un élément aléatoire de la liste avec un temps de recherche O(1)? Btw, sur Python 2.x vous devez hériter de object, c'est à dire utiliser class randomSet(object). Aussi PEP8 est quelque chose à considérer pour vous :-)
Modifier: Pour avoir quelques idées sur ce que les solutions hackish pourraient être capables de faire, ce fil vaut la peine d'être lu: http://python.6.n6.nabble.com/Get-item-from-set-td1530758.html
Oui, j'implémenterais un" ensemble ordonné " de la même manière que vous l'avez fait - et j'utiliserais une liste comme structure de données interne.
Cependant, j'hériterais directement de " set " et garderais juste une trace des éléments ajoutés dans un liste interne ( comme vous l'avez fait) - et laissez les méthodes que je n'utilise pas seul.
Peut-être ajouter une méthode "sync" pour mettre à jour la liste interne chaque fois que l'ensemble est mis à jour par des opérations spécifiques à l'ensemble, comme les méthodes *_update.
Que si vous utilisez un "dict ordonné" ne couvre pas votre les cas d'utilisation. (Je viens de trouver qu'essayer de convertir des clés ordered_dict en un ensemble régulier n'est pas optmisé, donc si vous avez besoin d'opérations de définition sur vos données, ce n'est pas une option)
Si cela ne vous dérange pas de ne prendre en charge que des éléments comparables, vous pouvez utiliser blist.sortedset.
Voici une solution à partir de zéro, qui ajoute et apparaît en temps constant. J'ai également inclus quelques fonctions de jeu supplémentaires à des fins démonstratives.
from random import randint
class RandomSet(object):
"""
Implements a set in which elements can be
added and drawn uniformly and randomly in
constant time.
"""
def __init__(self, seq=None):
self.dict = {}
self.list = []
if seq is not None:
for x in seq:
self.add(x)
def add(self, x):
if x not in self.dict:
self.dict[x] = len(self.list)
self.list.append(x)
def pop(self, x=None):
if x is None:
i = randint(0,len(self.list)-1)
x = self.list[i]
else:
i = self.dict[x]
self.list[i] = self.list[-1]
self.dict[self.list[-1]] = i
self.list.pop()
self.dict.pop(x)
return x
def __contains__(self, x):
return x in self.dict
def __iter__(self):
return iter(self.list)
def __repr__(self):
return "{" + ", ".join(str(x) for x in self.list) + "}"
def __len__(self):
return len(self.list)