Rendimiento de clase Collection en Java

Question

Todo,

he estado pasando por una gran cantidad de sitios que después de la realización de diversas clases de colección de diferentes acciones es decir, la adición de un elemento, búsqueda y eliminación. Pero también noté que todos proporcionan diferentes entornos en los que se realizó la prueba, es decir, sistema operativo, memoria, subprocesos, etc.

Mi pregunta es si hay algún sitio/material que proporcione la misma información de rendimiento en la mejor prueba base del medio ambiente? es decir, las configuraciones no deberían ser un problema o un catalizador del bajo rendimiento de cualquier estructura de datos específica.

[Actualizado]: Ejemplo, HashSet y LinkedHashSet tienen una complejidad de O (1) para insertar un elemento. Sin embargo, la prueba de Bruce Eckel afirma que la inserción llevará más tiempo para LinkedHashSet que para HashSet [http://www.artima.com/weblogs/viewpost.jsp?thread=122295]. Entonces, ¿debería seguir usando la notación Big-Oh?

Answer 1

Aquí están mis recomendaciones:

1. En primer lugar, no optimice :) No es que Le estoy diciendo que diseñe el software basura, pero solo para enfocarse más en el diseño y la calidad del código que en la optimización prematura. Suponiendo que hayas hecho esto, y ahora que realmente tiene que preocuparse de lo que es mejor colección más allá de razones puramente conceptual, vamos a pasar al punto 2
2. Really, don't optimize yet (robados aproximadamente desde M. A. Jackson)
3. fina. Entonces, su problema es que, aunque tiene fórmulas teóricas de complejidad de tiempo para los mejores casos, los peores casos y los casos promedio, ha notado que las personas dicen cosas diferentes y que los ajustes prácticos son muy diferentes de la teoría. ¡Así que ejecuta tus propios puntos de referencia! Solo puede leer tanto, y mientras lo hace, su código no se escribe solo. Una vez que haya terminado con la teoría, escriba su propio punto de referencia, para su aplicación de la vida real, no una mini aplicación irrelevante para fines de prueba, y vea qué le sucede realmente a su software y por qué. Luego elige el mejor algoritmo. Es empírico, podría considerarse como una pérdida de tiempo, pero es la única manera de que funcione de manera impecable (hasta llegar al siguiente punto).
4. Ahora que lo ha hecho, tiene la aplicación más rápida. Hasta la próxima actualización de la JVM. O de algún componente subyacente del sistema operativo de su cuello de botella de rendimiento particular depende. ¿Adivina qué? Quizás tus clientes tengan otros diferentes. Aquí viene la diversión: debe asegurarse de que su punto de referencia sea válido para otros o en la mayoría de los casos (o se divierta escribiendo código para diferentes casos). Necesita recopilar datos de los usuarios. UN MONTÓN. Y luego necesita hacer eso una y otra vez para ver qué sucede y si sigue siendo cierto. Y luego volver a escribir el código en consecuencia una y otra vez (El - ahora terminado -. Engineering Windows 7 blog es en realidad un buen ejemplo de cómo la recopilación de datos de usuario ayuda a tomar decisiones informadas para mejorar la experiencia del usuario

O se puede .. . sabes ... NO optimizar las plataformas y compiladores cambiarán, pero un buen diseño debe - en promedio - llevará a cabo lo suficientemente bien

Otras cosas que también puede hacer:..

• Tener un vistazo a la El código fuente de JVM. Es muy educativo y descubres una manada de cosas ocultas (no digo cuando tenga que usarlos ...)
• ¿Vea esa otra cosa en su lista de cosas por hacer en la que necesita trabajar?Sí, el que está cerca pero que siempre saltas porque es muy difícil o no es lo suficientemente divertido. Ese justo ahí. Bien, hazlo y deja la cosa de la optimización sola: es el niño malvado de una caja de Pandora y una banda de Moebius. Nunca saldrás de ella, y lamentarás profundamente que hayas intentado hacerlo.

Dicho, no sé por qué es necesario el aumento de rendimiento por lo que tal vez usted tiene una razón válida muy.

Y no estoy diciendo que escoger la colección correcta no importe. Solo aquellos que sabe cuál elegir para un problema en particular, y que ha analizado alternativas, entonces ha hecho su trabajo sin tener que sentirse culpable. Las colecciones generalmente tienen un significado semántico, y mientras lo respetes estarás bien.

Answer 2

En mi opinión, todo lo que necesita saber sobre una estructura de datos es la Gran O de las operaciones en ella, no medidas subjetivas de diferentes arquitecturas. Las diferentes colecciones tienen diferentes propósitos.

Map s son los diccionarios
Set s afirman singularidad
List s proporcionan la agrupación y preservan iteración fin
Tree s proporcionan pedido barato y búsquedas rápidas en los contenidos dinámicamente cambiantes que requieren constantes pedidos

Editado a incluir la declaración de bwawok sobre el caso de uso de las estructuras de árbol

actualización
De la tabla hash javadoc on LinkedHashSet

y lista enlazada implementación de la interfaz Conjunto, con orden de iteración predecible.

...

rendimiento es probable que sea sólo un poco por debajo del de HashSet, debido al costo adicional de mantener la lista enlazada, con una excepción: la iteración sobre un LinkedHashSet requiere un tiempo proporcional al tamaño de la establecer, independientemente de su capacidad. La iteración sobre un HashSet probablemente sea más costosa, requiriendo tiempo proporcional a su capacidad.

Ahora hemos pasado del caso muy general de elegir una interfaz de estructura de datos apropiada al caso más específico de qué implementación usar. Sin embargo, finalmente llegamos a la conclusión de que las implementaciones específicas son adecuadas para aplicaciones específicas basadas en la invariante única y sutil que ofrece cada implementación.

Answer 3

¿Qué necesita saber sobre ellos, y por qué? La razón por la que los puntos de referencia muestran un JDK determinado y la configuración del hardware es para poder (en teoría) reproducirse. Lo que debe obtener de los puntos de referencia es una idea de cómo funcionarán las cosas. Para obtener un número ABSOLUTO, deberá ejecutarlo en comparación con su propio código haciendo lo suyo.

Lo más importante que debe saber es el tiempo de ejecución Big O de varias colecciones.Saber que obtener un elemento de un ArrayList sin ordenar es O (n), pero sacarlo de un HashMap es O (1) es ENORME.

Si ya está utilizando la colección correcta para un trabajo determinado, ya ha recorrido el 90% del camino. Los momentos en los que debe preocuparse de qué tan rápido puede, por ejemplo, sacar elementos de un HashMap, deberían ser bastante raros.

Una vez que abandone el terreno de un solo hilo y se mueva a un terreno con múltiples hilos, deberá comenzar a preocuparse por cosas como el hashmap ConcurrentHashMap vs Collections.synchronized. Hasta que tenga múltiples hilos, no puede preocuparse por este tipo de cosas y centrarse en qué colección para qué uso.

Update para HashSet vs LinkedHashSet

no he encontrado nunca un caso de uso en el que necesitaba un conjunto vinculado Hash (porque si me importa orden que tienden a tener una lista, si me importa O (1) obtiene, tiendo a usar un HashSet. De manera realista, la mayoría del código usará ArrayList, HashMap o HashSet. Si necesita algo más, se encuentra en un caso de "borde"

Answer 4

Si tuviera que ordenar millones de filas, trataría de encontrar una forma diferente. Tal vez podría mejorar mi SQL, mejorar mi algoritmo o quizás escribir los elementos en el disco y usar el comando de clasificación del sistema operativo.

Nunca he tenido un caso de colecciones en las que haya problemas de rendimiento.

Answer 5

Las diferentes clases de colección tienen diferentes interpretaciones de gran O, pero todo lo que le dice es cómo se escalan a medida que crecen. Si su conjunto es lo suficientemente grande, el que tiene O (1) superará al que tiene O (N) u O (logN), pero no hay manera de decir qué valor de N es el punto de equilibrio, excepto por el experimento.

En general, utilizo lo más simple posible, y luego si se convierte en un "cuello de botella", como indican las operaciones en esa estructura de datos que toman mucho porcentaje de tiempo, entonces cambiaré a algo con una gran O clasificación. A menudo, el número de elementos en la colección nunca llega al punto de equilibrio, o hay otra manera simple de resolver el problema de rendimiento.

Answer 6

Ambos HashSet y LinkedHashSet tienen O (1) rendimiento. Lo mismo con HashMap y LinkedHashMap (en realidad, los primeros se implementan según el último). Esto solo le dice cómo estos algoritmos escalan, no cómo funcionan realmente. En este caso, LinkHashSet hace todo el mismo trabajo que HashSet pero también siempre tiene que actualizar un puntero anterior y siguiente para mantener el orden. Esto significa que la constante (este es un valor importante también cuando se habla del rendimiento real del algoritmo) para HashSet es inferior a LinkHashSet.

Así, puesto que estos dos tienen el mismo Big-O, que la escala de la misma esencialmente - es decir, como n cambios, ambos tienen el mismo cambio en el rendimiento y con O (1) el rendimiento, en promedio, que hace Sin cambio.

Así que ahora su elección se basa en la funcionalidad y sus requisitos (que de todos modos debería ser lo primero que considere). Si solo necesita rápido agregue y obtenga operaciones, siempre debe elegir HashSet. Si también necesita un pedido consistente, como el último acceso o el pedido de inserción, entonces debe también usar la versión Linked ... de la clase.

He utilizado la clase "vinculada" en las aplicaciones de producción, así LinkedHashMap.Usé esto en un caso para un símbolo como tabla, así que quería acceso rápido a los símbolos y la información relacionada. Pero también quería mostrar la información en al menos un contexto en el orden en que el usuario definió esos símbolos (orden de inserción). Esto hace que la salida sea más amigable para el usuario, ya que puede encontrar las cosas en el mismo orden en que fueron definidas.

Answer 7

he creado mi propia experimentación con HashSets y LinkedHashSets. Para add() y contiene el tiempo de ejecución es O (1), sin tener en cuenta una gran cantidad de colisiones. En el método add() para un conjunto de enlaces, coloco el objeto en una tabla hash creada por el usuario que es O (1) y luego pongo el objeto en una lista de enlaces separada para dar cuenta de la orden. Por lo tanto, el tiempo de ejecución para eliminar un elemento de un conjunto de enlaces, debe encontrar el elemento en la tabla hash y luego buscar a través de la lista vinculada que tiene el orden. Por lo que el tiempo de ejecución es O (1) + O (n), respectivamente, que es O (n) para remove()