I have been working on code to iteratively partition integers and use previous results to fully partition the numbers, with the idea that using previous partitions can increase speed. So far, I have gotten performance 22x slower than recursively partitioning the integers, and haven't been able to test larger numbers due to quickly running out of memory. If anyone could help optimize the code, I would be grateful for the help.
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());
}*/
}
}
