¿Qué tan caro es el tamaño de llamada() en Lista o Mapa en Java?

Question

¿Cuánto cuesta llamar a size() en List o Map en Java? o es mejor guardar el valor de size() en una variable si se accede con frecuencia?

Answer 1

La respuesta es que depende de la clase de implementación real. Para algunas clases Map y Collection, size() es una operación económica de tiempo constante. Para otros, puede implicar contar los miembros.

El Java Collections Cheatsheet (V2) es normalmente una buena fuente para este tipo de información, pero el servidor host está actualmente un poco enfermo.

El dominio "coderfriendly.com" ya no existe, pero rastreé una copia de the cheat-sheet en scribd.com.

El costo de size() también será obvio al mirar el código fuente. (Y esto es un "detalle de implementación" que está casi seguro de no cambiar ... para las clases de colección estándar.)

FOLLOWUP

Por desgracia, la única cheatsheet documenta la complejidad de size para la cola implementaciones.Creo que es porque es O(1) para todas las demás colecciones; ver la respuesta de @seriesizer

Answer 2

para ArrayList la puesta en práctica es como

public int size() { 
     return lastIndex - firstIndex; 
    } 

Así no sobre la cabeza

Puede comprobar el código fuente para obtener información detallada requerida para su Impl.

Nota: La fuente dada es de OpenJDK

Answer 3

Usted no tiene que preocuparse mucho acerca de eso. Las implementaciones de lista realizan un seguimiento del tamaño. El costo de la llamada es solo O (1). Si tiene mucha curiosidad, puede leer el código fuente de las implementaciones de las clases concretas de Collection y ver allí el método de size().

Answer 4

La implementación la obtiene de una variable precomputada privada, por lo que no es cara.

Answer 5

No hay necesidad de almacenar. No es para nada caro. Compruebe la fuente de ArrayList y HashMap.

Answer 6

Impleméntelo, luego pruébelo. Si es lento, échale un vistazo más de cerca.

"La optimización prematura es la raíz de todo mal". - D. Knuth

También: No debe requerir ciertas características de implementación, especialmente si están enmarcadas. ¿Qué sucede si reemplaza esa lista con una lista concurrente en una fecha posterior? ¿Qué sucede si Oracle decide reescribir List? ¿Seguirá siendo rápido? Usted simplemente no sabe.

Answer 7

Creo que algunas implementaciones de LinkedList cuentan el total de cada llamada. La llamada a un método en sí puede ser un poco exigente, pero solo si estamos hablando de grandes iteraciones o códigos de controladores para hardware, realmente sería un problema.

En cualquier caso, si lo guarda en una variable local, no habrá ningún problema.

Answer 8

List y Map son interfaces, por lo que es imposible de decir. Para las implementaciones en la API estándar de Java, el tamaño generalmente se mantiene en un campo y, por lo tanto, no es relevante para el rendimiento.

Answer 9

Para la mayoría de las colecciones, llamar al size() es una operación de tiempo constante. Sin embargo, hay algunas excepciones. Uno es ConcurrentLinkedQueue. Desde el Javadoc de the size() method:

Tenga en cuenta que, a diferencia de la mayoría de las colecciones, este método NO es una operación de tiempo constante. Debido a la naturaleza asíncrona de estas colas, determinar el número actual de elementos requiere un recorrido O (n).

Así que me temo que no hay una respuesta genérica, debe verificar la documentación de la colección individual que está utilizando.