Python эквивалентен java.util.SortedSet?

Кто-нибудь знает, имеет ли Python эквивалент интерфейса Java SortedSet?

Вот что я ищу: скажем, у меня есть объект типа foo, и я знаю, как сравнить два объекта типа foo, чтобы увидеть, является ли foo1 "больше" или "меньше" чем "foo2. Мне нужен способ хранения многих объектов типа foo в списке L, так что всякий раз, когда я пересекаю список L, я получаю объекты в порядке, в соответствии с методом сравнения, который я определяю.

Edit:

Я думаю, что я могу использовать словарь или список и sort() каждый раз, когда я его изменяю, но это лучший способ?

Ответ 1

Посмотрите BTrees. Похоже, вам нужен один из них. Насколько я понял, вам нужна структура, которая будет поддерживать относительно дешевую установку элемента в структуру хранилища и дешевую операцию сортировки (или даже отсутствие). BTrees предлагает это.

У меня есть опыт работы с ZODB.BTrees, и они масштабируются до тысяч и миллионов элементов.

Ответ 2

Вы можете использовать insort из модуля bisect для эффективного добавления новых элементов в уже отсортированный список:

from bisect import insort

items = [1,5,7,9]
insort(items, 3)
insort(items, 10)

print items # -> [1, 3, 5, 7, 9, 10]

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

Ответ 3

Если вы ищете реализацию эффективного типа контейнера для Python, реализованного с использованием чего-то вроде сбалансированного дерева поиска (например, дерево Red-Black), оно не входит в стандартную библиотеку.

Я смог найти это, хотя:

http://www.brpreiss.com/books/opus7/

Исходный код доступен здесь:

http://www.brpreiss.com/books/opus7/public/Opus7-1.0.tar.gz

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

Здесь PyAVL, который является модулем C, реализующим дерево AVL.

Кроме того, этот поток может быть вам полезен. Он содержит много предложений о том, как использовать модуль bisect для улучшения существующего словаря Python, чтобы делать то, что вы просите.

Конечно, использование insort() таким образом было бы довольно дорогостоящим для вставки и удаления, поэтому внимательно изучите его для своего приложения. Внедрение соответствующей структуры данных, вероятно, будет лучшим подходом.

В любом случае, чтобы понять, следует ли сортировать данные или сортировать их, когда вы перебираете их, вам нужно знать, собираетесь ли вы вставлять много или многократно перебирать. Сохранение сортировки структуры данных имеет смысл, если вы изменяете ее контент относительно редко, но много перебираете. И наоборот, если вы вставляете и удаляете элементы все время, но чередуете коллекцию относительно редко, сортировка коллекции ключей перед повторением будет быстрее. Правильного подхода нет.

Ответ 4

Если вам нужны только ключи и нет связанного значения, Python предлагает наборы:

s = set(a_list)

for k in sorted(s):
    print k

Однако вы будете сортировать набор каждый раз, когда вы это делаете. Если это слишком много, вы можете посмотреть HeapQueues. Они могут быть не такими элегантными и "Pythonic", но, возможно, они соответствуют вашим потребностям.

Ответ 5

Используйте blist.sortedlist из blist package.

from blist import sortedlist

z = sortedlist([2, 3, 5, 7, 11])
z.add(6)
z.add(3)
z.add(10)

print z

Это выведет:

sortedlist([2, 3, 3, 5, 6, 7, 10, 11])

Результирующий объект можно использовать так же, как и список python.

>>> len(z)
8
>>> [2 * x for x in z]
[4, 6, 6, 10, 12, 14, 20, 22]

Ответ 6

Подобно blist.sortedlist, модуль sortedcontainers предоставляет отсортированный список, отсортированный набор и отсортированный тип данных dict. Он использует модифицированное B-дерево в базовой реализации и в большинстве случаев быстрее, чем blist.

Модуль sortedcontainers является чистым Python, поэтому установка проста:

pip install sortedcontainers

Тогда, например:

from sortedcontainers import SortedList, SortedDict, SortedSet
help(SortedList)

Модуль отсортированных контейнеров имеет 100% -ное покрытие и часы стресса. Там представлено довольно полное сравнение производительности, в котором перечислены большинство параметров, которые вы рассмотрели бы для этого.

Ответ 7

Есть ли у вас возможность использовать Jython? Я просто упоминаю об этом, потому что использование TreeMap, TreeSet и т.д. Тривиально. Также, если вы исходите из фона Java и хотите отправиться в питоновское направление, Jython отлично подходит для облегчения перехода. Хотя я понимаю, что использование TreeSet в этом случае не будет частью такого "перехода".

Для суперпользователей Jython у меня есть вопрос: пакет blist нельзя импортировать, поскольку он использует файл C, который необходимо импортировать. Но есть ли преимущества использования blist вместо TreeSet? Можем ли мы в целом предположить, что JVM использует алгоритмы, которые по существу так же хороши, как и свойства CPython?