¿Dónde puedo encontrar la complejidad temporal y espacial de los tipos de secuencia integrados en Python?

Question

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

Answer 1

Revisar la TiempoComplejidad página en la wiki de py dot org.Cubre conjuntos/dictados/listas/etc al menos en lo que respecta a la complejidad del tiempo.

Answer 2

Raymond D.Hettinger lo hace una excelente charla (diapositivas) sobre las colecciones integradas de Python llamadas 'Contenedores principales de Python: bajo el capó'.La versión que vi se centraba principalmente en set y dict, pero list estaba cubierto también.

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

He aquí un resumen de mis notas sobre list:

• Almacena elementos como una serie de punteros.El subíndice cuesta O(1) tiempo.Adjuntar costos amortizados O(1) tiempo.Insertar cuesta O(n) tiempo.
• intenta evitar memcpy cuando crece mediante sobreasignación.Muchas listas pequeñas desperdiciarán mucho espacio, pero las listas grandes nunca desperdician más de un 12,5% aproximadamente en una sobreasignación.
• Algunas operaciones pre-tamaño.Los ejemplos dados fueron range(n), map(), list(), [None] * n, y rebanar.
• Al reducirse, la matriz es realloced sólo cuando está desperdiciando el 50% del espacio. pop es barato.

Answer 3

Si preguntas lo que creo que preguntas, puedes encontrarlos. Aquí...página 476 y siguientes.

Está escrito sobre técnicas de optimización para Python;Es principalmente una notación Big-O de eficiencias de tiempo y no mucha memoria.