28 votos

¿Por qué es lista.size()>0 más lento que el de la lista.isEmpty() en Java?

¿Por qué es list.size()>0 más lento de lo list.isEmpty() en Java? En otras palabras, por qué isEmpty() es preferible a size()>0?

Cuando miro a la aplicación en ArrayList, parece que la velocidad debe ser la misma:

ArrayList.size()

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
      return size;
    }

ArrayList.isEmpty()

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
     }

Si acabamos de escribir un programa simple para obtener el tiempo de tomar por los dos métodos, en ese caso size() tendrá más isEmpty() en todos los casos, ¿por qué esta así?

Aquí está mi TestCode;

import java.util.List;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        List l=new Vector();
        int i=0;
        for(i=0;i<10000;i++){
            l.add(new Integer(i).toString());
        }
        System.out.println(i);
        Long sTime=System.nanoTime();
        l.size();
        Long eTime=System.nanoTime();
        l.isEmpty();
        Long eeTime=System.nanoTime();
        System.out.println(eTime-sTime);
        System.out.println(eeTime-eTime);
    }
}

Aquí eTime-sTime>eeTime-eTime en todos los casos. Por qué?

49voto

Andrzej Doyle Puntos 52541

Para ArrayLists, sí, tienes razón de que las operaciones se llevarán a (aproximadamente) el mismo tiempo.

Para otras implementaciones de la lista de ingenuos listas enlazadas*, por ejemplo, para contar el tamaño podría tomar un tiempo muy largo, mientras que realmente solo importa si es mayor que cero.

Así que si usted absolutamente seguro de que la lista es una implementación de ArrayList y nunca va a cambiar nunca, entonces realmente no importa; pero:

  1. esta es una mala práctica de programación de todos modos a ate de abajo a una aplicación específica.
  2. Si las cosas cambian un par de años abajo de la línea con el código de reestructuración, las pruebas demostrará que "funciona" pero las cosas están funcionando de manera menos eficiente que antes
  3. Incluso en el mejor de los casos, size() == 0 todavía no es más rápido que isEmpty(), así que no hay ninguna razón de peso para utilizar nunca la primera.
  4. isEmpty es una definición más clara de qué es lo que realmente importa son las pruebas, y por lo que hace el código un poco más comprensible.

(También, me gustaría revisar el uso de NULL en el encabezado de la pregunta; la pregunta en sí, y de estas operaciones, no tienen nada que ver con el hecho de que cualquier objeto de las referencias son null.)

* Originalmente escribí LinkedList aquí, implictly de referencia de java.util.LinkedList, a pesar de que en particular en la aplicación de la tienda de su longitud de forma explícita, haciendo que el tamaño de la() O(1) operación aquí. Una más ingenuo lista enlazada operación no podría hacer esto, y en un sentido más general no hay ninguna garantía de eficiencia en las implementaciones de Lista.

37voto

JRL Puntos 36674

Su prueba de código es erróneo.

Simplemente se invierte el orden, yo.correo llamada isEmpty primer y el tamaño > 0 segundo y obtendrás el opuesto resultado. Esto es debido a la clase de carga, almacenamiento en caché, etc.

13voto

Robert Munteanu Puntos 31558

Lo siento, pero su punto de referencia es errónea. Echa un vistazo a Java teoría y la práctica: Anatomía de un defectuoso microbenchmark para una descripción general sobre cómo acercarse a los puntos de referencia.


Actualización: para un adecuado punto de referencia que usted debe buscar en Japex.

5voto

wds Puntos 9910

Usted dijo:

Aquí eTime-sTime>eeTime-eTime en todos los casos, por Qué?

En primer lugar, es probablemente a causa de su código de prueba. Usted no puede probar la velocidad de llamar l.size() y l.isEmpty() al mismo tiempo, ya que tanto las consultas como el mismo valor. Lo más probable llamando l.size() se ha cargado el tamaño de su lista en su caché de cpu y llamando l.isEmpty() es mucho más rápido.

Usted podría tratar de llamar a l.size() un par de millones de veces y l.isEmpty() un par de millones de veces en los dos programas independientes pero, en teoría, el compilador sólo podría optimizar lejos de todas esas llamadas ya que no estás haciendo nada con los resultados.

En cualquier caso, la diferencia de rendimiento entre los dos van a ser insignificantes, especialmente una vez que haces la comparación que usted necesita hacer para ver si la lista está vacía (l.size() == 0). Más probable es que el código generado se ven casi completamente similar. Como algunos otros pósters de lo contrario, usted desea optimizar para mejorar la legibilidad en este caso, no de velocidad.

edit: he probado a mí mismo. Se trata prácticamente de una sacudida. size() y isEmpty() utilizado en Vector dieron resultados diferentes en las tandas largas, ni vencer a los otros constantemente. Cuando se ejecuta en un ArrayList size() parecía más rápido, pero no por mucho. Esto es más probable debido al hecho de que el acceso a la Vector está sincronizado, así que lo que realmente estamos viendo cuando se trata de punto de referencia para el acceso a estos métodos es la sincronización de sobrecarga, que puede ser muy sensible.

La cosa aquí es que cuando usted está tratando de optimizar un método de llamada con un par de nanosegundos diferencia en el tiempo de ejecución, entonces estás haciendo mal. Obtener los conceptos básicos: en primer lugar, como el uso de Longs donde usted debe utilizar long.

1voto

Stephen Denne Puntos 17031

Contar los elementos de una lista enlazada puede ser muy lento.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X