Onde posso encontrar a complexidade de tempo e espaço dos tipos de sequência integrados em Python

Question

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?

Answer 1

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.

Answer 2

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 é realloced somente quando está desperdiçando 50% do espaço. pop é barato.

Answer 3

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.