Estoy pensando en llenar una colección con una gran cantidad de objetos únicos. ¿Cómo se compara el costo de un inserto en un conjunto (p. Ej. HashSet) con una lista (por ejemplo, ArrayList)?Inserción de colección Java: Conjunto vs. Lista
Mi sensación es que la eliminación duplicada en los conjuntos puede causar una ligera sobrecarga.
No hay una "eliminación duplicada", como la comparación de todos los elementos existentes. Si inserta en el conjunto de hash, es realmente un diccionario de elementos por código hash. No hay verificación duplicada a menos que ya haya elementos con el mismo código hash. Dada una función hash razonable (bien distribuida), no es tan malo.
Como ha notado Will, debido a la estructura del diccionario HashSet es probablemente un poco más lento que ArrayList (a menos que desee insertar "entre" elementos existentes). También es un poco más grande. Sin embargo, no estoy seguro de que sea una diferencia significativa.
La eliminación duplicada está ahí, es solo inherente a la estructura de datos. –
Derecha. Quiero decir, normalmente no hay una eliminación duplicada que siempre compare el elemento recién insertado con todos los existentes (a menos que se equivoque con el 'hashCode'). –
Gracias por aclarar. Sin embargo, insertar en una lista es un poco más pequeño conceptualmente, ¿no? – Will
Hay que comparar implementaciones concretas (por ejemplo HashSet con ArrayList), debido a que las interfaces abstractas Set/List realmente no le dicen nada sobre el rendimiento.
Insertar en un HashSet es una operación bastante económica, siempre que el hashCode() del objeto que se va a insertar esté en buen estado. Todavía será un poco más lento que ArrayList, porque su inserción es una inserción simple en una matriz (suponiendo que inserte en el extremo y todavía hay espacio libre; no tengo en cuenta el cambio de tamaño del conjunto interno, porque el mismo costo se aplica al HashSet también).
Tiene razón: las estructuras de conjuntos son inherentemente más complejas para reconocer y eliminar duplicados. Si esta sobrecarga es significativa para su caso, debe probarse con un punto de referencia.
Otro factor es el uso de la memoria. Si sus objetos son muy pequeños, la sobrecarga de memoria introducida por la estructura del conjunto puede ser significativa. En el caso más extremo (TreeSet<Integer> frente a ArrayList<Integer>), la estructura establecida puede requerir más de 10 veces más memoria.
Si usted es cierto sus datos serán únicos, utilice una lista. Puede usar un conjunto para hacer cumplir esta regla.
Sets are faster than Lists si tiene un conjunto de datos grande, mientras que inverse is true para conjuntos de datos más pequeños. No he probado personalmente esta afirmación.
¿Qué tipo de lista?
Además, considere qué lista usar. LinkedLists son más rápidos al agregar, eliminar elementos.
ArrayLists son más rápidos en el acceso aleatorio (for bucles, etc.), pero esto se puede evitar mediante el Iterator de un LinkedList. ArrayLists son mucho más rápido en: list.toArray().
No estoy seguro de que las listas enlazadas sean rápidas para la inserción ... Pensé que era O (n) el momento de buscar la posición, y luego el tiempo constante (y bajo) para la inserción misma. LinkedList no proporciona acceso aleatorio a los datos. Además, un iterador ** no ** proporciona acceso aleatorio. – Agemen
En realidad, sospecho que todo depende de la implementación, y el OP puede construir fácilmente el suyo. Las interfaces List y Set obviamente no proporcionan ningún código concreto, por lo que uno puede hacerse más rápido que el otro. Dicho esto, no estoy seguro de cómo, pero me ha impresionado enormemente LinkedList y lo he cambiado después de encontrar que ArrayList era demasiado lento. Lo que estaba haciendo era 'add()' e iteration – Redandwhite
Esto se debe a la estructura de LinkedList, y porque regularmente necesita hacer una copia de array cuando usa add en una ArrayList. LinkedLists es realmente eficiente para las inserciones al principio o al final, pero definitivamente no para el acceso aleatorio. Las inserciones no están limitadas a agregar operaciones. – Agemen
Si el objetivo es la unicidad de los elementos, debe usar una implementación de la interfaz java.util.Set.La clase java.util.HashSet y java.util.LinkedHashSet tienen O (alpha) (cerca de O (1) en el mejor de los casos) complejidad para insertar, eliminar y contener verificación.
ArrayList tienen O (n) para el objeto (no índice) contiene cheque (que tiene que desplazarse a través de toda la lista) y la inserción (si la inserción no está en la cola de la lista, usted tiene que cambiar el conjunto subrayar matriz).
Puede usar LinkedHashSet que conservan el orden de inserción y tienen el mismo potencial de HashSet (ocupa solo un poco más de memoria).
No creo que pueda hacer este juicio simplemente sobre el costo de la construcción de la colección. Otras cosas que debe tener en cuenta son:
Todos estos pueden afectar su elección de estructura de datos.
Lista de Java:
Si usted no tiene tal requisito de que usted tiene que mantener duplicado o no. Entonces puede usar List en lugar de Set.
La lista es una interfaz en el marco de recopilación. Que extiende la interfaz de Colección. y ArrayList, LinkedList es la implementación de la interfaz de lista.
Cuándo utilizar ArrayList o LinkedList
ArrayList: Si usted tiene tal requisito de que en su aplicación sobre todo el trabajo está accediendo a los datos. Entonces deberías ir por ArrayList. porque ArrayList implementa la interfaz RtandomAccess, que es la interfaz de marcador. debido a la interfaz Marray, ArrayList tiene capacidad para acceder a los datos en O (1) vez. y puede usar ArrayList sobre LinkedList donde desea obtener datos de acuerdo con el orden de inserción.
LinkedList: Si tiene tal requisito que su trabajo mayoritario es la inserción o eliminación. Entonces debería usar LinkedList sobre ArrayList. porque en LinkedList, la inserción y la eliminación se producen en O (1) tiempo, mientras que en ArrayList es O (n) hora.
Java Set:
Si usted tiene requisito de la aplicación que no desea que los duplicados. Entonces deberías buscar Set en lugar de List. Porque Set no almacena ningún duplicado. Porque Set funciona según el principio de Hashing. Si agregamos un objeto en Set, primero verifica el hashCode del objeto en el cubo si encuentra que hay presente un hashCode en él, entonces no agregará ese objeto.
Si ya tiene algún mecanismo que garantice la unicidad, ¿por qué molestarse con el conjunto? Si no lo hace y necesita garantizar la exclusividad, entonces una lista definitivamente no es lo que quiere. – Andrew