组合 Java 性能

Question

我想以很大的可能性使用这个函数，比如 700 整数，但该函数执行时间太长。有人有提高性能的想法吗？谢谢:)

public static Set<Set<Integer>> combinations(List<Integer> groupSize, int k) {
    Set<Set<Integer>> allCombos = new HashSet<Set<Integer>> ();
    // base cases for recursion
    if (k == 0) {
        // There is only one combination of size 0, the empty team.
        allCombos.add(new HashSet<Integer>());
        return allCombos;
    }
    if (k > groupSize.size()) {
        // There can be no teams with size larger than the group size,
        // so return allCombos without putting any teams in it.
        return allCombos;
    }
    // Create a copy of the group with one item removed.
    List<Integer> groupWithoutX = new ArrayList<Integer> (groupSize);
    Integer x = groupWithoutX.remove(groupWithoutX.size() - 1);
    Set<Set<Integer>> combosWithoutX = combinations(groupWithoutX, k);
    Set<Set<Integer>> combosWithX = combinations(groupWithoutX, k - 1);
    for (Set<Integer> combo : combosWithX) {
        combo.add(x);
    }
    allCombos.addAll(combosWithoutX);
    allCombos.addAll(combosWithX);
    return allCombos;
}

Answer 1

您需要

在返回值上使用哪些Set功能？

如果您只需要其中的一些 - 也许只是iterator()或contains(...) - 那么您可以考虑返回一个即时计算组合的Iterator。

这里有一个有趣的机制来生成字典顺序集合的第 n 个组合。

Answer 2

其他数据结构。 您可以尝试使用BitSet而不是Set<Integer>。如果整数值具有野生范围（负，较大的间隙），请使用 groupSize 中的索引。

使用索引而不是整数值还有其他优点：所有子集作为位都可以在for循环中完成（BigInteger为set）。

暂无数据。 或者制作所有组合的迭代器 （Stream） 以重复应用于您的处理方法。

并发。 平行主义只意味着4/8的系数。ThreadPoolExecutor 和 Future 也許。

---

优化算法本身

集合集最好是一个列表。这极大地改善了添加集合。并显示算法是否不会错误地创建相同的集合。