我一直在编写代码来迭代地划分整数并使用以前的结果来完全划分数字，我的想法是使用以前的分区可以提高速度。到目前为止，我的性能比递归地对整数进行分区慢了 22 倍，并且由于快速耗尽内存而无法测试更大的数字。如果有人可以帮助优化代码，我将不胜感激。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Collectors;
public class Summands {
private static HashMap<Integer, HashSet<List<Integer>>> results;
private static HashMap<Integer, HashSet<String>> recursiveResults;
private static void sort(int[] a) {
//Radix sort for int array
int i, m = a[0], exp = 1, n = a.length;
int[] b = new int[n];
for (i = 1; i < n; i++) {
if (a[i] > m) {
m = a[i];
}
}
while (m / exp > 0) {
int[] bucket = new int[n];
for (i = 0; i < n; i++)
bucket[(a[i] / exp) % n]++;
for (i = 1; i < n; i++)
bucket[i] += bucket[i - 1];
for (i = n - 1; i >= 0; i--)
b[--bucket[(a[i] / exp) % n]] = a[i];
for (i = 0; i < n; i++)
a[i] = b[i];
exp *= n;
}
}
private static void generateResults(int n) {
//iterative partitioning
results.put(n, new HashSet<>());
results.get(n).add(new ArrayList<>());
for (List<Integer> list : results.get(n)) {
list.add(n);
}
for (int i = 1; i <= Math.floorDiv(n, 2); i++) {
//get all 2 summands partitions
int a = n - i;
results.get(n).add(Arrays.asList(i, a));
}
if (n > 1) {
//Get the rest of the partitions
HashSet<List<Integer>> set = new HashSet<>(results.get(n));
for (List<Integer> equ : set) {
if (equ.size() > 1) {
if (equ.get(1) > 1) {
HashSet<List<Integer>> temp = results.get(equ.get(1));
for (List<Integer> k : temp) {
List<Integer> tempEquList = new ArrayList<>(k);
tempEquList.add(equ.get(0));
int[] tempEqu = tempEquList.stream()
.mapToInt(Integer::intValue).toArray();
sort(tempEqu);
results.get(n).add(Arrays.stream(tempEqu)
.boxed().collect(Collectors.toList()));
}
}
}
}
}
}
private static void recursivePartition(int n) {
//recursively partition
recursiveResults.put(n, new HashSet<>());
partition(n, n, "", n);
}
private static void partition(int n, int max, String prefix, int key) {
//recursive method for partitioning
if (n == 0) {
recursiveResults.get(key).add(prefix);
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
partition(n - i, i, prefix + " " + i, key);
}
}
public static void main(String[] args) {
//get number of partitions to get
int target = Integer.valueOf(args[0]);
//time the iterative version
long time1 = System.currentTimeMillis();
results = new HashMap<>(target);
//loop until done
for (int i = 1; i <= target; i++) {
System.out.println(i);
generateResults(i);
}
//time both methods
long time2 = System.currentTimeMillis();
recursiveResults = new HashMap<>(target);
for (int i = 1; i <= target; i++) {
//loop until done
System.out.println(i);
recursivePartition(i);
}
long time3 = System.currentTimeMillis();
System.out.println("Iterative time: " + String.valueOf(time2 - time1));
System.out.println("Recursive time: " + String.valueOf(time3 - time2));
/*for (Integer key : results.keySet()) {
//For ensuring proper amount of partitions
//for lower numbers. Primarily for testing
System.out.println(key + ": " + results.get(key).size());
}*/
}
}