Onde posso encontrar a complexidade de tempo e espaço dos tipos de sequência integrados em Python
-
09-06-2019 - |
Pergunta
Não consegui encontrar uma fonte para essas informações, a não ser examinar pessoalmente o código-fonte do Python para determinar como os objetos funcionam.Alguém sabe onde posso encontrar isso online?
Solução
Confira a Complexidade do tempo página no wiki py dot org.Abrange set/dicts/lists/etc, pelo menos no que diz respeito à complexidade do tempo.
Outras dicas
Raimundo D.Hettinger faz uma excelente palestra (diapositivos) sobre as coleções integradas do Python chamadas 'Core Python Containers - Under the Hood'.A versão que vi focava principalmente em set
e dict
, mas list
também estava coberto.
Há também algumas fotos dos slides pertinentes do EuroPython em um blog.
Aqui está um resumo das minhas anotações sobre list
:
- Armazena itens como uma matriz de ponteiros.O subscrito custa O(1) tempo.Anexar custos amortizados O(1) tempo.Insira custos O(n) tempo.
- Tenta evitar
memcpy
ao crescer por alocação excessiva.Muitas listas pequenas desperdiçarão muito espaço, mas listas grandes nunca desperdiçam mais do que 12,5% na superalocação. - Algumas operações são pré-dimensionadas.Os exemplos dados foram
range(n)
,map()
,list()
,[None] * n
, e fatiar. - Ao encolher, a matriz é
realloc
ed somente quando está desperdiçando 50% do espaço.pop
é barato.
Se você está perguntando o que eu acho que está perguntando, você pode encontrá-los Aqui...página 476 em diante.
Está escrito em torno de técnicas de otimização para Python;É principalmente a notação Big-O de eficiência de tempo, sem muita memória.