Почему в стандартных библиотеках Python нет отсортированных контейнеров?

Question

Существует ли решение о разработке Python (PEP), которое запрещает добавление отсортированного контейнера в Python?

(OrderedDict не отсортированный контейнер, поскольку он упорядочен по порядку вставки.)

Answer 1

Также имеется модуль python sortedcontainers , который реализует отсортированные типы списков, dict и set.Он очень похож на blist, но реализован в pure-Python и в большинстве случаев быстрее .

>>> from sortedcontainers import SortedSet
>>> ss = SortedSet([3, 7, 2, 2])
>>> ss
SortedSet([2, 3, 7])

. Он также имеет функции, необычные для других пакетов:

>>> from sortedcontainers import SortedDict
>>> sd = SortedDict((num, num) for num in range(100000))
>>> sd.iloc[-5] # Lookup the fifth-to-last key.
99995

Отказ от ответственности: Я являюсь автором модуля sortedcontainers.

Answer 2

Это сознательное дизайнерское решение со стороны Гвидо (он даже несколько неохотно относился к добавлению модуля collections).Его цель - сохранить «один очевидный способ сделать это», когда дело доходит до выбора типов данных для приложений.

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

Учитывая, что list + sorting, list + heapq и list + bisect покрывают многие случаи использованиякоторый в противном случае полагался бы на изначально отсортированные структуры данных, и существуют пакеты, такие как blist, не существует огромного диска, чтобы добавить больше сложности в это пространство стандартной библиотеке.

В некоторых отношениях это похоже натот факт, что в стандартной библиотеке нет многомерного массива, вместо этого передается эта задача людям NumPy.

Answer 3

Существует также модуль blist , который содержит тип данных sortedset :

sortedset(iterable=(), key=None)

>>> from blist import sortedset
>>> my_set = sortedset([3,7,2,2])
sortedset([2, 3, 7]

Answer 4

Не совсем «отсортированный контейнер», но вас может заинтересовать модуль bisect стандартной библиотеки, который «обеспечивает поддержку сохранения списка в отсортированном порядке без необходимости сортировки списка после каждой вставки» .

Answer 5

В стандартной библиотеке есть heapq, она не точно отсортирована, но вроде.Существует также пакет blist , но его нет в стандартной библиотеке.

Answer 6

Списки Python упорядочены. Если вы сортируете их, они остаются такими. В Python 2.7 был добавлен тип OrderedDict для поддержки явно упорядоченного словаря.

Python также имеет наборов (коллекция, в которой члены должны быть уникальными), но по определению они неупорядочены. Сортировка набора просто возвращает list.