java - nodo - ¿Cómo escribir el método clear() en la estructura de datos de la lista?

listas enlazadas en java codigo fuente

Question

Recientemente, he leído algunos códigos fuente de marcos y noté que escribieron el método clear () de una estructura de datos similar a una lista como esta. Eliminar los elementos uno por uno.

while (_arr.length > 0 )
{

    remove(_arr[0]);

}       

(Tal vez lo de arriba parece un poco confuso, pero es porque el tipo de matriz nativa en este idioma en sí era una matriz dinámica) o

 for (int i = 0; i < size; i++)
  { elementData[i] = null;}
 size = 0;

Pero recuerdo que escribí un código como este. La lista decoró el tipo de matriz nativa y escribí el método clear () de esta manera.

 _arr=new Array();
 _size=0;

instanciar un nuevo tipo de matriz nativa directamente.

y este código está escrito en el idioma que tiene la recolección de basura. así que creo que todos los elementos finalmente se recopilarán, entonces, ¿por qué hay un bucle? ¿Es un nuevo será rápido?

Answer 1

¡De acuerdo con la respuesta de @Eran al crear una nueva matriz o reutilizar la existente!

Quiero agregar una información más aquí.

El código fuente para clear () es el siguiente:

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

El código fuente para removeAll () (definido en AbstractCollection):

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> e = iterator();
    while (e.hasNext()) {
        if (c.contains(e.next())) {
            e.remove();
            modified = true;
        }
    }
    return modified;
}

clear () es, por supuesto, más rápido, ya que no tiene que ocuparse de todas esas llamadas adicionales. Por lo tanto, es mejor configurar el elemento como nulo en lugar de eliminarlo.

Answer 2

Debería ser un comentario, pero no cabrá como tal, supongo.

También está el hecho de que besides asignar una matriz puede ser demasiado costoso y borrar la matriz anterior sería más barato, también existe el hecho de que asignar una matriz en forma de new byte[100] o lo que sea tiene que hacer también la puesta a cero de los contenidos , que también puede ser costoso

Como tal, en java-9 String concatenación de String usa UNSAFE.allocateUninitializedArray que dice específicamente UNSAFE.allocateUninitializedArray Allocates an array of a given type, but does not do zeroing. la UNSAFE.allocateUninitializedArray Allocates an array of a given type, but does not do zeroing. y por supuesto también agrega:

Este método solo debe utilizarse en los casos muy raros en los que un código de alto rendimiento sobrescribe la matriz de destino por completo, y los compiladores no pueden ayudar a la eliminación de la reducción a cero. En una abrumadora mayoría de los casos, se debe usar una asignación Java normal.

Y así es como se ve el método real:

    @ForceInline
    private static byte[] newArray(int length, byte coder) {
        return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, length << coder);
    }

Esto es solo para demostrar que hay casos en los que de hecho es demasiado caro crear arreglos y es más barato no hacerlo. Especialmente dado que las matrices pueden requerir asignación de memoria contigua, pero esto no es obligatorio por la especificación.

Answer 3

En algunos contextos, es más eficiente borrar y reutilizar la matriz de respaldo. (Obviamente, necesitas un campo de size y debes establecerlo en cero cuando borres la lista).

• El borrado reduce la basura generada cuando vacía la lista.
• Si crece la lista de forma incremental (es decir, sin una sugerencia de capacity ), la eliminación también reduce la basura generada por reasignaciones.

Pero la otra cara es que no siempre es una buena idea clear . Por ejemplo;

• Si llama a clear en una ArrayList , el tamaño de la matriz de respaldo permanece del mismo tamaño que cuando la lista estaba llena. Si la lista fue muy larga, la matriz puede ser muy grande. Y si nunca necesita que la lista vuelva a ser tan larga, la gran matriz puede desperdiciar mucho espacio.

• El GC tiene que verificar todas las celdas de la matriz de respaldo de ArrayList todos modos, independientemente del valor actual del campo de size . Y necesita copiar toda la matriz al espacio "a".

• Eso también significa que debe asignar null a las celdas "borradas" para evitar fugas de memoria.

• Puede haber problemas secundarios de rendimiento debido a factores generacionales y / o locales si coloca continuamente objetos "nuevos" en una gran matriz "antigua".

En resumen, si una lista con respaldo de matriz es probable que sobreviva a múltiples ciclos de GC, entonces la limpieza (es decir, el procedimiento de limpieza y reutilización de la matriz de respaldo) es una proposición dudosa.

Answer 4

En mi opinión, al crear una nueva matriz y crear instancias con ceros, debería ser más lenta. En este caso, la inicialización y la iteración se realizan para establecer el valor predeterminado. En el caso de usar una matriz existente, solo se hace el bit de iteración. Por lo tanto, usar una matriz existente e iterar sobre ella debería ser más rápido.

En nuestro proyecto, con frecuencia creamos objetos de matriz durante algún cálculo en un proceso por lotes de larga ejecución. Después de crear un conjunto desde el que puede obtener y regresar después de su uso, se muestra una mejora significativa.

Answer 5

Ninguno. Simplemente configure _arr en una matriz vacía. Ciertamente no debe llamar a remove() en un bucle, por razones de eficiencia, y establecer todos los elementos en nulo es semánticamente incorrecto.

Answer 6

Supongo que la motivación es reutilizar la matriz de respaldo existente en lugar de asignar una nueva. Esto es importante especialmente cuando la matriz de respaldo es muy grande (lo que en algunos casos raros puede incluso significar que la nueva matriz no se puede asignar antes de que la anterior sea recogida de basura).

La asignación de una nueva matriz (y la recolección de la antigua) probablemente requiera más tiempo que iterar sobre la matriz existente y establecer las referencias de todos los elementos a null .

EDITAR: como se menciona en los comentarios, establecer las referencias a null en una List basada en una matriz no es suficiente. También debe indicar que la List está vacía. En java.util.ArrayList esto se hace estableciendo la propiedad de size en 0 .