整数分区迭代代码优化

本文介绍了整数分区迭代代码优化的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我一直在编写代码来对整数进行迭代分区，并使用以前的结果对数字进行完全分区，其想法是使用以前的分区可以提高速度.到目前为止，我的性能比递归分区整数慢 22 倍，并且由于内存快速耗尽而无法测试更大的数字.如果有人可以帮助优化代码，我将不胜感激.

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()); }*/ } }

推荐答案

您可以使用 mapToObj<生成一组指定数字的被加数的组合，即整数分区/code> 和 reduce 方法.首先准备被加数的数组集合，然后将这些集合的对依次相乘，得到笛卡尔积.

You can generate a set of combinations of the summands of the specified number, i.e. the integer partition, using mapToObj and reduce methods. First prepare the sets of arrays of summands, and then multiply the pairs of these sets sequentially and get the Cartesian product.

在线试用！

int n = 7; Set<int[]> partition = IntStream.range(0, n) // prepare sets of arrays of summands .mapToObj(i -> IntStream.rangeClosed(1, n - i) .mapToObj(j -> new int[]{j}) // Stream<TreeSet<int[]>> .collect(Collectors.toCollection( // comparing the contents of two arrays () -> new TreeSet<>(Arrays::compare)))) // intermediate output, sets of arrays of summands .peek(set -> System.out.println( set.stream().map(Arrays::toString).collect(Collectors.joining()))) // sequential summation of pairs of sets up to the given number .reduce((set1, set2) -> set1.stream() // combinations of inner arrays .flatMap(arr1 -> { // sum of the elements of the first array int sum = Arrays.stream(arr1).sum(); // if the specified number is reached if (sum == n) return Arrays.stream(new int[][]{arr1}); // otherwise continue appending summands return set2.stream() // drop the combinations that are greater .filter(arr2 -> Arrays.stream(arr2).sum() + sum <= n) .map(arr2 -> Stream.of(arr1, arr2) .flatMapToInt(Arrays::stream) .sorted().toArray()); // the sorted array }) // set of arrays of combinations .collect(Collectors.toCollection( // two arrays that differ // only in order are considered the same partition () -> new TreeSet<>(Arrays::compare)))) // otherwise an empty set of arrays .orElse(new TreeSet<>(Arrays::compare));

// final output, the integer partition of the specified number partition.stream().map(Arrays::toString).forEach(System.out::println);

中间输出，加数数组集:

Intermediate output, sets of arrays of summands:

[1][2][3][4][5][6][7] [1][2][3][4][5][6] [1][2][3][4][5] [1][2][3][4] [1][2][3] [1][2] [1]

最终输出，指定数字的整数分区:

Final output, the integer partition of the specified number:

[1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 2] [1, 1, 1, 1, 3] [1, 1, 1, 2, 2] [1, 1, 1, 4] [1, 1, 2, 3] [1, 1, 5] [1, 2, 2, 2] [1, 2, 4] [1, 3, 3] [1, 6] [2, 2, 3] [2, 5] [3, 4] [7]

另见:构建可有效求和为数字的排列