contêineres classificados em python
v2.1.0 JOSS
Sorted Containers é uma biblioteca de coleções classificadas licenciada pelo Apache2, escrita em Python puro e rápida como extensões C.
A biblioteca padrão do Python é ótima até que você precise de um tipo de coleção classificada. Muitos atestarão que você pode ir muito longe sem um, mas no momento em que você realmente precisa de uma lista ordenada, um ditado ordenado ou um conjunto ordenado, você se depara com uma dúzia de implementações diferentes, a maioria usando extensões C sem grande documentação e benchmarking.
Em Python, podemos fazer melhor. E podemos fazer isso em Python puro!
> >> 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' )
2Todas as operações mostradas acima são executadas mais rapidamente que o tempo linear. A demonstração acima também ocupa quase um gigabyte de memória para ser executada. Quando a lista ordenada é multiplicada por dez milhões, ela armazena dez milhões de referências para cada uma, de "a" a "e". Cada referência requer oito bytes no contêiner classificado. Isso é muito difícil de superar, pois é o custo de um ponteiro para cada objeto. Também é 66% menos sobrecarga do que uma implementação típica de árvore binária (por exemplo, Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap, etc.) para a qual cada nó também deve armazenar dois ponteiros para nós filhos.
Sorted Containers elimina todo o trabalho das coleções classificadas do Python - facilitando a implantação e o uso do Python. Não há necessidade de instalar um compilador C ou pré-construir e distribuir extensões personalizadas. O desempenho é um recurso e os testes têm 100% de cobertura com testes unitários e horas de estresse.
Alex Martelli , membro da Python Software Foundation
"Boa coisa!... Gosto da ideia de implementação simples e eficaz de dividir os contêineres classificados em "fragmentos" menores para evitar os custos de inserção O(N)."
Jeff Knupp , autor de Writing Idiomatic Python e Python Trainer
"Essa última parte, 'rápida como extensões C', era difícil de acreditar. Eu precisaria de algum tipo de comparação de desempenho para me convencer de que isso é verdade. O autor inclui isso nos documentos. É."
Kevin Samuel , treinador de Python e Django
Estou bastante surpreso, não apenas pela qualidade do código (é incrivelmente legível e tem mais comentários do que código, uau), mas pela quantidade real de trabalho que você dedica a coisas que não são código: documentação, benchmarking, explicações de implementação. Até o log do git está limpo e os testes de unidade são executados imediatamente no Python 2 e 3.
Mark Summerfield , um breve apelo para Python Sorted Collections
A biblioteca padrão "baterias incluídas" do Python parece estar faltando uma bateria. E o argumento de que “nunca tivemos isso antes” se desgastou. Já é hora de o Python oferecer uma gama completa de classes de coleção prontas para uso, incluindo aquelas classificadas.
Sorted Containers é usado em projetos populares de código aberto, como: Zipline, uma biblioteca de negociação algorítmica da Quantopian; Angr, uma plataforma de análise binária da UC Santa Barbara; Trio, uma biblioteca de E/S assíncrona; e Dask Distributed, uma biblioteca de computação distribuída suportada pela Continuum Analytics.
Instalar contêineres classificados é simples com pip:
$ pip instalar contêineres classificados
Você pode acessar a documentação no interpretador com a função de ajuda integrada do Python. A ajuda funciona em módulos, classes e métodos em Sorted Containers.
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )A documentação completa para Sorted Containers está disponível em http://www.grantjenks.com/docs/sortedcontainers/
O guia do usuário fornece uma introdução aos contêineres classificados e extensas comparações e análises de desempenho.
O guia da comunidade fornece informações sobre o desenvolvimento de Sorted Containers, juntamente com detalhes de suporte, implementação e histórico.
A documentação da API fornece informações sobre funções, classes e módulos específicos no pacote Sorted Containers.
Direitos autorais 2014-2024 Grant Jenks
Licenciado sob a Licença Apache, Versão 2.0 (a "Licença"); você não pode usar este arquivo, exceto em conformidade com a Licença. Você pode obter uma cópia da Licença em
http://www.apache.org/licenses/LICENSE-2.0
A menos que exigido pela lei aplicável ou acordado por escrito, o software distribuído sob a Licença é distribuído "COMO ESTÁ", SEM GARANTIAS OU CONDIÇÕES DE QUALQUER TIPO, expressas ou implícitas. Consulte a Licença para saber o idioma específico que rege as permissões e limitações da Licença.
