Artículo Java efectivo 17: ¿Cómo se puede eliminar el eliminar eliminarRange() mejorar el rendimiento?

list data-structures

Question

En el libro Effective Java de Joshua Bloch, hay una discusión sobre cómo una clase puede proporcionar "métodos protegidos elegidos juiciosamente" como gancho en su funcionamiento interno.
El autor luego cita la documentación en AbstractList.removeRange() :

Este método es llamado por la operación clear en esta lista y sus sublistas. Anular este método para aprovechar las funciones internas de la implementación de la lista puede mejorar sustancialmente el rendimiento de la operación clear en esta lista y sus sublistas.

Mi pregunta es, ¿cómo puede anular este método mejorar el rendimiento (más que simplemente no anularlo)? ¿Alguien puede dar un ejemplo de esto?

Answer 1

Como se especifica en los javadocs del método:

Esta implementación obtiene un iterador de lista colocado antes fromIndex, y llama repetidamente a ListIterator.next seguido de ListIterator.remove hasta que se haya eliminado todo el rango.

Dado que esta clase abstracta no conoce las partes internas de sus subclases, se basa en este algoritmo genérico que se ejecutará en un tiempo proporcional al número de elementos que se eliminarán.

Si, por ejemplo, implementó una subclase que almacenó elementos como una lista vinculada. Entonces podría aprovechar este hecho y anular este método para usar un algoritmo específico de la lista enlazada (mover el puntero a fromIndex para apuntar a toIndex ) que se ejecuta en tiempo constante. Por lo tanto, ha mejorado el rendimiento porque aprovechó las funciones internas.

Answer 2

Simplemente anulando este método, puede utilizar este algoritmo genérico de acuerdo con sus necesidades como sus problemas de indexación. Como es un método protegido en AbstractList y también en ArrayList y su implementación, funciona como llamadas iterativas para eliminar () que necesitan cada cambio de tiempo de todos los elementos disponibles en el lado derecho del elemento eliminado por un índice. Obviamente no es efectivo, por lo que puede hacer que funcione mejor.

Answer 3

Tomemos un ejemplo concreto: supongamos que su implementación está respaldada por una matriz dinámica (así es como funciona ArrayList , por ejemplo). Ahora, supongamos que quiere eliminar elementos en el rango [inicio, fin]. La implementación predeterminada de removeRange funciona al hacer que un iterador coloque el start , y luego llama a remove() el número apropiado de veces.

Cada vez que se remove() , la implementación de la matriz dinámica debe mezclar todos los elementos en la posición start + 1 y reenviar un punto para llenar el espacio restante en el elemento eliminado. Esto podría tomar tiempo O (n), ya que es posible que todos los elementos de la matriz deban barajarse. Esto significa que si quita un total de k elementos de la lista, el enfoque ingenuo tomará tiempo O (kn), ya que está haciendo O (n) trabaja k veces.

Ahora considere un enfoque mucho mejor: copie el elemento en el end de la posición al start posición, luego el elemento end + 1 para colocar el start + 1 , etc. hasta que se copien todos los elementos. Esto requiere que solo haga un total de O (n) trabajo, porque cada elemento se mueve como máximo una vez. Comparado con el enfoque O (kn) dado por el algoritmo ingenuo, esta es una gran mejora en el rendimiento. Por lo tanto, anular removeRange para utilizar este algoritmo más eficiente puede aumentar drásticamente el rendimiento.

¡Espero que esto ayude!