patternjavaMinor
Integer Partition using an iterator
Viewed 0 times
iteratorpartitionintegerusing
Problem
I tried implementing Integer Partition (enumerating all possible sets of whole numbers whose sum is a given integer).
Looking at @rolfl's answer, I reasoned that with a stack data structure, we shouldn't need to use recursion, since recursion implicitly stores state in the call stack. I also tried to address @JeffVanzella's criticism about separation of concerns by converting the class into an iterator.
My solution ended up being a bit more monstrous than I had anticipated. It looks nothing like the elegant original, and runs more slowly too. Therefore, I suspect that a better iterative solution is possible.
```
import java.util.Iterator;
public class Partition implements Iterator {
/**
* Fixed-capacity stack of ints. As used in Partition.next(), the
* invariant is that elements towards the top of the stack are never
* larger than elements underneath. (In other words, the array
* elements are nonincreasing.
*/
private static class IntStack {
private int[] data;
private int size;
IntStack(int capacity) {
this.data = new int[capacity];
this.size = 0;
}
public void push(int datum) {
this.data[this.size++] = datum;
}
public int pop() {
return this.data[--this.size];
}
public boolean isEmpty() {
return this.size == 0;
}
/**
* Returns the elements as a space-delimited string.
*/
public String toString() {
// toString() of an empty stack is never used in practice...
if (this.isEmpty()) return "";
StringBuilder sb = new StringBuilder(String.valueOf(this.data[0]));
for (int i = 1; i 0; ones -= top) {
stack.push(top < ones ? top : ones);
}
return retval;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
public static void m
Looking at @rolfl's answer, I reasoned that with a stack data structure, we shouldn't need to use recursion, since recursion implicitly stores state in the call stack. I also tried to address @JeffVanzella's criticism about separation of concerns by converting the class into an iterator.
My solution ended up being a bit more monstrous than I had anticipated. It looks nothing like the elegant original, and runs more slowly too. Therefore, I suspect that a better iterative solution is possible.
```
import java.util.Iterator;
public class Partition implements Iterator {
/**
* Fixed-capacity stack of ints. As used in Partition.next(), the
* invariant is that elements towards the top of the stack are never
* larger than elements underneath. (In other words, the array
* elements are nonincreasing.
*/
private static class IntStack {
private int[] data;
private int size;
IntStack(int capacity) {
this.data = new int[capacity];
this.size = 0;
}
public void push(int datum) {
this.data[this.size++] = datum;
}
public int pop() {
return this.data[--this.size];
}
public boolean isEmpty() {
return this.size == 0;
}
/**
* Returns the elements as a space-delimited string.
*/
public String toString() {
// toString() of an empty stack is never used in practice...
if (this.isEmpty()) return "";
StringBuilder sb = new StringBuilder(String.valueOf(this.data[0]));
for (int i = 1; i 0; ones -= top) {
stack.push(top < ones ? top : ones);
}
return retval;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
public static void m
Solution
I am not sure how to 'review' your code in this case.... I have a sense of 'competition' here, and the moment performance enters the equation, there are things I just know are going to be slower, but I cannot always explain why.....
I think often times it simply comes down to primitives vs. Object creation.... whenever that happens things slow down.
I have put together a 'competing' solution, and it uses tricks I have learned over the years... tricks I feel, for the most part, lead to 'fast' code. I have been accused of 'premature optimization' when I do these things, but, it tends to work for me.... ;-)
printing Strings is never going to be a good measure of performance, so I have taken three solutions: the recursive solution I suggested in the earlier post. Your solution using the iterator, and then a 'competing' iterator performance.
So, in my benchmarks, this iterative process is about 5 times faster than yours.... (excluding the System.out.println()):
here are my results (times in milliseconds on my machine):
Edit:
New results ... note, 200_success is also running faster here....
Hate performance variances ... probably a Windows/Intel CPU frequency thing.
Main class:
Your solution is above (I have left it called 'Partition').
Then my iterative solution is...
EDIT:
I have edited my solution to add comments. As I was adding the comments I realized that a lot of the logic in the advance() method was related to setup of the system.
I have moved the setup to the constructor, and by verifying a couple of things, I am now able to guarantee a couple of behavioral advantages that mean I don't need a few of the loops in the system. I have updated my results now as well.
```
package comp;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter implements Iterator {
private final int[] stack;
private final int[] outpos;
private final StringBuilder outstring;
private final int limit;
private boolean hasnext = true;
private int spos = 0;
public PartitionRLIter(int n) {
if (n <= 0) throw new IllegalArgumentException();
limit = n;
stack = new int[limit];
outpos = new int[limit];
// NOTE THAT THE CONSTRUCTOR NOW MANUALLY INITIALIZES THE SYSTEM
outstring = new StringBuilder(limit * 2); // worst case is "1 1 1 1 1 ...";
Arrays.fill(stack, 1);
for (int i = 0; i < limit; i++) {
outpos[i] = outstring.length();
o
I think often times it simply comes down to primitives vs. Object creation.... whenever that happens things slow down.
I have put together a 'competing' solution, and it uses tricks I have learned over the years... tricks I feel, for the most part, lead to 'fast' code. I have been accused of 'premature optimization' when I do these things, but, it tends to work for me.... ;-)
printing Strings is never going to be a good measure of performance, so I have taken three solutions: the recursive solution I suggested in the earlier post. Your solution using the iterator, and then a 'competing' iterator performance.
So, in my benchmarks, this iterative process is about 5 times faster than yours.... (excluding the System.out.println()):
here are my results (times in milliseconds on my machine):
200_Success=2045.091 rolflIter=446.846=rolflRecur 2046.462011
200_Success=1737.469 rolflIter=573.900=rolflRecur 1521.951070
200_Success=1814.468 rolflIter=385.520=rolflRecur 1499.896568
200_Success=1714.592 rolflIter=333.105=rolflRecur 1372.042103
200_Success=1799.969 rolflIter=383.033=rolflRecur 1520.779467
200_Success=1676.415 rolflIter=336.651=rolflRecur 1474.669545
200_Success=1978.581 rolflIter=407.804=rolflRecur 1417.124248
200_Success=1665.783 rolflIter=343.939=rolflRecur 1375.178203
200_Success=1654.083 rolflIter=331.607=rolflRecur 1369.912767
200_Success=1654.958 rolflIter=339.234=rolflRecur 1369.170302Edit:
New results ... note, 200_success is also running faster here....
Hate performance variances ... probably a Windows/Intel CPU frequency thing.
200_Success=1463.484 rolflIter=624.754 rolflRecur=1777.548864
200_Success=1304.401 rolflIter=302.086 rolflRecur=1492.951479
200_Success=1577.132 rolflIter=367.537 rolflRecur=1485.176134
200_Success=1230.959 rolflIter=266.068 rolflRecur=1389.742206
200_Success=1230.445 rolflIter=269.587 rolflRecur=1382.473980
200_Success=1220.637 rolflIter=269.352 rolflRecur=1376.292369
200_Success=1204.206 rolflIter=266.920 rolflRecur=1369.920239
200_Success=1201.280 rolflIter=264.481 rolflRecur=1365.711999
200_Success=1204.419 rolflIter=262.047 rolflRecur=1368.854637
200_Success=1251.656 rolflIter=264.030 rolflRecur=1416.935596Main class:
package comp;
import java.util.Iterator;
public class RunParts {
private static int charsIn(Iterator iter) {
int chars = 0;
while (iter.hasNext()) {
chars += iter.next().length();
}
return chars;
}
public static void main(String[] args) {
final int target = Integer.parseInt(args[0]);
long[] nanos = new long[3];
int[] charlen = new int[3];
for (int i = 0; i < 10; i++) {
System.gc();
nanos[0] = System.nanoTime();
charlen[0] = charsIn(new Partition(target));
nanos[0] = System.nanoTime() - nanos[0];
System.gc();
nanos[1] = System.nanoTime();
charlen[1] = charsIn(new PartitionRLIter(target));
nanos[1] = System.nanoTime() - nanos[1];
System.gc();
nanos[2] = System.nanoTime();
charlen[2] = PartitionRLRecur.partitionRL(target);
nanos[2] = System.nanoTime() - nanos[2];
System.out.printf("200_Success=%.3f rolflIter=%.3f rolflRecur=%3f\n",
nanos[0] / 1000000.0, nanos[1] / 1000000.0, nanos[2] / 1000000.0);
}
}
}Your solution is above (I have left it called 'Partition').
Then my iterative solution is...
EDIT:
I have edited my solution to add comments. As I was adding the comments I realized that a lot of the logic in the advance() method was related to setup of the system.
I have moved the setup to the constructor, and by verifying a couple of things, I am now able to guarantee a couple of behavioral advantages that mean I don't need a few of the loops in the system. I have updated my results now as well.
```
package comp;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter implements Iterator {
private final int[] stack;
private final int[] outpos;
private final StringBuilder outstring;
private final int limit;
private boolean hasnext = true;
private int spos = 0;
public PartitionRLIter(int n) {
if (n <= 0) throw new IllegalArgumentException();
limit = n;
stack = new int[limit];
outpos = new int[limit];
// NOTE THAT THE CONSTRUCTOR NOW MANUALLY INITIALIZES THE SYSTEM
outstring = new StringBuilder(limit * 2); // worst case is "1 1 1 1 1 ...";
Arrays.fill(stack, 1);
for (int i = 0; i < limit; i++) {
outpos[i] = outstring.length();
o
Code Snippets
200_Success=2045.091 rolflIter=446.846=rolflRecur 2046.462011
200_Success=1737.469 rolflIter=573.900=rolflRecur 1521.951070
200_Success=1814.468 rolflIter=385.520=rolflRecur 1499.896568
200_Success=1714.592 rolflIter=333.105=rolflRecur 1372.042103
200_Success=1799.969 rolflIter=383.033=rolflRecur 1520.779467
200_Success=1676.415 rolflIter=336.651=rolflRecur 1474.669545
200_Success=1978.581 rolflIter=407.804=rolflRecur 1417.124248
200_Success=1665.783 rolflIter=343.939=rolflRecur 1375.178203
200_Success=1654.083 rolflIter=331.607=rolflRecur 1369.912767
200_Success=1654.958 rolflIter=339.234=rolflRecur 1369.170302200_Success=1463.484 rolflIter=624.754 rolflRecur=1777.548864
200_Success=1304.401 rolflIter=302.086 rolflRecur=1492.951479
200_Success=1577.132 rolflIter=367.537 rolflRecur=1485.176134
200_Success=1230.959 rolflIter=266.068 rolflRecur=1389.742206
200_Success=1230.445 rolflIter=269.587 rolflRecur=1382.473980
200_Success=1220.637 rolflIter=269.352 rolflRecur=1376.292369
200_Success=1204.206 rolflIter=266.920 rolflRecur=1369.920239
200_Success=1201.280 rolflIter=264.481 rolflRecur=1365.711999
200_Success=1204.419 rolflIter=262.047 rolflRecur=1368.854637
200_Success=1251.656 rolflIter=264.030 rolflRecur=1416.935596package comp;
import java.util.Iterator;
public class RunParts {
private static int charsIn(Iterator<String> iter) {
int chars = 0;
while (iter.hasNext()) {
chars += iter.next().length();
}
return chars;
}
public static void main(String[] args) {
final int target = Integer.parseInt(args[0]);
long[] nanos = new long[3];
int[] charlen = new int[3];
for (int i = 0; i < 10; i++) {
System.gc();
nanos[0] = System.nanoTime();
charlen[0] = charsIn(new Partition(target));
nanos[0] = System.nanoTime() - nanos[0];
System.gc();
nanos[1] = System.nanoTime();
charlen[1] = charsIn(new PartitionRLIter(target));
nanos[1] = System.nanoTime() - nanos[1];
System.gc();
nanos[2] = System.nanoTime();
charlen[2] = PartitionRLRecur.partitionRL(target);
nanos[2] = System.nanoTime() - nanos[2];
System.out.printf("200_Success=%.3f rolflIter=%.3f rolflRecur=%3f\n",
nanos[0] / 1000000.0, nanos[1] / 1000000.0, nanos[2] / 1000000.0);
}
}
}package comp;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PartitionRLIter implements Iterator<String> {
private final int[] stack;
private final int[] outpos;
private final StringBuilder outstring;
private final int limit;
private boolean hasnext = true;
private int spos = 0;
public PartitionRLIter(int n) {
if (n <= 0) throw new IllegalArgumentException();
limit = n;
stack = new int[limit];
outpos = new int[limit];
// NOTE THAT THE CONSTRUCTOR NOW MANUALLY INITIALIZES THE SYSTEM
outstring = new StringBuilder(limit * 2); // worst case is "1 1 1 1 1 ...";
Arrays.fill(stack, 1);
for (int i = 0; i < limit; i++) {
outpos[i] = outstring.length();
outstring.append("1 ");
}
hasnext = true;
spos = limit - 1;
}
@Override
public boolean hasNext() {
return hasnext;
}
@Override
public String next() {
if (!hasnext)
throw new NoSuchElementException();
try {
return outstring.substring(0, outstring.length() - 1);
} finally {
hasnext = advance();
}
}
private final boolean advance() {
// advance() keeps four 'stack-like' variables in sync
// advance() will only ever be called when the current system has a valid answer
//
// **stack** contains the digits that get summed... It is the 'real stack'. The constructor initializes it to all 1's.
//
// **spos** is our depth in the stack.
//
// the **outstring** is a StringBuilder that is kept in sync with the actual stack...
// reusing the StringBuilder makes it much faster... but we need to manage it like a stack.
// when you go deeper in the stack, the outstring has values added to it,
// when you come back up, the outstring is truncated to remove unneeded characters.
// very much like push and pop operations (except at the end of the string, not the front)
//
// the **outpos** is the array of integer positions in the outstring StringBuffer that
// keeps track of where the outstring should be truncated at each level.
// this is what allows working push/pop on the outstring.
//
// back up..... the stack, we always know we are already at the limit.
// pop the value off (keep sum in sync).
int sum = limit - stack[spos];
if (--spos < 0) {
// we ran out of things to do, there's no more possibilities.
return false;
}
// on the previous level, we increment....
// we can never overflow the previous level because
// of the way the math works (we would not have a next level if we can't increment this one).
stack[spos] ++;
sum++;
// pop the previous vpackage comp;
public class PartitionRLRecur {
public static int partitionRL(final int n)
{
return recursivePartition(n, 1, new int[n], 0);
}
private static int recursivePartition(final int target, final int from, final int[] stack, final int stacksize)
{
if(target == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < stacksize; i++) {
sb.append(stack[i]).append(" ");
}
// System.out.println(sb.toString());
// );
return sb.toString().length();
}
int sz = 0;
for(int i = from; i <= target; i++) {
stack[stacksize] = i;
sz += recursivePartition(target-i, i, stack, stacksize + 1);
}
return sz;
}
}Context
StackExchange Code Review Q#36815, answer score: 6
Revisions (0)
No revisions yet.