эквивалент TreeSet Java в Python?

Question

Недавно я натолкнулся на некоторый Java-код, который просто поместил некоторые строки в Java TreeSet, реализовал на нем компаратор расстояния, а затем сделал свой веселый путь в закат, чтобы вычислить данный балл, чтобы решить данную проблему.

Мои вопросы,

• существует эквивалентная структура данных для Python?

  • Java treeet выглядит в основном как упорядоченный словарь, который может использовать какой-либо компаратор для достижения этого упорядочения.

• У меня есть PEP for Py3K для OrderedDict, но я использую 2.6.x. Есть куча упорядоченных реализаций диктовки - кто-нибудь, в частности, может быть рекомендован?

PS, просто добавить - я мог вероятно импортировать DictMixin или UserDict и реализовать свой собственный отсортированный/упорядоченный словарь, и сделать это с помощью функции сравнения - но это, кажется излишним.

Спасибо.

---

Обновление. Спасибо за ответы. Чтобы разработать немного, позволяю сказать, что у меня есть функция сравнения Thats, определенная как, (данная конкретное значение п),

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 

Я немного не уверен о том, как я бы интегрировать это в упорядочение данного в заказе dict link given here...

Что-то подобное,

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

Идеи будут приветствоваться.

Answer 1

Питона 2,7 docs for collections.OrderedDict имеет ссылку на OrderedDict recipe, который работает на Python 2.4 или лучше.

Редактировать: Относительно сортировки: Используйте key=, а не cmp=. Он имеет тенденцию приводить к faster code и, кроме того, ключевое слово cmp= было устранено в 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)] 

код вы вывесили на mycmp не дают понять, что вы хотите, как прошло x1.Ниже я полагаю, что x1 должно быть значением в каждой паре ключей. Если да, то вы могли бы сделать что-то вроде этого:

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

key=... передается функции, lambda item: abs(item[1]-length). Для каждого item в d.items() функция лямбда возвращает номер abs(item[1]-length). Это число действует как прокси-элемент для элемента при сортировке. См. this essay для получения дополнительной информации о сортировке идиом в Python.

PS. len - встроенная функция Python. Итак, чтобы не сбивать len, я изменил имя переменной на length.

Answer 2

1. Я не думаю, что у python есть встроенные сортированные наборы. Как насчет чего-то подобного?

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

2.Java TreeSet является реализация абстракции под названием SortedSet. Основные типы будут отсортированы по естественному order.A TreeSet экземпляра выполняет все ключевые сравнения, используя его СотрагеТо (или сравнить) method.So пользовательских ключи должны осуществлять надлежащий compareTo

Answer 3

Если то, что вы хотите это набор, который всегда перебирает в отсортированном порядке, это мог бы получить большую часть пути туда:

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

я должен были бы увидеть некоторые примеры данных, но если вы» re просто пытается сделать взвешенную сортировку, тогда встроенный python sorted() может сделать это двумя способами.

С хорошо упорядоченных кортежей и функциональной клавиши():

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 

или с классом с __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 

Оба они возвращают один и тот же вывод:

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

Answer 5

Я недавно реализованный TreeSet для Python с помощью модуля разрез`ать.

https://github.com/fukatani/TreeSet

Его использование аналогично 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