Сортированные контейнеры Python
v2.1.0 JOSS
Sorted Containers — это библиотека сортированных коллекций, лицензированная Apache2, написанная на чистом Python и быстрая, как C-расширения.
Стандартная библиотека Python хороша до тех пор, пока вам не понадобится тип отсортированных коллекций. Многие подтвердят, что без него можно добиться очень далеко, но в тот момент, когда вам действительно нужен отсортированный список, отсортированный словарь или отсортированный набор, вы сталкиваетесь с дюжиной различных реализаций, большинство из которых используют C-расширения без подробной документации и сравнительного анализа.
В Python мы можем добиться большего. И мы можем сделать это на чистом Python!
> >> from sortedcontainers import SortedList
> >> sl = SortedList ([ 'e' , 'a' , 'c' , 'd' , 'b' ])
> >> sl
SortedList ([ 'a' , 'b' , 'c' , 'd' , 'e' ])
> >> sl *= 10_000_000
> >> sl . count ( 'c' )
10000000
> >> sl [ - 3 :]
[ 'e' , 'e' , 'e' ]
> >> from sortedcontainers import SortedDict
> >> sd = SortedDict ({ 'c' : - 3 , 'a' : 1 , 'b' : 2 })
> >> sd
SortedDict ({ 'a' : 1 , 'b' : 2 , 'c' : - 3 })
> >> sd . popitem ( index = - 1 )
( 'c' , - 3 )
> >> from sortedcontainers import SortedSet
> >> ss = SortedSet ( 'abracadabra' )
> >> ss
SortedSet ([ 'a' , 'b' , 'c' , 'd' , 'r' ])
> >> ss . bisect_left ( 'c' )
2Все операции, показанные выше, выполняются быстрее линейного времени. Для запуска приведенной выше демонстрации также требуется почти гигабайт памяти. Когда отсортированный список умножается на десять миллионов, он сохраняет десять миллионов ссылок на каждую из букв от «a» до «e». Для каждой ссылки требуется восемь байтов в отсортированном контейнере. Это довольно сложно превзойти, поскольку это стоимость указателя на каждый объект. Это также на 66% меньше накладных расходов, чем типичная реализация двоичного дерева (например, Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap и т. д.), для которой каждый узел также должен хранить два указателя на дочерние узлы.
Сортированные контейнеры берут на себя всю работу по сортировке коллекций Python, что упрощает развертывание и использование Python. Нет необходимости устанавливать компилятор C или предварительно создавать и распространять пользовательские расширения. Производительность — это особенность, и тестирование на 100% охватывает модульные тесты и часы стресса.
Алекс Мартелли , член Python Software Foundation
«Хорошая штука! ... Мне нравится простая и эффективная идея разделения отсортированных контейнеров на более мелкие «фрагменты», чтобы избежать затрат на вставку O(N)».
Джефф Кнупп , автор книг «Написание идиоматического Python» и «Тренер Python»
«В эту последнюю часть, «быстро, как C-расширения», трудно было поверить. Мне нужно было какое-то сравнение производительности, чтобы убедиться, что это правда. Автор включил это в документацию. Так оно и есть».
Кевин Сэмюэл , тренер Python и Django
Я весьма поражен не только качеством кода (он невероятно читабелен и содержит больше комментариев, чем кода, вау), но и фактическим объемом работы, которую вы вкладываете в вещи, которые не являются кодом: документацию, тестирование производительности, объяснения реализации. Даже журнал git чист, а модульные тесты на Python 2 и 3 запускаются «из коробки».
Марк Саммерфилд , краткий призыв к сортированным коллекциям Python
В стандартной библиотеке Python «батарейки в комплекте», похоже, отсутствует батарея. И аргумент о том, что «у нас никогда этого не было», уже исчерпан. Настало время, когда Python предлагает полный набор классов коллекций «из коробки», включая отсортированные.
Sorted Containers используется в популярных проектах с открытым исходным кодом, таких как: Zipline, библиотека алгоритмической торговли от Quantopian; Angr, платформа бинарного анализа из Калифорнийского университета в Санта-Барбаре; Trio, библиотека асинхронного ввода-вывода; и Dask Distributed, библиотека распределенных вычислений, поддерживаемая Continuum Analytics.
Установить Sorted Containers с помощью pip очень просто:
$ pip install sortedcontainers
Вы можете получить доступ к документации в интерпретаторе с помощью встроенной функции справки Python. Справка работает с модулями, классами и методами в отсортированных контейнерах.
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )Полную документацию по сортированным контейнерам можно найти по адресу http://www.grantjunks.com/docs/sortedcontainers/.
Руководство пользователя содержит введение в Sorted Containers, а также подробное сравнение и анализ производительности.
Руководство сообщества предоставляет информацию о разработке Sorted Containers, а также подробную информацию о поддержке, реализации и истории.
Документация API предоставляет информацию о конкретных функциях, классах и модулях пакета Sorted Containers.
Авторские права: Грант Дженкс, 2014–2024 гг.
Лицензируется по лицензии Apache версии 2.0 («Лицензия»); вы не можете использовать этот файл, кроме как в соответствии с Лицензией. Вы можете получить копию Лицензии по адресу:
http://www.apache.org/licenses/LICENSE-2.0
Если это не требуется действующим законодательством или не согласовано в письменной форме, программное обеспечение, распространяемое по Лицензии, распространяется на условиях «КАК ЕСТЬ», БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ ИЛИ УСЛОВИЙ, явных или подразумеваемых. См. Лицензию для определения конкретного языка, регулирующего разрешения и ограничения в рамках Лицензии.
