Equivalente TreeSet Java in Python?

Question

Recentemente mi sono imbattuto in un codice Java che semplicemente ha messo alcune stringhe in un TreeSet Java, implementato un comparatore basato sulla distanza per esso, e poi ha fatto la sua strada verso il tramonto per calcolare un determinato punteggio per risolvere il problema dato.

mie domande,

• Esiste una struttura di dati equivalente disponibile per Python?

  • Il set di alberi Java sembra fondamentalmente un dizionario ordinato che può utilizzare un comparatore di qualche tipo per ottenere questo ordine.

• Vedo che c'è un PEP for Py3K per un OrderedDict, ma sto usando 2.6.x. Ci sono un sacco di implementazioni di dict ordinate là fuori - qualcuno in particolare che può essere raccomandato?

PS, Giusto per aggiungere - ho potuto probabilmente importare DictMixin o UserDict e realizzare il mio dizionario propria ordinato/ordinato, e farlo accadere attraverso una funzione di confronto - ma che sembra essere eccessivo.

Grazie.

---

Aggiornamento

. Grazie per le risposte. Per elaborare un po ', consente di dire ho una funzione di confronto i thats definita come, (dato un particolare valore 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 

Sono un po' incerto su come mi piacerebbe integrare questo in ordine data nel comando ordinato link given here...

Qualcosa di simile,

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

idee sarebbe il benvenuto.

Answer 1

Il Python 2.7 docs for collections.OrderedDict ha un collegamento a un OrderedDict recipe che gira su Python 2.4 o superiore.

Edit: Per quanto riguarda l'ordinamento: Usa key= piuttosto che cmp=. Tende a portare a faster code e inoltre, la parola chiave cmp= è stata eliminata in 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)] 

Il codice che avete inviato per mycmp non rende chiaro ciò che si desidera passato come x1.Di seguito, presumo che x1 sia il valore in ciascuna coppia chiave-valore. Se è così, si potrebbe fare qualcosa di simile:

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

key=... è passato una funzione, lambda item: abs(item[1]-length). Per ogni item in d.items(), la funzione lambda restituisce il numero abs(item[1]-length). Questo numero funge da proxy per l'articolo per quanto riguarda l'ordinamento. Vedere this essay per ulteriori informazioni sull'ordinamento degli idiomi in Python.

PS. len è una funzione incorporata di Python. Quindi, in modo da non clobberare quello len, ho cambiato il nome della variabile in length.

Answer 2

1. Non penso che Python abbia un set Sorted incorporato. Che ne dici di qualcosa del genere?

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

2.Java TreeSet è un'implementazione di astrazione chiamato SortedSet. Tipi di base verranno ordinati in order.A naturale TreeSet esempio esegue tutti i confronti chiave utilizzando il suo compareTo (o confrontare) method.So le chiavi personalizzate dovrebbero attuare una corretta compareTo

Answer 3

Se quello che vuoi è un set che sempre itera in ordinati-ordine, questo potrebbe ottenere la maggior parte del tragitto:

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

avrei bisogno di vedere alcuni dati di esempio, ma se si' Sto solo cercando di fare un ordinamento ponderato, quindi il built-in python sort() può farlo, in due modi.

Con tuple ben ordinate e una funzione chiave():

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 

o con una classe con un operatore di __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 

Entrambi restituiscono lo stesso risultato:

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

Answer 5

Recentemente ho implementato TreeSet per Python utilizzando bisettrice modulo.

https://github.com/fukatani/TreeSet

Il suo utilizzo è simile a TreeSet di 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