création Java de nouvelle série trop lent

Question

J'ai ce programme où il a une fonction récursive semblable à ceci:

public static void lambda(HashSet<Integer> s){ 
    if(end(s)){ 
     return; 
    } 
    for(int i=0;i<w;i++){ 
     HashSet<Integer> p = (HashSet) s.clone(); 
     p.addAll(get_next_set()); 
     do_stuff_to(p); 
     lambda(p); 
    } 
} 

Ce que je fais est l'union tous ensemble avec l'ensemble de l'art. Et lancez lambda sur chacun des syndicats. J'ai exécuté un profileur et trouvé l'opération c.clone() a pris 100% du temps de mon code. Y a-t-il un moyen d'accélérer cela considérablement?

Answer 1

C'est ce que j'ai fait pour tout accélérer, de cette façon je n'ai jamais besoin de créer de nouveaux sets.

public static void lambda(HashSet<Integer> s){ 
    if(end(s)){ 
     return; 
    } 
    ArrayList<Integer> diff = new ArrayList<Integer>(); 
    for(int i=0;i<w;i++){ 
     //an array version of the next set, it is pre-computed 
     int[] a = get_next_set_array(); 
     for(int j=0;j<a.length;j++){ 
      if(!s.contains(a[j])){ 
       diff.add(a[j]); 
      } 
     } 
     s.addAll(diff); 
     do_stuff_to(s); 
     s.removeAll(diff); 
     diff.clear(); 
     lambda(p); 
    } 
} 

En moyenne, c'est beaucoup plus rapide, et le programme passe à peu près le même laps de temps sur addAll et removeAll.

Answer 2

Lorsque vous clonez, qu'essayez-vous vraiment de faire, peut-être que vous n'avez pas besoin de faire un cloan complet?

Votre meilleur pari à améliorer les performances de votre fonction lambda est d'étendre HashSet et overide la définition de clone avec un personnalisé qui est particulier à votre situation ...

Je ne sais pas de anyother façon de vraiment aider avec plus d'informations malheureusement.

Answer 3

Si je bien vous essayez de faire ce qui suit:

lambda(Set p) { 
    lambda(p + further elements); 
} 

Vous pouvez éviter le clonage p par exemple par réimplémentant une liste et en utilisant les noeuds en tant que paramètres pour lambda:

class Node { 
    int content; 
    Node next; 

    Node(int content, Node next) { 
     this.content = content; 
     this.next = next; 
    } 
} 

void lambda(Node set) { 
    // add new elements to front 
    Node newSet = set; 

    for(Integer i : new_elements()) { 
     newSet = new Node(i, newSet); 
    } 

    lambda(newSet); 
    // Observe that set is not modified by adding new elements 
} 

Ceci est un faible niveau solution et vous auriez à mettre en œuvre une recherche séquentielle lente/trouver l'algorithme (si vous comptez sur des éléments uniques l'ensemble), mais dans mon expérience une telle pile est une bonne solution pour la plupart des algorithmes récursifs.