Onde posso encontrar o tempo eo espaço complexidade dos tipos de seqüência embutidos em Python

votos
15

Eu fui incapaz de encontrar uma fonte para esta informação, curta de olhar através do código-fonte Python me para determinar como os objetos funcionam. Alguém sabe onde eu poderia encontrar esta online?

Publicado 05/09/2008 em 05:27
fonte usuário
Em outras línguas...                            


3 respostas

votos
17

Checkout da TimeComplexity página na py wiki dot org. Abrange set / dicts / listas / etc pelo menos tanto como a complexidade que o tempo passa.

Respondeu 05/09/2008 em 17:19
fonte usuário

votos
13

Raymond D. Hettinger faz uma excelente conversa ( diapositivos ) sobre Python embutido coleções chamadas 'Core Python Contentores - Under the Hood'. A versão que eu vi focado principalmente em sete dict, mas listestava coberto também.

Há também algumas fotos dos slides pertinentes de EuroPython em um blog .

Aqui está um resumo das minhas anotações sobre list:

  • Armazena itens como uma matriz de ponteiros. Subscrito custos de O (1) hora. Anexar custos amortizados O (1) hora. Insira custos O (n).
  • Tenta evitar memcpyao crescer pelo excesso de reparte. Muitas pequenas listas vai perder muito espaço, mas grandes listas não perder mais do que cerca de 12,5% a Superalocação.
  • Algumas operações de pré-size. Os exemplos dados foram range(n), map(), list(), [None] * n, e de corte.
  • Quando encolhendo, a matriz é realloced apenas quando ele é o desperdício de 50% do espaço. popé barato.
Respondeu 05/09/2008 em 12:04
fonte usuário

votos
2

Se o seu perguntando o que eu acho que a sua pergunta, você pode encontrá-los aqui ... página 476 e no.

Ele é escrito em torno de técnicas de otimização para Python; É principalmente Big-O notação de eficiência de tempo não muito memória.

Respondeu 05/09/2008 em 05:52
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more