TreeSet Java, эквивалентный в Python?
Я недавно столкнулся с некоторым кодом Java, которые просто помещают некоторые строки в Java TreeSet, реализовал основанный на расстоянии компаратор для него и затем превратил его веселый путь в закат для вычислений данного счета для решения данной проблемы.
Мои вопросы,
Существует ли эквивалентная структура данных, доступная для Python?
- Java treeset смотрит в основном, чтобы быть заказанным словарем, который может использовать какой-то компаратор для достижения этого упорядочивания.
Я вижу, что существует PEP для Py3K для OrderedDict, но я использую 2.6.x. Существует набор заказанных dict реализаций там - кто-либо в особенности, который может быть рекомендован?
PS, Только для добавления - я мог, вероятно, импортировать DictMixin или UserDict и реализовать мое собственное, сортировал/заказывал словарь, И заставьте его произойти через функцию компаратора - но это, кажется, излишество.
Спасибо.
Обновление. Спасибо за ответы. Для разработки немного, позволяет, говорят, что у меня есть сравнить функция, это определяется как, (учитывая конкретное значение ln),
def mycmp(x1, y1, ln):
a = abs(x1-ln)
b = abs(y1-ln)
if ab:
return 1
else:
return 0
Я немного не уверен в том, как я интегрировал бы это в упорядочивание, данное в заказанной ссылке dict, данной здесь...
Что-то как,
OrderedDict(sorted(d.items(), cmp=mycmp(len)))
Идеи приветствовались бы.
4 ответа
Документы Python 2.7 для коллекций.OrderedDict ] есть ссылка на рецепт OrderedDict , который работает на Python 2.4 или выше.
Изменить: В отношении сортировки: используйте ключ = вместо 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) .
Для каждого элемента в d.items () лямбда-функция возвращает число abs (длина элемента [1]) . Этот номер действует как прокси для элемента при сортировке. См. это эссе для получения дополнительной информации о сортировке идиом в Python.
PS. len - встроенная функция Python. Чтобы не сбивать len , я изменил имя переменной на length .
Мне нужно увидеть несколько примеров данных, но если вы просто пытаетесь выполнить взвешенное sort, то встроенный python sorted () может это сделать двумя способами.
С хорошо упорядоченными кортежами и функцией key ():
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)
Если вам нужен набор, который всегда повторяется в отсортированном порядке, это может помочь вам в большинстве случаев:
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))
1. Я не думаю, что в python есть встроенные сортированные наборы. Как насчет чего-то вроде этого?
letters = ['w', 'Z', 'Q', 'B', 'C', 'A']
for l in sorted(set(letters)):
print l
2.Java TreeSet является реализацией абстракции под названием SortedSet. Основные типы будут отсортированы в естественном порядке.Экземпляр TreeSet выполняет все сравнения ключей, используя свой метод compareTo (или compare).Поэтому ваши пользовательские ключи должны реализовать надлежащие compareTo