Java creation of new set too slow

Question

I have this program where it have some recursive function similar to this:

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

What I'm doing is union every set with the set s. And run lambda on each one of the union. I run a profiler and found the c.clone() operation took 100% of the time of my code. Are there any way to speed this up considerably?

Answer 1

Wait, how does your program end? What I see is this:

lambda(HashSet s){
    .
    p = s.clone();
    .
    lambda( p )

You sure you're not stuck in an infinite loop here?

Edit:

I see you changed the function. Wouldn't it make more sense:

Public static void lambda(HashSet<Integer> s, int _count){
    if( _count < 0 ){
        return;
    }

    s.addAll( get_next_set() );
    do_stuff_to( s );
    lambda( s, _count - 1 );
}

The issue here is that your original function and even this one as it is written will run more than "w" times if the "end" function doesn't return true after each operation.

Answer 2

When you are cloning, what are you really trying to do, maybe you don't need to do a complete cloan?

Your best bet at improving the performance of your lambda function is to extend HashSet and overide the clone definition with a custom one that is particular to your situation...

I don't know of anyother way to really help with out more information unfortunatly.

Answer 3

If I get it right you try to do the following:

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

You can avoid cloning p e.g. by reimplementing a list and using the Nodes as parameters for 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
}

This is a low-level-solution and you would have to implement a slow sequential search/find-algorithm (if you rely on unique elements in the set), yet in my experience such a stack is a good solution for most recursive algorithms.

Answer 4

This is what I did to speed up everything, this way I never have to create new 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);
    }
}

On average this is much faster, and the program spend roughly the same amount of time on the addAll and removeAll.