python sortedcontainers
v2.1.0 JOSS
Sorted Containers는 순수 Python으로 작성되었으며 C 확장만큼 빠른 Apache2 라이선스 정렬 컬렉션 라이브러리입니다.
Python의 표준 라이브러리는 정렬된 컬렉션 유형이 필요할 때까지 훌륭합니다. 많은 사람들이 이것 없이도 많은 것을 얻을 수 있다고 증명할 것입니다. 그러나 정렬된 목록, 정렬된 딕셔너리 또는 정렬된 세트가 실제로 필요한 순간에는 12가지 다른 구현에 직면하게 되며 대부분은 훌륭한 문서화 및 벤치마킹 없이 C 확장을 사용합니다.
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위에 표시된 모든 작업은 선형 시간보다 빠르게 실행됩니다. 위의 데모를 실행하는 데에도 거의 1GB의 메모리가 필요합니다. 정렬된 목록에 천만을 곱하면 "a"부터 "e"까지 각각에 대한 참조가 천만 개 저장됩니다. 각 참조에는 정렬된 컨테이너에 8바이트가 필요합니다. 각 개체에 대한 포인터 비용이 들기 때문에 이기기가 매우 어렵습니다. 또한 모든 노드가 하위 노드에 대한 두 개의 포인터를 저장해야 하는 일반적인 이진 트리 구현(예: Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap 등)보다 오버헤드가 66% 적습니다.
Sorted Containers는 Python 정렬 컬렉션의 모든 작업을 수행하므로 Python 배포 및 사용이 쉬워집니다. C 컴파일러를 설치하거나 사용자 정의 확장을 사전 구축 및 배포할 필요가 없습니다. 성능은 기능이며 테스트는 단위 테스트와 몇 시간의 스트레스를 포함하여 100% 적용됩니다.
Alex Martelli , Python 소프트웨어 재단 펠로우
"좋은 것 같아요! ... O(N) 삽입 비용을 피하기 위해 정렬된 컨테이너를 더 작은 "조각"으로 분할하는 간단하고 효과적인 구현 아이디어가 마음에 듭니다."
Jeff Knupp , Writing Idiomatic Python 및 Python Trainer의 저자
"마지막 부분인 "C 확장만큼 빠르다"는 것은 믿기 어려웠습니다. 이것이 사실인지 확인하려면 일종의 성능 비교가 필요합니다. 저자는 이를 문서에 포함시켰습니다. 그렇습니다.
Kevin Samuel , Python 및 Django 트레이너
코드 품질(가독성이 뛰어나고 코드보다 주석이 더 많습니다. 와우)뿐만 아니라 문서화, 벤치마킹, 구현 설명 등 코드가 아닌 작업에 쏟는 실제 작업량에도 놀랐습니다. git 로그도 깨끗하고 Python 2와 3에서는 단위 테스트가 즉시 실행됩니다.
Mark Summerfield , Python Sorted Collections에 대한 짧은 간청
Python의 "배터리 포함" 표준 라이브러리에 배터리가 없는 것 같습니다. 그리고 "우리는 이전에 그런 일을 해본 적이 없다"는 주장은 쇠약해졌습니다. 이제 Python이 정렬된 클래스를 포함하여 모든 범위의 컬렉션 클래스를 즉시 제공할 때입니다.
Sorted Containers는 다음과 같은 인기 있는 오픈 소스 프로젝트에서 사용됩니다: Quantopian의 알고리즘 거래 라이브러리인 Zipline; UC Santa Barbara의 바이너리 분석 플랫폼인 Angr; 비동기 I/O 라이브러리인 Trio; Continuum Analytics가 지원하는 분산 계산 라이브러리인 Dask Distributed가 있습니다.
pip를 사용하면 정렬된 컨테이너를 간단하게 설치할 수 있습니다.
$ pip install sortedcontainers
Python에 내장된 도움말 기능을 사용하여 인터프리터의 문서에 액세스할 수 있습니다. 도움말은 정렬된 컨테이너의 모듈, 클래스 및 메서드에 대해 작동합니다.
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )정렬된 컨테이너에 대한 전체 문서는 http://www.grantjenks.com/docs/sortedcontainers/에서 확인할 수 있습니다.
사용자 가이드에서는 정렬된 컨테이너에 대한 소개와 광범위한 성능 비교 및 분석을 제공합니다.
커뮤니티 가이드는 지원, 구현 및 기록 세부 정보와 함께 정렬된 컨테이너 개발에 대한 정보를 제공합니다.
API 문서는 정렬된 컨테이너 패키지의 특정 기능, 클래스 및 모듈에 대한 정보를 제공합니다.
저작권 2014-2024 그랜트 젠크스
Apache 라이센스 버전 2.0("라이센스")에 따라 라이센스가 부여되었습니다. 라이센스를 준수하는 경우를 제외하고는 이 파일을 사용할 수 없습니다. 다음에서 라이센스 사본을 얻을 수 있습니다.
http://www.apache.org/licenses/LICENSE-2.0
해당 법률에서 요구하거나 서면으로 동의하지 않는 한, 라이선스에 따라 배포되는 소프트웨어는 명시적이든 묵시적이든 어떠한 종류의 보증이나 조건 없이 "있는 그대로" 배포됩니다. 라이선스에 따른 허가 및 제한 사항을 관리하는 특정 언어는 라이선스를 참조하세요.
