¿Dónde puedo encontrar la complejidad temporal y espacial de los tipos de secuencia integrados en Python?
-
09-06-2019 - |
Pregunta
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?
Solución
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.
Otros consejos
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
realloc
ed sólo cuando está desperdiciando el 50% del espacio.pop
es barato.
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.