python - tutorial - the django project

¿Dónde puedo encontrar la complejidad de tiempo y espacio de los tipos de secuencia integrados 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

Si preguntas lo que creo que estás preguntando, puedes encontrarlos aquí ... 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 2

Consulte 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 3

Raymond D. Hettinger hace una excelente charla ( diapositivas ) sobre las colecciones integradas de Python llamadas ''Core Python Containers - Under the Hood''. La versión que vi se enfocó principalmente en set y dict , pero la list estaba cubierta.

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

Aquí hay un resumen de mis notas en la list :

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