Pregunta de rendimiento de Java Collection

Question

He creado un método que toma dos Collection<String> como entrada y copia uno al otro.

Sin embargo, no estoy seguro de si debería verificar si las colecciones contienen los mismos elementos antes de comenzar a copiar, o si solo debo copiar independientemente. Este es el método:

/** 
    * Copies from one collection to the other. Does not allow empty string. 
    * Removes duplicates. 
    * Clears the too Collection first 
    * @param src 
    * @param dest 
    */ 
public static void copyStringCollectionAndRemoveDuplicates(Collection<String> src, Collection<String> dest) { 
    if(src == null || dest == null) 
    return; 

    //Is this faster to do? Or should I just comment this block out 
    if(src.containsAll(dest)) 
    return; 

    dest.clear(); 
    Set<String> uniqueSet = new LinkedHashSet<String>(src.size()); 
    for(String f : src) 
    if(!"".equals(f)) 
    uniqueSet.add(f); 

    dest.addAll(uniqueSet); 
} 

tal vez es más rápido que simplemente quitar el

if(src.containsAll(dest)) 
    return; 

Debido a que este método va a iterar sobre la colección completa de todos modos.

Answer 1

Yo diría: ¡Eliminarlo! Es un 'código' duplicado, el conjunto está haciendo la misma operación 'contains()' por lo que no es necesario preprocesarlo aquí. A menos que tenga una gran colección de entradas y una brillante prueba O (1) para containsAll() ;-)

El conjunto es lo suficientemente rápido. Tiene una complejidad O (n) basada en el tamaño de la entrada (una contiene() y (tal vez) una operación add() para cada cadena) y si la prueba target.containsAll() falla, contains() se hace dos veces para cada cadena -> menos rendimiento.

EDITAR

Algunos pseudo código para visualizar mi respuesta

void copy(source, dest) { 
    bool:containsAll = true; 
    foreach(String s in source) { // iteration 1 
    if (not s in dest) {   // contains() test 
     containsAll=false 
     break 
    } 
    } 
    if (not containsAll) { 
    foreach(String s in source) { // iteration 2 
     if (not s in dest) {  // contains() test 
     add s to dest 
     } 
    } 
    } 
} 

Si todos los elementos de la fuente están en dest, a continuación, contiene() se llama una vez para cada elemento de origen. Si todos menos los últimos elementos de origen están en dest (el peor de los casos), entonces contiene() se llama (2n-1) veces (n = tamaño de la colección de origen). Pero el número total de contiene() prueba con la prueba adicional es siempre igual o mayor que el mismo código sin la prueba adicional.

EDIT 2 supongamos, tenemos las siguientes colecciones:

source = {"", "a", "b", "c", "c"} 
dest = {"a", "b"} 

En primer lugar, la prueba containsAll falla, debido a que la cadena vacía en origen no está en dest (este es un pequeño defecto de diseño en tu codigo ;)). A continuación, cree un conjunto temporal que será {"a", "b", "c"} (Cadena vacía y segunda "c" ignorada). Finalmente agregas todo a dest y asumiendo, dest es una ArrayList simple, el resultado es {"a", "b", "a", "b", "c"}. ¿Esa es la intención? Una alternativa más corta:

void copy(Collection<String> in, Collection<String> out) { 
    Set<String> unique = new HashSet<String>(in); 
    in.remove(""); 
    out.addAll(unique); 
} 

Answer 2

Podría compararla, si importaba mucho. Creo que la llamada al containsAll() probablemente no ayude, aunque podría depender de la frecuencia con que las dos colecciones tengan el mismo contenido.

Pero este código es confuso. Está tratando de agregar nuevos elementos al dest? Entonces, ¿por qué aclara primero? Simplemente devuelva su nuevo uniqueSet a la persona que llama en lugar de molestarlo. ¿Y no está su cheque containsAll() invertido?

Answer 3

El containsAll() no sería de ayuda si target tiene más elementos que dest:
objetivo: [a, b, c, d]
dest: [a, b, c]
target.containsAll(dest) es cierto, por lo dest es [a, b, c] pero debería ser [a, b, c, d].

creo que el siguiente código es más elegante:

Set<String> uniqueSet = new LinkedHashSet<String>(target.size()); 
uniqueSet.addAll(target); 
if(uniqueSet.contains("")) 
    uniqueSet.remove(""); 

dest.addAll(uniqueSet); 

Answer 4

1. Demasiados nombres de los parámetros confusas. dest y target tienen casi el mismo significado. Será mejor que elija algo como dest y source. Hará las cosas mucho más claras incluso para ti.

2. Tengo la sensación (no estoy seguro de que es correcto) de que usa el API de colecciones de una manera incorrecta. La interfaz Collection no dice nada acerca de la unicidad de sus elementos, pero le agrega esta cualidad.

3. Modificar colecciones que pasaron como parámetros no es la mejor idea (pero como de costumbre, depende). En general, la mutabilidad es dañina e innecesaria. Por otra parte, ¿qué pasa si las colecciones pasadas son inmodificables/inmutables? Es mejor devolver una nueva colección y luego modificar las colecciones entrantes.

4. Collection interfaz tiene métodos addAll, removeAll, retainAll. ¿Los probaste primero? ¿Ha realizado pruebas de rendimiento para el código como:

   Collection<String> result = new HashSet<String> (dest); 
   result.addAll (target); 
   

   o

   target.removeAll (dest); 
   dest.addAll (target); 
   

Answer 5

El código es difícil de leer y no es muy eficiente. El parámetro "dest" es confuso: se pasa como un parámetro, luego se borra y los resultados se agregan a él. ¿Cuál es el punto de que sea un parámetro? ¿Por qué no simplemente devuelve una nueva colección? El único beneficio que puedo ver es que la persona que llama puede determinar el tipo de colección. ¿Es eso necesario?

creo que este código puede ser más clara y probablemente más eficiente escrita de la siguiente manera:

public static Set<String> createSet(Collection<String> source) { 
    Set<String> destination = new HashSet<String>(source) { 
     private static final long serialVersionUID = 1L; 

     public boolean add(String o) { 
      if ("".equals(o)) { 
       return false; 
      } 
      return super.add(o); 
     } 
    }; 
    return destination; 
} 

Otra forma es crear su propio tipo de conjunto:

public class NonEmptyStringSet extends HashSet<String> { 
    private static final long serialVersionUID = 1L; 

    public NonEmptyStringSet() { 
     super(); 
    } 

    public NonEmptyStringSet(Collection<String> source) { 
     super(source); 
    } 

    public boolean add(String o) { 
     if ("".equals(o)) { 
      return false; 
     } 
     return super.add(o); 
    } 
} 

Uso:

createSet(source); 
new NonEmptyStringSet(source); 

Devolver el conjunto es más eficaz ya que primero no tiene que crear un conjunto temporal y luego un anuncio d todo a la colección dest.

El beneficio del tipo NonEmptyStringSet es que puede seguir agregando cadenas y aún tener la verificación de cadena vacía.

EDIT1:

Extracción del "si (src.containsAll (dest)) return;" código introduce un "error" al llamar al método con fuente == dest; El resultado es que la fuente estará vacía Ejemplo:.

Collection<String> source = new ArrayList<String>(); 
source.add("abc"); 
copyStringCollectionAndRemoveDuplicates(source, source); 
System.out.println(source); 

Edit2:

Hice un pequeño benchmark que muestra que mi implementación es aproximadamente un 30% más rápida que una versión simplificada de su implementación inicial. Este benchmark es un caso óptimo para su implementación inicial porque la colección de destino está vacía, por lo que no tiene que borrarla También tenga en cuenta que mi implementación utiliza HashSet en lugar de LinkedHashSet, lo que hace que mi implementación sea un poco más rápida.

código

Benchmark:

public class SimpleBenchmark { 
public static void main(String[] args) { 
    Collection<String> source = Arrays.asList("abc", "def", "", "def", "", 
      "jsfldsjdlf", "jlkdsf", "dsfjljka", "sdfa", "abc", "dsljkf", "dsjfl", 
      "js52fldsjdlf", "jladsf", "dsfjdfgljka", "sdf123a", "adfgbc", "dslj452kf", "dsjfafl", 
      "js21ldsjdlf", "jlkdsvbxf", "dsfjljk342a", "sdfdsa", "abxc", "dsljkfsf", "dsjflasd4"); 

    int runCount = 1000000; 
    long start1 = System.currentTimeMillis(); 
    for (int i = 0; i < runCount; i++) { 
     copyStringCollectionAndRemoveDuplicates(source, new ArrayList<String>()); 
    } 
    long time1 = (System.currentTimeMillis() - start1); 
    System.out.println("Time 1: " + time1); 


    long start2 = System.currentTimeMillis(); 
    for (int i = 0; i < runCount; i++) { 
     new NonEmptyStringSet(source); 
    } 
    long time2 = (System.currentTimeMillis() - start2); 
    System.out.println("Time 2: " + time2); 

    long difference = time1 - time2; 
    double percentage = (double)time2/(double) time1; 

    System.out.println("Difference: " + difference + " percentage: " + percentage); 
} 

public static class NonEmptyStringSet extends HashSet<String> { 
    private static final long serialVersionUID = 1L; 

    public NonEmptyStringSet() { 
    } 

    public NonEmptyStringSet(Collection<String> source) { 
     super(source); 
    } 

    @Override 
    public boolean add(String o) { 
     if ("".equals(o)) { 
      return false; 
     } 
     return super.add(o); 
    } 
} 

public static void copyStringCollectionAndRemoveDuplicates(
     Collection<String> src, Collection<String> dest) { 
    Set<String> uniqueSet = new LinkedHashSet<String>(src.size()); 
    for (String f : src) 
     if (!"".equals(f)) 
      uniqueSet.add(f); 

    dest.addAll(uniqueSet); 
} 
} 

Answer 6

Realmente no creo que entiendo por qué desea este método, pero suponiendo que vale la pena, me gustaría ponerlo en práctica de la siguiente manera:

public static void copyStringCollectionAndRemoveDuplicates(
     Collection<String> src, Collection<String> dest) { 
    if (src == dest) { 
     throw new IllegalArgumentException("src == dest"); 
    } 
    dest.clear(); 
    if (dest instanceof Set) { 
     dest.addAll(src); 
     dest.remove(""); 
    } else if (src instance of Set) { 
     for (String s : src) { 
      if (!"".equals(s)) { 
       dest.add(s); 
      } 
     } 
    } else { 
     HashSet<String> tmp = new HashSet<String>(src); 
     tmp.remove(""); 
     dest.addAll(tmp); 
    } 
} 

notas:

1. esto no conserva el orden de los elementos en el argumento src en todos los casos, pero la firma del método implica que esto es irrelevante.
2. Deliberadamente no compruebo null. Es un error si se proporciona un nulo como argumento, y lo correcto es permitir que se genere un NullPointerException.
3. Intentar copiar una colección a sí mismo también es un error.