2010-05-27 20 views
5

Ho creato un metodo che richiede due input Collection<String> e ne copia uno nell'altro.Domanda prestazioni raccolta Java

Tuttavia, non sono sicuro se dovrei controllare se le raccolte contengono gli stessi elementi prima di iniziare a copiare, o se dovrei semplicemente copiare indipendentemente. Questo è il metodo:

/** 
    * 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); 
} 

Forse è più veloce per rimuovere solo il

if(src.containsAll(dest)) 
    return; 

Poiché questo metodo sarà iterare l'intera collezione in ogni modo.

+2

Solo un commento minore, non correlato alla tua domanda: target e des hanno significati simili. Dal momento che stai copiando una stringa non vuota da destinazione a destinazione, forse può essere rinominata in src? –

risposta

7

Direi: rimuovilo! È un 'codice' duplicato, il Set sta facendo la stessa operazione 'contains()' quindi non c'è bisogno di pre-processarlo qui. A meno che tu non abbia un'enorme collezione di input e un brillante test O (1) per containsAll() ;-)

Il Set è abbastanza veloce. Ha una complessità O (n) basata sulla dimensione dell'input (una contiene() e (forse) una operazione add() per ogni stringa) e se il test target.containsAll() fallisce, contains() viene eseguito due volte per ogni stringa -> meno performante.

EDIT

Alcuni pseudo codice per visualizzarne mia risposta

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 
     } 
    } 
    } 
} 

Se tutti gli elementi sorgente sono in dest, quindi contiene() viene chiamato una volta per ogni elemento di origine. Se tutti tranne gli ultimi elementi sorgente sono in dest (worst case), quindi contains() è chiamato (2n-1) times (n = size of source collection). Ma il numero totale di contiene() prova con il test aggiuntivo è sempre uguale o maggiore dello stesso codice senza il test aggiuntivo.

EDIT 2 lascia supporre, abbiamo le seguenti collezioni:

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

In primo luogo, il test containsAll fallisce, perché la stringa vuota in sorgente non è in dest (questo è un piccolo difetto di progettazione in il tuo codice ;)). Quindi crei un set temporaneo che sarà {"a", "b", "c"} (stringa vuota e la seconda "c" ignorata). Infine aggiungi tutto a dest e assuming, dest è un semplice ArrayList, il risultato è {"a", "b", "a", "b", "c"}. È questa l'intenzione? Un'alternativa più breve:

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

Supponiamo di rimuovere il Set e di creare una copia che richiede la "Collezione ". Sarebbe utile controllare l'uguaglianza prima di aggiungere? –

2

Si potrebbe fare un benchmark, se fosse così importante. Penso che la chiamata a containsAll() probabilmente non aiuti, anche se potrebbe dipendere dalla frequenza con cui le due raccolte hanno lo stesso contenuto.

Ma questo codice è fonte di confusione. Sta cercando di aggiungere nuovi articoli a dest? Quindi perché lo chiarisce prima? Invece, restituisci il tuo nuovo uniqueSet al chiamante invece di preoccuparti. E il tuo assegno containsAll() non è invertito?

+0

È molto probabile che le raccolte abbiano lo stesso contenuto e si chiami almeno 10 volte –

3

Il containsAll() non sarebbe d'aiuto se target ha più elementi di dest:
bersaglio: [a, b, c, d]
dest: [a, b, c]
target.containsAll(dest) è vero, così dest è [a, b, c] ma dovrebbe essere [a, b, c, d].

penso che il seguente codice è più elegante:

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

dest.addAll(uniqueSet); 
+0

Accetto ... Salterò persino la chiamata a 'contains'. –

+0

Grazie, non ci ho pensato. In realtà il bersaglio ha molto probabilmente più elementi rispetto al dest –

1
  1. Troppi nomi dei parametri di confusione. dest e target hanno quasi lo stesso significato. Faresti meglio a scegliere qualcosa come dest e source. Renderà le cose molto più chiare anche per te.

  2. Ho la sensazione (non sono sicuro che sia corretto) che usi le API delle collezioni in modo sbagliato. L'interfaccia Collection non dice nulla su uniquness dei suoi elementi ma si aggiunge questa qualità ad esso.

  3. Modificare le raccolte che passano come parametri non è l'idea migliore (ma come al solito, dipende). In generale, la mutevolezza è dannosa e inutile. Inoltre, cosa succederebbe se le collezioni passate non fossero modificabili/immutabili? È meglio restituire una nuova collezione e quindi modificare le raccolte in arrivo.

    interfaccia
  4. Collection ha metodi addAll, removeAll, retainAll. Li hai provati prima? Avete fatto test di performance per il codice come:

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

    o

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

Il codice è difficile da leggere e non è molto efficiente. Il parametro "dest" è confuso: viene passato come parametro, quindi viene cancellato e vengono aggiunti i risultati. Qual è il punto di essere un parametro? Perché non semplicemente restituire una nuova collezione? L'unico vantaggio che posso vedere è che il chiamante può determinare il tipo di raccolta. È necessario?

penso che questo codice può essere più chiaro e probabilmente più efficace scritto come segue:

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; 
} 

Un altro modo è quello di creare un tipo di set:

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); 
    } 
} 

Usage:

createSet(source); 
new NonEmptyStringSet(source); 

Il ritorno del set è più performante perché non è necessario prima creare un set temporaneo e quindi un annuncio d tutti alla collezione dest.

Il vantaggio del tipo NonEmptyStringSet è che è possibile continuare ad aggiungere stringhe e mantenere il controllo della stringa vuota.

Edit1:

Rimozione del "if (src.containsAll (distillata)) return;" codice introduce un "errore" quando si chiama il metodo con sorgente == dest; Il risultato è che fonte sarà vuoto Esempio:.

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

EDIT2:

Ho fatto un piccolo benchmark che mostra che la mia implementazione è circa il 30% più veloce di una versione semplificata della tua implementazione iniziale Questo benchmark è un caso ottimale per la tua implementazione iniziale perché il gruppo di destinazione è vuoto, quindi non deve cancellarlo Inoltre, non prenderemo che la mia implementazione utilizzi HashSet invece di LinkedHashSet, il che rende la mia implementazione un po 'più veloce.

Codice

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); 
} 
} 
0

Io in realtà non credo che capisco perché si vuole questo metodo, ma supponendo che vale la pena, vorrei implementarlo come segue:

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); 
    } 
} 

Note:

  1. questo non conservi l'ordine degli elementi nella discussione src in tutti i casi, ma la firma del metodo implica che questo è irrilevante.
  2. Evento deliberatamente null. È un errore se viene fornito un valore null come argomento e la cosa corretta da fare è consentire il lancio di un valore NullPointerException.
  3. Anche il tentativo di copiare una raccolta su se stesso è un bug.