¿El equivalente TreeSet de Java en Python?

Question

Recientemente me encontré con un código Java que simplemente colocaba algunas cadenas en un TreeSet de Java, implementaba un comparador basado en la distancia, y luego hacía su camino alegremente hacia la puesta del sol para calcular un puntaje dado para resolver el problema.

Mis preguntas,

• ¿Existe una estructura de datos equivalentes disponibles para Python?

  • El conjunto de árboles de Java parece ser básicamente un diccionario ordenado que puede usar un comparador de algún tipo para lograr este orden.

• veo que hay una PEP for Py3K para una OrderedDict, pero estoy usando 2.6.x. Hay un montón de implementaciones de Dict ordenadas, ¿alguien en particular que pueda ser recomendado?

PS, sólo para añadir - me podía probablemente importar DictMixin o UserDict y poner en práctica mi diccionario propia ordenados/ordenado, y hacer que suceda a través de una función de comparación - pero que parece ser excesiva.

Gracias.

---

Actualizar. Gracias por las respuestas. Para elaborar un poco, digamos que tengo una función de comparación definida como los thats, (dado un valor En particular),

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 

estoy un poco inseguro sobre cómo iba a integrar este principio en el orden dado en el dict ordenado link given here...

Algo así como,

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

ideas sería bienvenido.

Answer 1

El Python 2.7 docs for collections.OrderedDict tiene un enlace a una OrderedDict recipe que se ejecuta en Python 2.4 o superior.

Editar: En cuanto a la clasificación: Use key= en lugar de cmp=. Tiende a llevar a faster code y, además, la palabra clave cmp= se ha eliminado en 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)] 

El código que envió para mycmp no dejar claro lo que quiere pasar como x1.A continuación, supongo que se supone que x1 es el valor en cada par clave-valor. Si es así, usted podría hacer algo como esto:

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

key=... se pasa a una función, lambda item: abs(item[1]-length). Para cada item en d.items(), la función lambda devuelve el número abs(item[1]-length). Este número actúa como proxy para el artículo en lo que respecta a la clasificación. Consulte this essay para obtener más información sobre cómo ordenar idiomas en Python.

PS. len es una función incorporada de Python. Por lo tanto, para no criticar ese len, he cambiado el nombre de la variable a length.

Answer 2

1. No creo que Python tenga un conjunto ordenado incorporado. ¿Qué tal algo así?

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

2.Java TreeSet es una implementación de la abstracción llamada SortedSet. tipos básicos serán ordenados en order.A naturales TreeSet ejemplo, realiza todas las comparaciones clave utilizando su compareTo (o comparar) method.So sus teclas personalizadas deben poner en práctica adecuada compareTo

Answer 3

Si lo que desea es un conjunto que siempre repite en orden clasificado, esto podría conseguir que la mayor parte del camino:

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

que había necesidad de ver algunos datos de ejemplo, pero si' Solo estamos tratando de hacer una ordenación ponderada, y luego la pitón integrada ordenada() puede hacerlo de dos maneras.

Con tuplas bien ordenadas y una función clave():

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 clase con un operador __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 

Ambos devuelven el mismo resultado:

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

Answer 5

recientemente he implementado TreeSet para Python usando el módulo de la bisectriz.

https://github.com/fukatani/TreeSet

Su uso es similar a TreeSet de 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