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

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

Мои вопросы,

Существует ли эквивалентная структура данных для Python?
- Дерево деревьев Java выглядит в основном как упорядоченный словарь, который может использовать какой-то компаратор для достижения этого упорядочения.
Я вижу там PEP для Py3K для OrderedDict, но я использую 2.6.x. Есть куча упорядоченных реализаций dict там - кто-нибудь, в частности, что можно рекомендовать?

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

Спасибо.

Update. Спасибо за ответы. Чтобы разработать немного, скажем, у меня есть функция сравнения, определенная как (с учетом определенного значения 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

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

Что-то вроде,

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

Идеи приветствуются.

Ответ 1

Python 2.7 docs для collections.OrderedDict имеет ссылку на Рецепт OrderedDict, который работает на Python 2.4 или лучше.

Изменить:. Что касается сортировки: используйте key=, а не cmp=. Это, как правило, приводит к более быстрому коду и, кроме того, ключевое слово 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). Это число действует как прокси-элемент для элемента при сортировке. См. это эссе для получения дополнительной информации о сортировке идиом в Python.

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

Ответ 2

Недавно я реализовал TreeSet для Python с помощью модуля bisect.

https://github.com/fukatani/TreeSet

Его использование похоже на Java Treeset.

ех.

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

Ответ 3

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

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

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

booklist = [
        ("Grey 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 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 Anatomy", 3000, 200)

Ответ 4

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

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

2.Java TreeSet - это реализация абстракции, называемой SortedSet. Базовые типы будут отсортированы по естественному порядку. Экземпляр TreeSet выполняет все сопоставления ключей с использованием метода compareTo (или сравнения). Таким образом, ваши пользовательские ключи должны реализовывать правильные compareTo

Ответ 5

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

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))