Hola, hallamos la respuesta a tu interrogante, desplázate y la obtendrás un poco más abajo.
Solución:
Como ha notado correctamente, el CPython implementación de list.clear Está encendido). El código itera sobre los elementos para disminuir el recuento de referencias de cada uno, sin forma de evitarlo. No hay duda de que se trata de una operación O (n) y, dada una lista lo suficientemente grande, se puede medir el tiempo invertido en clear() en función del tamaño de la lista:
import time
for size in 1_000_000, 10_000_000, 100_000_000, 1_000_000_000:
l = [None] * size
t0 = time.time()
l.clear()
t1 = time.time()
print(size, t1 - t0)
La salida muestra una complejidad lineal; en mi sistema con Python 3.7 imprime lo siguiente:
1000000 0.0023756027221679688
10000000 0.02452826499938965
100000000 0.23625731468200684
1000000000 2.31496524810791
El tiempo por elemento es, por supuesto, pequeño porque el ciclo está codificado en C y cada iteración hace muy poco trabajo. Pero, como muestra la medición anterior, incluso un pequeño factor por elemento eventualmente se suma. La constante pequeña por elemento no es la razón para ignorar el costo de una operación, o lo mismo se aplicaría al ciclo que desplaza los elementos de la lista en l.insert(0, ...), que también es muy eficiente y, sin embargo, pocos afirmarían que la inserción al principio es O (1). (Y clear potencialmente lo hace más funciona porque un decref ejecutará una cadena arbitraria de destructores para un objeto cuyo recuento de referencias en realidad llega a cero).
A nivel filosófico, se podría argumentar que los costos de la gestión de la memoria deben ignorarse al evaluar la complejidad porque de lo contrario sería imposible analizar nada con certeza, ya que cualquier operación podría desencadenar un GC. Este argumento tiene mérito; GC se produce de forma ocasional e impredecible, y su costo se puede considerar amortizado en todas las asignaciones. En una línea similar, el análisis de la complejidad tiende a ignorar la complejidad de malloc porque los parámetros de los que depende (como la fragmentación de la memoria) normalmente no están directamente relacionados con el tamaño de la asignación o incluso con el número de bloques ya asignados. Sin embargo, en caso de list.clear solo hay un bloque asignado, no se activa ningún GC y el código sigue visitando todos y cada uno de los elementos de la lista. Incluso con el supuesto de O (1) malloc y O (1) GC amortizado, list.cleartodavía toma el tiempo proporcional al número de elementos de la lista.
El artículo vinculado desde la pregunta trata sobre Python, el lenguaje y no menciona una implementación en particular. Es probable que las implementaciones de Python que no utilizan el recuento de referencias, como Jython o PyPy, tengan true O (1) list.clear, y para ellos la afirmación del artículo sería totalmente correcta. Entonces, al explicar la lista de Python en un nivel conceptual, no es incorrecto decir que borrar la lista es O (1); después de todo, todas las referencias de objetos están en un contiguo array, y lo liberas solo una vez. Este es el punto que probablemente debería hacer su publicación de blog, y eso es lo que el artículo vinculado está tratando de decir. Tener en cuenta el costo del recuento de referencias demasiado pronto podría confundir a sus lectores y darles ideas completamente erróneas sobre las listas de Python (por ejemplo, podrían imaginar que están implementadas como listas enlazadas).
Finalmente, en algún momento uno debe aceptar que la estrategia de administración de memoria cambia la complejidad de algunos operaciones. Por ejemplo, destruir una lista enlazada en C ++ es O (n) desde la perspectiva del llamador; descartarlo en Java o Go sería O (1). Y no en el sentido trivial de un lenguaje de recolección de basura es simplemente posponer el mismo trabajo para más adelante; es muy posible que un recolector en movimiento solo atraviese objetos alcanzables y, de hecho, nunca visite los elementos de la lista vinculada descartada. El recuento de referencias hace que el descarte de contenedores grandes sea algorítmicamente similar a la recolección manual, y GC puede eliminar eso. Mientras que CPython’s list.clear tiene que tocar cada elemento para evitar una fuga de memoria, es muy posible que el recolector de basura de PyPy Nunca necesita hacer algo por el estilo, y por lo tanto tiene un true O (1) list.clear.
Es O (1) descuidar la gestión de la memoria. No es correcto decir que es O (N) la contabilidad de la gestión de la memoria, porque la contabilidad de la gestión de la memoria es complicada.
La mayoría de las veces, para la mayoría de los propósitos, tratamos los costos de la administración de la memoria por separado de los costos de las operaciones que la activaron. De lo contrario, casi todo lo que podría hacer se convierte en O (quién sabe), porque casi cualquier operación podría desencadenar un pase de recolección de basura o un destructor costoso o algo así. Demonios, incluso en lenguajes como C con gestión de memoria “manual”, no hay garantía de que ningún malloc o free la llamada será rápida.
Se puede argumentar que las operaciones de recuento deben tratarse de manera diferente. Después de todo, list.clear realiza explícitamente una serie de Py_XDECREF operaciones iguales a la longitud de la lista, e incluso si no se desasignan o finalizan objetos como resultado, el recuento en sí mismo llevará necesariamente un tiempo proporcional a la longitud de la lista.
Si cuentas el Py_XDECREF operaciones list.clear realiza explícitamente, pero ignora cualquier destructor u otro código que pueda ser desencadenado por las operaciones de recuento, y asume PyMem_FREE es tiempo constante, entonces list.clear es O (N), donde N es la longitud original de la lista. Si descarta toda la sobrecarga de administración de memoria, incluida la Py_XDECREF operaciones list.clear es O (1). Si cuenta todos los costos de administración de memoria, entonces el tiempo de ejecución de list.clear no puede estar delimitado asintóticamente por ninguna función de la longitud de la lista.
Te invitamos a patrocinar nuestra función ejecutando un comentario o valorándolo te damos las gracias.