Dónde puedo encontrar la complejidad de tiempo y espacio de los tipos de secuencia incorporados en Python

Question

No he podido encontrar una fuente para esta información, salvo buscar el código fuente de Python para determinar cómo funcionan los objetos. ¿Alguien sabe dónde podría encontrar esto en línea?

Answer 1

Pagar la página TimeComplexity en la wiki de py dot org. Cubre set/dicts/lists/etc al menos en cuanto a la complejidad del tiempo.

Answer 2

Si preguntas lo que creo que estás preguntando, puedes encontrarlos Here ... página 476 y sucesivamente.

Está escrito en torno a las técnicas de optimización para Python; Se trata principalmente de notación Big-O de eficiencias de tiempo, no mucha memoria.

Answer 3

Raymond D. Hettinger hace an excellent talk (slides) sobre las colecciones integradas de Python llamadas 'Contenedores Core Python - Under the Hood'. La versión que vi se centró principalmente en set y dict, pero también se cubrió list.

También hay algunas fotos de las diapositivas pertinentes de EuroPython en a blog.

Aquí se presenta un resumen de mis notas en list:

• almacena los elementos como una matriz de punteros. El subíndice cuesta O (1) vez. Anexar costos amortizados O (1) tiempo. Insertar costos O (n) tiempo.
• Intenta evitar memcpy al crecer por sobreasignación. Muchas listas pequeñas perderán mucho espacio, pero las grandes listas nunca desperdician más de aproximadamente el 12.5% ​​de sobreasignación.
• Algunas operaciones pre-tamaño. Los ejemplos dados fueron range(n), map(), list(), [None] * n, y rebanado.
• Al contraerse, la matriz es realloc ed solo cuando está desperdiciando el 50% del espacio. pop es barato.