java - tiempo - primera carga celular nuevo

¿Cuánta pila usa una recursión(eliminando el nodo de la lista)? (1)

Actualización: Tenga en cuenta que tal como está esta pregunta no tiene mucho sentido, ya que la pila de llamadas crecerá independientemente del tipo T. La lista de llamadas depende únicamente de la cantidad de nodos en la lista que se procesa - los datos contenidos en esos nodos no tienen efecto en el tamaño de la pila de llamadas.

Digamos que tengo una implementación java recursiva de un método "remove-node-from-list" que se ve más o menos así:

// head public void remove(T data) { if (data == null) throw new IllegalArgumentException(); head = remove(head, data); } // other nodes of list private ListNode remove(ListNode current, T data) { if (current == null) return null; if (current.data.compareTo(data) == 0) return current.next; current.next = remove(current.next, data); return current; }

Supongamos además que el tipo T es int

Mi pregunta es: ¿Qué tan grande será la pila de llamadas (en el peor de los casos) en comparación con el tamaño de la lista que estoy procesando?

Lo que he pensado hasta ahora: por lo que he visto, Java 8 no optimiza las recursiones (¿verdad? Todo mi análisis asume que esto es cierto). Por lo tanto, tendremos un callstack creciendo linealmente con el tamaño de la lista.

Más precisamente: este método remove(ListNode current, T data) básicamente pondrá una referencia de nodo (32 bits en el arco de 32 bits) y un int (también de 32 bits) en la pila de llamadas para cada nodo en mi lista.

Ahora, dado que un nodo en la lista también consta de una referencia y un int un nodo tiene prácticamente el mismo tamaño que una de esas llamadas recursivas. En realidad, una de esas llamadas puede incluso usar más espacio (la dirección de retorno también debe ser empujada a la pila, ¿no? O ¿puede optimizarse de alguna manera?).

Entonces, si estoy en lo cierto, entonces la pila de llamadas básicamente será tan grande como la propia lista en el peor de los casos (cuando el elemento que se va a eliminar es el último en la lista). ¿Es este realmente el caso? Si estoy en lo correcto, esto implicaría un factor de 1 o incluso mayor con respecto a la pila de llamadas requerida para procesar la lista de int . Como consecuencia, al procesar listas grandes (en realidad ni siquiera tan grandes), digamos 1M, se obtendrá un stackoverflow si se ejecuta con las configuraciones predeterminadas para stacksize (0.5M)

Soy consciente del hecho de que para tipos de datos más grandes, el factor será menor, pero de todos modos, en lo que me mantendría firme es básicamente esto: si no hay optimización, entonces la pila de llamadas crecerá linealmente con el tamaño de la lista; por lo tanto, uno debería preferir el procedimiento iterativo sobre el recursivo.

En general, diría que la callstack crecerá linealmente de forma aproximada con un factor (size_of_all_arguments_in_call + size_of_return_address)/size_of_a_single_listelement que en el caso de una lista de int s es más o menos el mismo, ¿no? Por favor, no me malinterpreten con size_of_all_arguments : sé que solo pasamos el valor de las referencias a los objetos en esas llamadas y no a los objetos completos en sí mismos. Por lo tanto, para objetos grandes, el factor podría no ser tan dramático, pero aún diría que uno no debería aceptar ese espacio lineal innecesario. Sin embargo, para una lista de int s, el factor sería aprox. 1.

¿Este análisis es correcto o me falta algo?

Trasfondo : La persona con la que estaba discutiendo esto, estaba tratando de convencerme de que el callstack en Java no crecerá tan dramáticamente y señaló que me estaba perdiendo algo obvio (lamentablemente no me dijo qué y para mí realmente no es nada obvio). ) - ya que no sé qué es lo que me estoy perdiendo, estoy ansioso por aprender;)

Relacionado:

Lo principal que falta en las preguntas relacionadas para mí es cuánto espacio usará CallShack en realidad.

¿Cuánta pila usa una recursión (eliminando el nodo de la lista)?

Esa es una pregunta difícil de responder sin crear un perfil del código o tener detalles sobre una JVM en particular. Eso se debe a que la especificación de máquina virtual de Java (JVMS) deja muchos detalles al implementador.

Capítulo 2 de JVMS: los detalles de implementación que no son parte de la especificación de la Máquina virtual de Java restringirían innecesariamente la creatividad de los implementadores. Por ejemplo, el diseño de la memoria de las áreas de datos en tiempo de ejecución, el algoritmo de recolección de basura utilizado y cualquier optimización interna de las instrucciones de la máquina virtual de Java (por ejemplo, traducirlas en código de máquina) quedan a discreción del implementador.

Parte de esos detalles son las implementaciones de stack y Stack Frame. Y dado que parece que en realidad estás preguntando sobre la relación entre la pila creada por la eliminación recursiva y la lista que procesa el algoritmo, debemos considerar que el marco de la pila puede no ser tan grande en la pila como crees (o proponer en su pregunta).

JVMS (§2.5.2): Debido a que la pila de Java Virtual Machine nunca se manipula directamente, excepto para los marcos push y pop, los frames pueden asignarse al montón.

Eso significa que podría haber una sola referencia puesta en la pila para cada marco de pila. Si es así, eso haría que la relación entre la pila y la lista que procesa sea realmente insignificante para el ejemplo que proporcione. Veamos algunos números:

De acuerdo con Algorithms (Sedgewick, Wayne) :

Un Integer es 24 bytes
Overhead + variable de instancia ( int ) + relleno
= 16 + 4 + 4 = 24 bytes
Una clase de Node definida de forma recursiva no estática anidada en la List asociada es de 40 bytes Sobrecarga + referencias + sobrecarga adicional (referencia a la clase List )
= 16 + 8 + 8 + 8 = 40 bytes

Por lo tanto, podemos ver que hay 64 bytes por entrada en la lista. Por lo tanto, si hay una implementación en la que los marcos están asignados en un montón, la relación entre la pila y la lista que está procesando sería 8/64 = 1/8 bytes .

Es más difícil determinar el tamaño de la pila cuando los marcos de pila se asignan en la pila. De hecho, necesitamos más detalles de implementación para determinarlo.

JVMS (§2.6. Frames): los tamaños de la matriz de variables locales y la pila de operandos se determinan en tiempo de compilación y se suministran junto con el código para el método asociado con la trama (§4.7.3). Por lo tanto, el tamaño de la estructura de datos de trama depende solo de la implementación de la Máquina Virtual de Java, y la memoria para estas estructuras se puede asignar simultáneamente en la invocación del método.

Aun así, diría que, dado su ejemplo, no es probable que la pila crezca a una relación, o cerca de, 1: 1 en relación con una lista (hablando aquí del tamaño total en la memoria). Claro, podría presentar un problema específico que validaría su argumento, pero probablemente sería trivial y probablemente no con el ejemplo que proporcionó.