programacion - ¿Creando una lista distinta de la lista existente en Java 7 y 8?

manual programacion android español pdf (7)

Si tengo:

List<Integer> listInts = { 1, 1, 3, 77, 2, 19, 77, 123, 14, 123... }

en Java, ¿cuál es una forma eficiente de crear una List<Integer> listDistinctInts contiene solo los valores distintos de listInts ?

Mi pensamiento inmediato es crear un Set<Integer> setInts contenga todos los valores de listInts luego llamar a List<Integer> listDistinctInts = new ArrayList<>(setInts);

Pero esto parece potencialmente ineficiente. ¿Existe una solución mejor utilizando Java 7?

No estoy usando Java 8, pero creo que al usarlo podría hacer algo como esto (?):

List<Integer> listDistinctInts = listInts.stream().distinct().collect(Collectors.toList());

¿Sería esto más eficaz que el enfoque anterior y / o hay alguna forma más eficiente de hacerlo en Java 8?

Finalmente, (y soy consciente de que hacer muchas preguntas mal visto, pero está directamente relacionado) si solo me importó el conteo de elementos distintos en listInts existe una manera más eficiente de obtener ese valor (en Java 7 y 8) - ¿Sin crear primero una lista o conjunto de todos los elementos distintos?

Estoy más interesado en las formas nativas de Java de lograr esto y evitar reinventar las ruedas, pero consideraría las bibliotecas o el código enrollado a mano si ofrecen una mayor claridad o rendimiento. He leído esta pregunta relacionada sobre Java - Lista de objetos distintivos, pero no está del todo claro acerca de las diferencias en el rendimiento entre los enfoques de Java 7 y 8 o si hay mejores técnicas.

Ahora, MicroBench ha marcado la mayoría de las opciones propuestas por las excelentes respuestas proporcionadas. Como la mayoría de las preguntas relacionadas con el rendimiento no trivial, la respuesta a cuál es la mejor es "depende" .

Todas mis pruebas se realizaron con el arnés Java Microbenchmarking de JMH .

La mayoría de estas pruebas se realizaron con JDK 1.8, aunque también realicé algunas de las pruebas con JDK 1.7 solo para garantizar que su rendimiento no fuera muy diferente (fue casi idéntico). Probé las siguientes técnicas tomadas de las respuestas proporcionadas hasta el momento:

1. Java 8 Stream : la solución que usaba stream() propuse como posibilidad si utilizaba Java8:

public List<Integer> testJava8Stream(List<Integer> listInts) { return listInts.stream().distinct().collect(Collectors.toList()); }

Ventajas del enfoque moderno de Java 8, sin dependencias de terceros.

contras requiere Java 8

2. Agregar a la lista : la solución propuesta por Victor2748 donde se construye y agrega una nueva lista, solo si la lista no contiene el valor. Tenga en cuenta que también preasigno la lista de destinos al tamaño del original (el máximo posible) para evitar cualquier reasignación:

public List<Integer> testAddingToList(List<Integer> listInts) { List<Integer> listDistinctInts = new ArrayList<>(listInts.size()); for(Integer i : listInts) { if( !listDistinctInts.contains(i) ) { listDistinctInts.add(i); } } return listDistinctInts; }

pros Funciona en cualquier versión de Java, no es necesario crear un Set y luego copiar, no hay terceros.

Contras Debe revisar repetidamente la Lista para ver los valores existentes a medida que la construimos

3. GS Collections Fast (ahora Eclipse collections) : la solución propuesta por Craig P. Motlin utilizando la biblioteca de GS Collections y su lista personalizada de FastList :

public List<Integer> testGsCollectionsFast(FastList listFast) { return listFast.distinct(); }

Pros Según se informa, muy rápido, código expresivo simple, funciona en Java 7 y 8

contras Requiere una biblioteca de terceros y una lista FastList lugar de una List<Integer> regular List<Integer>

4. Adaptaciones de GS adaptadas : la solución FastList no se parecía mucho a la de like-for-like porque necesitaba que una FastList pasara al método en lugar de una buena lista de ArrayList<Integer> así que también probé el método del adaptador que Craig propuso:

public List<Integer> testGsCollectionsAdapted(List<Integer> listInts) { return listAdapter.adapt(listInts).distinct(); }

pros no requiere un FastList , funciona en Java 7 y 8

Contras Tiene que adaptar la lista, por lo que no puede funcionar tan bien, necesita una biblioteca de terceros

5. Guava ImmutableSet : el método propuesto por Louis Wasserman en los comentarios, y por 卢声远 Shengyuan Lu en su respuesta utilizando Guava :

public List<Integer> testGuavaImmutable(List<Integer> listInts) { return ImmutableSet.copyOf(listInts).asList(); }

profesionales Según se informa muy rápido, funciona en Java 7 u 8

contras Devuelve una Immutable List , no puede manejar nulos en la lista de entrada y requiere una biblioteca de terceros

7. HashSet - Mi idea original (también recomendada por EverV0id , ulix y Radiodef)

public List<Integer> testHashSet(List<Integer> listInts) { return new ArrayList<Integer>(new HashSet<Integer>(listInts)); }

Pros trabaja en Java 7 y 8, sin dependencias de terceros

contras No conserva el orden original de la lista, tiene que construir el conjunto y luego copiar en la lista.

6. LinkedHashSet : como la solución HashSet no conservó el orden de los enteros en la lista original, también probé una versión que usa LinkedHashSet para conservar el orden:

public List<Integer> testLinkedHashSet(List<Integer> listInts) { return new ArrayList<Integer>(new LinkedHashSet<Integer>(listInts)); }

pros Retiene el pedido original, funciona en Java 7 y 8, sin dependencias de terceros

Contras Es poco probable que sea tan rápido como el enfoque HashSet regular

Resultados

Aquí están mis resultados para varios tamaños diferentes de listInts (resultados ordenados de más lento a más rápido):

1. Tomando distinto de ArrayList de 100,000 entradas aleatorias entre 0-50,000 (es decir, lista grande, algunos duplicados)

Benchmark Mode Samples Mean Mean error Units AddingToList thrpt 10 0.505 0.012 ops/s Java8Stream thrpt 10 234.932 31.959 ops/s LinkedHashSet thrpt 10 262.185 16.679 ops/s HashSet thrpt 10 264.295 24.154 ops/s GsCollectionsAdapted thrpt 10 357.998 18.468 ops/s GsCollectionsFast thrpt 10 363.443 40.089 ops/s GuavaImmutable thrpt 10 469.423 26.056 ops/s

2. tomando la distinción de ArrayList de 1000 ints aleatorios entre 0-50 (es decir, lista mediana, muchos duplicados)

Benchmark Mode Samples Mean Mean error Units AddingToList thrpt 10 32794.698 1154.113 ops/s HashSet thrpt 10 61622.073 2752.557 ops/s LinkedHashSet thrpt 10 67155.865 1690.119 ops/s Java8Stream thrpt 10 87440.902 13517.925 ops/s GsCollectionsFast thrpt 10 103490.738 35302.201 ops/s GsCollectionsAdapted thrpt 10 143135.973 4733.601 ops/s GuavaImmutable thrpt 10 186301.330 13421.850 ops/s

3. Tomando distinto de ArrayList de 100 entradas aleatorias entre 0-100 (es decir, lista pequeña, algunos duplicados)

Benchmark Mode Samples Mean Mean error Units AddingToList thrpt 10 278435.085 14229.285 ops/s Java8Stream thrpt 10 397664.052 24282.858 ops/s LinkedHashSet thrpt 10 462701.618 20098.435 ops/s GsCollectionsAdapted thrpt 10 477097.125 15212.580 ops/s GsCollectionsFast thrpt 10 511248.923 48155.211 ops/s HashSet thrpt 10 512003.713 25886.696 ops/s GuavaImmutable thrpt 10 1082006.560 18716.012 ops/s

4. tomando la diferencia de ArrayList de 10 entradas aleatorias entre 0-50 (es decir, una pequeña lista, pocos duplicados)

Benchmark Mode Samples Mean Mean error Units Java8Stream thrpt 10 2739774.758 306124.297 ops/s LinkedHashSet thrpt 10 3607479.332 150331.918 ops/s HashSet thrpt 10 4238393.657 185624.358 ops/s GsCollectionsAdapted thrpt 10 5919254.755 495444.800 ops/s GsCollectionsFast thrpt 10 7916079.963 1708778.450 ops/s AddingToList thrpt 10 7931479.667 966331.036 ops/s GuavaImmutable thrpt 10 9021621.880 845936.861 ops/s

Conclusiones

Si solo toma los elementos distintos de una lista una vez, y la lista no es muy larga, cualquiera de estos métodos debería ser adecuado.
Los enfoques generales más eficientes provinieron de las bibliotecas de terceros: GS Collections y Guava se realizaron admirablemente.
Es posible que deba considerar el tamaño de su lista y el número probable de duplicados al seleccionar el método más eficaz.
El enfoque ingenuo de agregar a una nueva lista solo si el valor no está ya en él funciona bien para listas pequeñas, pero tan pronto como tenga más de un puñado de valores en la lista de entrada, realiza el peor de los métodos probados.
El método ImmutableSet.copyOf(listInts).asList() Guava funciona más rápido en la mayoría de las situaciones. Pero tome nota de las restricciones: la lista devuelta es Immutable y la lista de entrada no puede contener nulos.
El método HashSet realiza el mejor de los enfoques de terceros y, por lo general, mejor que los flujos de Java 8, pero reordena los enteros (lo que puede o no ser un problema según su caso de uso).
El enfoque LinkedHashSet mantiene el orden, pero como era de esperar, por lo general fue peor que el método HashSet.
Tanto el HashSet como el método LinkedHashSet tendrán un peor desempeño al usar listas de tipos de datos que tienen cálculos complejos de HashCode, así que haga su propio perfil si está tratando de seleccionar distintos Foo s de una List<Foo> .
Si ya tiene GS Collections como una dependencia, entonces se desempeña muy bien y es más flexible que el enfoque ImmutableList Guava . Si no lo tiene como una dependencia, vale la pena considerar agregarlo si el rendimiento de la selección de elementos distintos es fundamental para el rendimiento de su aplicación.
Decepcionantemente, las secuencias de Java 8 parecían funcionar bastante mal. Puede haber una mejor manera de codificar la llamada distinct() que la que usé, por lo que los comentarios u otras respuestas son bienvenidos, por supuesto.

NÓTESE BIEN. No soy un experto en MicroBenchmarking, por lo que si alguien encuentra fallas en mis resultados o metodología, por favor, avíseme y trataré de corregir la Respuesta.

Al agregar un valor a un listInts :

int valueToAdd; //... if (!listInts.contains(valueToAdd)) {listInts.add(valueToAdd)}

si tiene una lista existente, use una declaración para cada copia para copiar todos los valores de esa lista, a uno nuevo, que desea que sean "distintos":

List<Integer> listWithRepeatedValues; List<Integer> distinctList; //... for (Integer i : listWithRepeatedValues) { if (!listInts.contains(valueToAdd)) {distinctList.add(i);} }

Debes probar el new LinkedList(new HashSet(listInts)) .

Esto debería funcionar:

yourlist.stream (). map (su envoltorio que anula los métodos de método hashchode y hashchode :: new) .distinct (). map (envoltorio definido anteriormente :: método que devuelve el resultado final) .collect (Collectors.toList ());

No te preocupes Usar un HashSet es una forma bastante fácil y eficiente de eliminar duplicados:

Set<Integer> uniqueList = new HashSet<>(); uniqueList.addAll(listInts); // Add all elements eliminating duplicates for (int n : uniqueList) // Check the results (in no particular order) System.out.println(n); System.out.println("Number distinct values: " + uniqueList.size());

En un escenario más específico, en caso de que se conozca el rango de valores posibles, no es muy grande, mientras que listInts es muy grande.
La forma más eficiente de contar el número de entradas únicas en la lista que puedo imaginar es:

boolean[] counterTable = new boolean[124]; int counter = 0; for (int n : listInts) if (!counterTable[n]) { counter++; counterTable[n] = true; } System.out.println("Number of distinct values: " + counter);

Si está utilizando Eclipse Collections (anteriormente GS Collections ), puede usar el método distinct() .

ListIterable<Integer> listInts = FastList.newListWith(1, 1, 3, 77, 2, 19, 77, 123, 14, 123); Assert.assertEquals( FastList.newListWith(1, 3, 77, 2, 19, 123, 14), listInts.distinct());

La ventaja de usar distinct() lugar de convertir a un conjunto y luego volver a una lista es que distinct() conserva el orden de la lista original, conservando la primera aparición de cada elemento. Se implementa utilizando tanto un Conjunto como una Lista.

MutableSet<T> seenSoFar = UnifiedSet.newSet(); int size = list.size(); for (int i = 0; i < size; i++) { T item = list.get(i); if (seenSoFar.add(item)) { targetCollection.add(item); } } return targetCollection;

Si no puede convertir su Lista original en un tipo de Colecciones GS, puede usar ListAdapter para obtener la misma API.

MutableList<Integer> distinct = ListAdapter.adapt(integers).distinct();

No hay forma de evitar la creación del Set. Aún así, UnifiedSet es más eficiente que HashSet, por lo que habrá algún beneficio de velocidad.

Si todo lo que desea es la cantidad de elementos distintos, es más eficiente crear un conjunto sin crear la lista.

Verify.assertSize(7, UnifiedSet.newSet(listInts));

Eclipse Collections 8.0 requiere Java 8. Eclipse Collections 7.x funciona bien con Java 8, pero solo requiere Java 5.

Nota: Soy un comendador para las colecciones de Eclipse.

Guava puede ser tu elección:

ImmutableSet<Integer> set = ImmutableSet.copyOf(listInts);

La API está extremadamente optimizada.

Es MÁS RÁPIDO que listInts.stream().distinct() y new LinkedHashSet<>(listInts) .