Equivalent TreeSet de Java en Python?

Question

J'ai récemment rencontré du code Java qui mettait simplement des chaînes dans un TreeSet Java, implémentait un comparateur basé sur la distance, puis faisait son chemin au coucher du soleil pour calculer un score donné pour résoudre le problème donné.

Mes questions,

• Y at-il une structure de données équivalente disponibles pour Python? Le jeu d'arbres Java ressemble essentiellement à un dictionnaire ordonné qui peut utiliser un comparateur quelconque pour réaliser cet ordre. Je vois qu'il y a un PEP for Py3K pour un OrderedDict, mais j'utilise 2.6.x. Il y a un tas de mises en œuvre dictées ordonnées là-bas - quelqu'un en particulier qui peut être recommandé?

PS, Juste pour ajouter - je pourrait importer probablement DictMixin ou UserDict et mettent en place mon propre triés/commandé le dictionnaire, et pour y arriver grâce à une fonction de comparaison - mais qui semble être surpuissant.

Merci.

---

Mise à jour. Merci pour les réponses. Pour élaborer un peu, disons que j'ai une fonction de comparaison des thats définie comme, (donné une valeur particulière ln),

def mycmp(x1, y1, ln): 
    a = abs(x1-ln) 
    b = abs(y1-ln) 
    if a<b: 
    return -1 
    elif a>b: 
    return 1 
    else: 
    return 0 

Je suis un peu incertain au sujet de la façon dont je l'intégrer dans l'ordre donné dans la dict ordonnée link given here...

Quelque chose comme,

OrderedDict(sorted(d.items(), cmp=mycmp(len))) 

Idées serait la bienvenue.

Answer 1

Le Python 2.7 docs for collections.OrderedDict a un lien vers un OrderedDict recipe qui fonctionne sur Python 2.4 ou mieux. En ce qui concerne le tri: Utilisez key= plutôt que cmp=. Il tend à conduire à faster code et de plus, le mot-clé cmp= a été éliminé dans Python3.

d={5:6,7:8,100:101,1:2,3:4} 
print(d.items()) 
# [(1, 2), (3, 4), (100, 101), (5, 6), (7, 8)] 

Le code affiché pour mycmp ne dit pas clairement ce que vous voulez passé en x1.Ci-dessous, je suppose que x1 est supposé être la valeur dans chaque paire clé-valeur. Si oui, vous pourriez faire quelque chose comme ceci:

length=4 
print(sorted(d.items(),key=lambda item: abs(item[1]-length))) 
# [(3, 4), (1, 2), (5, 6), (7, 8), (100, 101)] 

key=... est passé d'une fonction, lambda item: abs(item[1]-length). Pour chaque item dans d.items(), la fonction lambda renvoie le numéro abs(item[1]-length). Ce numéro agit en tant que proxy pour l'article en ce qui concerne le tri. Voir this essay pour plus d'informations sur le tri des idiomes en Python.

PS. len est une fonction intégrée Python. Donc, afin de ne pas clabber que len, j'ai changé le nom de la variable à length.

Answer 2

1. Je ne pense pas que python a un ensemble intégré. Que diriez-vous de quelque chose comme ça?

letters = ['w', 'Z', 'Q', 'B', 'C', 'A'] 
    for l in sorted(set(letters)): 
    print l 

2.Java TreeSet est une implémentation de l'abstraction appelée SortedSet. Les types de base seront triés sur ordre.Un naturel TreeSet exemple effectue toutes les comparaisons clés en utilisant son compareTo (ou comparer) method.So vos clés personnalisés doivent mettre en œuvre une bonne compareTo

Answer 3

Si ce que vous voulez est un ensemble qui a toujours itère en ordre trié, cela pourrait vous obtenir la plupart du chemin:

def invalidate_sorted(f): 
    def wrapper(self, *args, **kwargs): 
     self._sort_cache = None 
     return f(self, *args, **kwargs) 
    return wrapper 

class SortedSet(set): 
    _sort_cache = None 

    _invalidate_sort_methods = """ 
     add clear difference_update discard intersection_update 
     symmetric_difference_update pop remove update 
     __iand__ __ior__ __isub__ __ixor__ 
     """.split() 

    def __iter__(self): 
     if not self._sort_cache: 
      self._sort_cache = sorted(set.__iter__(self)) 
     for item in self._sort_cache: 
      yield item 

    def __repr__(self): 
     return '%s(%r)' % (type(self).__name__, list(self)) 

    for methodname in _invalidate_sort_methods: 
     locals()[methodname] = invalidate_sorted(getattr(set, methodname)) 

Answer 4

Je dois voir quelques exemples de données, mais si vous juste en essayant de faire un tri pondéré, alors le python intégré trié() peut le faire, de deux façons.

Avec tuples bien ordonnés et une fonction clé():

def cost_per_page(book): 
    title, pagecount, cost = book 
    return float(cost)/pagecount 

booklist = [ 
     ("Grey's Anatomy", 3000, 200), 
     ('The Hobbit', 300, 7.25), 
     ('Moby Dick', 4000, 4.75), 
] 
for book in sorted(booklist, key=cost_per_page): 
    print book 

ou avec une classe avec un opérateur __cmp__.

class Book(object): 
    def __init__(self, title, pagecount, cost): 
     self.title = title 
     self.pagecount = pagecount 
     self.cost = cost 
    def pagecost(self): 
     return float(self.cost)/self.pagecount 
    def __cmp__(self, other): 
     'only comparable with other books' 
     return cmp(self.pagecost(), other.pagecost()) 
    def __str__(self): 
     return str((self.title, self.pagecount, self.cost)) 

booklist = [ 
     Book("Grey's Anatomy", 3000, 200), 
     Book('The Hobbit', 300, 7.25), 
     Book('Moby Dick', 4000, 4.75), 
] 
for book in sorted(booklist): 
    print book 

Ces deux renvoient la même sortie:

('Moby Dick', 4000, 4.75) 
('The Hobbit', 300, 7.25) 
("Grey's Anatomy", 3000, 200) 

Answer 5

J'ai récemment implémenté TreeSet pour Python en utilisant le module bissectrice.

https://github.com/fukatani/TreeSet

Son utilisation est similaire à TreeSet Java.

ex.

from treeset import TreeSet 
ts = TreeSet([3,7,2,7,1,3]) 
print(ts) 
>>> [1, 2, 3, 7] 

ts.add(4) 
print(ts) 
>>> [1, 2, 3, 4, 7] 

ts.remove(7) 
print(ts) 
>>> [1, 2, 3, 4] 

print(ts[2]) 
>>> 3