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

Question

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

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

Edit:

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

Answer 1

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

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

Answer 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, потому что он использует список. Если вы вставите один и тот же элемент более одного раза, у вас будут дубликаты в списке.

Answer 3

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

Мне удалось найти это, хотя:

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

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

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

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

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

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

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

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

Answer 4

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

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

pip install sortedcontainers

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

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

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

Answer 5

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

s = set(a_list)

for k in sorted(s):
    print k

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

Answer 6

Используйте blist.sortedlist из блистерной упаковки .

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

Полученный объект можно использовать так же, как список питонов.

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

Answer 7

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

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