Java 创建新集合太慢

Question

我有这个程序，它有一些类似于以下的递归函数：

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

我正在做的是将每个集合与集合 s 结合起来。并在每个联合上运行 lambda。 我运行探查器，发现 c.clone() 操作占用了我代码 100% 的时间。有什么办法可以大大加快这个速度吗？

Answer 1

当你克隆时，你真正想要做什么，也许你不需要做一个完整的克隆？

提高 lambda 函数性能的最佳选择是扩展 HashSet 并使用特定于您的情况的自定义定义覆盖克隆定义...

不幸的是，我不知道有任何其他方法可以真正帮助您提供更多信息。

Answer 2

如果我做对了，你可以尝试执行以下操作：

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

你可以通过重新实现列表并使用节点作为 lambda 的参数来避免克隆 p 例如：

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
}

这是一个低级解决方案，你必须实现缓慢的顺序搜索/ find-algorithm（如果您依赖于集合中的唯一元素），但根据我的经验，这样的堆栈对于大多数递归算法来说是一个很好的解决方案。

Answer 3

这就是我为了加快一切速度所做的事情，这样我就不必创建新的集合。

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

平均而言，这要快得多，并且程序在 addAll 和 removeAll 上花费的时间大致相同。