optimise recursive method that prints all possible rows in a 2D array

Hi, I have a method below that takes an int[][] array (column,row) and creates a new int[] array for every possible combination of rows in the grid, this method works even if the column lengths are different.

The problem is that It creates too much garbage for the GC when using a big grid due to the creation of new array Objects inside each loop of each recursion. I would like to dispense with the "new TIntArrayList" but I don't know how to do it without ruining the logic of the method. Ideally I would like to change the method so it uses only loops instead of recursion to eliminate the method call overhead as I don't think the VM is inlineing the compiled code.

Code:

` public static void AllRowCombinations(int[][] grid, int column, TIntArrayList aRow, ArrayList<int[]> finalRows) {`

if (column > grid.length - 1) {

finalRows.add(aRow.toArray());

return;

}

for (int k : grid[column]) {

TIntArrayList row = new TIntArrayList(aRow.toArray());

row.add(k);

AllRowCombinations(grid, column + 1, row,finalRows);

}

}

Any ideas?

Re: optimise recursive method that prints all possible rows in a 2D array

Can you give an example (a small matrix and its result)?

kind regards,

Jos

Re: optimise recursive method that prints all possible rows in a 2D array

here you go>

Code:

`int[][] grid = new int[][]{{1,2,3},{4,5},{6,7,8}};`

ArrayList<int[]> result = new ArrayList<>();

AllRowCombinations(grid,0,new TIntArrayList(),result);

for(int[] ary : result) System.out.println(Arrays.toString(ary));

produces>

[1, 4, 6]

[1, 4, 7]

[1, 4, 8]

[1, 5, 6]

[1, 5, 7]

[1, 5, 8]

[2, 4, 6]

[2, 4, 7]

[2, 4, 8]

[2, 5, 6]

[2, 5, 7]

[2, 5, 8]

[3, 4, 6]

[3, 4, 7]

[3, 4, 8]

[3, 5, 6]

[3, 5, 7]

[3, 5, 8]

Re: optimise recursive method that prints all possible rows in a 2D array

Yes, it can be done iteratively; a few observations; if the original matrix has n rows, each combination has n elements. Have another array ready with n elements, where each element is a column index in a row of the original matrix. Obviously element i of that other matrix has to be in the range [0, m) where m is the length of the corresponding row in the original matrix. This is how one combination is generated:

Code:

`int[] comb(int[] index, int[][] matrix) {`

int[] c= new int[index.length];

for (i= 0; i < index.length; i++)

c[i]= matrix[i][index[i]];

return c;

}

The method above stores the corresponding elements of each row of the matrix in array c. The next method updates array index so that it contains the column indexes of the next combination:

Code:

`boolean next(int[] index, int[][] matrix) {`

for (int i= index.length ; i-- > 0)

if (++index[i] >= matri[i].length)

index[i]= 0;

else

return true;

return false;

}

Using the two method together, you can generate/process all combinations:

Code:

`int[] index= new int[matrix.length];`

do {

process(comb(index, matrix);

}

while (next(index, matrix);

kind regards,

Jos

Re: optimise recursive method that prints all possible rows in a 2D array

Thanks, jos, the code works a treat. Its much faster than the recursive version and the garbage collector hardly ever runs, thanks again.

Re: optimise recursive method that prints all possible rows in a 2D array

You're welcome of course; you can even do better than my implementation if you don't want to keep all those combinations (just print them or process them once). My comb( ... ) method builds a new array 'c' each time it is called (where the combination is stored). You could also pass in an array for the storage and use it over and over again.

kind regards,

Jos

Re: optimise recursive method that prints all possible rows in a 2D array

Here was my approach. Parts are similar to Jos' (no insult intended). I wrote down the required indices on paper and saw a pattern and then tried to produce the pattern.

Code:

`public class Combo {`

public static void main(String... args) {

int [][] g = {{1,2,3},{4,5},{6,7,8}};

int n = 1;

for (int j = 0; j < g.length; j++) {

n *= g[j].length;

}

int i[] = new int[g.length];

for (int k = 0; k < n; k++) {

for (int rr = 0; rr < g.length; rr++) {

System.out.print(g[rr][i[rr]] + " ");

}

System.out.println();

i[g.length-1]++;

for (int j = g.length-1; j > 0; j--) {

if (i[j] >= g[j].length) {

i[j] = 0;

i[j - 1]++;

} else

break;

}

}

}

}

Edit: I looked at this some more and it can be made cleaner with some while loops (and probably more efficient with other changes).

Regards,

Jim

Re: optimise recursive method that prints all possible rows in a 2D array

Thanks for the input jim.

I tested both of your algorithms on a 7x16 matrix producing 260 million rows. The jos version takes 39.794 seconds and jims version takes 40.193 seconds (on one core @ 4.2Ghz) so they are the same pretty much.

I recon the additional loop in jims version adds a tiny bit of overhead and the VM seems to be inlineing the two methods of joses version which would eliminate the method call overhead but i'm nit picking really.

Both versions are at least twice as fast as my initial recursive version, which is mostly due to not needing to create new objects for each element.

Thank you for both for your contributions they are most welcome.

Re: optimise recursive method that prints all possible rows in a 2D array

Yeah! I went back to this just after I posted it and eliminated my initial loop of creating n. It isn't needed. So lines 4 thru 7 can be eliminatated. Actually I couldn't figure a real way to implement recursion for this. I had to pass references so nothing was really saved on the stack. So my recursive algorithm was more or less nothing but a loop.

Regards,

Jim

Re: optimise recursive method that prints all possible rows in a 2D array

Quote:

Originally Posted by

**Daedalus** Thanks for the input jim.

The jos version takes 39.794 seconds and jims version takes 40.193 seconds

Yeah! <does the victory dance/> Jos (the hare) versus Jim (the turtle) ;-)

kind regards,

Jos

Re: optimise recursive method that prints all possible rows in a 2D array

Add the 0.4 seconds it takes Jos to down a Grolsch and Jim's version is faster ...

Re: optimise recursive method that prints all possible rows in a 2D array

Quote:

Originally Posted by

**DarrylBurke** Add the 0.4 seconds it takes Jos to down a Grolsch and Jim's version is faster ...

Did you put your money on the wrong party? <does the happy dance/>

kind regards,

Jos ;-)

Re: optimise recursive method that prints all possible rows in a 2D array

Quote:

Originally Posted by

**Daedalus** I tested both of your algorithms on a 7x16 matrix producing 260 million rows. The jos version takes 39.794 seconds and jims version takes 40.193 seconds (on one core @ 4.2Ghz) so they are the same pretty much.

260 millions rows - impressively complete test as this certainly accounts for JVM warmup. Usually when you do a performance test, you should let Java perform the same code multiple times in the same JVM instance so hotspot/JIT gets to kick in.

Re: optimise recursive method that prints all possible rows in a 2D array

And subtract .7 seconds for the fact the Jos probably wrote it in a stupor and he still wins!

Regards,

Jim

Re: optimise recursive method that prints all possible rows in a 2D array

Quote:

Originally Posted by

**jim829** And subtract .7 seconds for the fact the Jos probably wrote it in a stupor and he still wins!

My stupors are worth much more than that; I'd say an hour and a half or so ...

kind regards,

Jos ;-)

Re: optimise recursive method that prints all possible rows in a 2D array

Quote:

Originally Posted by

**gimbal2** 260 millions rows - impressively complete test as this certainly accounts for JVM warmup. Usually when you do a performance test, you should let Java perform the same code multiple times in the same JVM instance so hotspot/JIT gets to kick in.

The problem is not the warm up but the GC pauses and heap reSizes. I set java to use 20GB of heap from the start with the xms flag to stop the reSizes but It will still do a collection of the young generation (stops the world and clears the cpus L2 cache) a few times even when its only using 5gb of the 20GB heap which is not something you can control. 260 million int[7] arrays is about 30 bytes per int[7] for a total of 7.8GB not including the ArrayList<int[]> with 265 million elements.

On my first try I forgot to give the arrayList 265 million elements at creation time resulting in twice the run time, just shows how inefficient the arrayList reSize operation is.

What strikes me as funny is that the algorithms of jos and jims to create every combination of rows in a matrix is much more elegant than the somewhat simpler task i'm now faced with, which is creating every combination of values from a single int[] array (each unique row from the matrix). I've seen impementations of the Steinhaus–Johnson–Trotter algorithm which is most commonly use for this task but they are not very compact to say the least.

eg, PermutationUtils xref

Maybe the approach that jos used by having an index array and then modifying the index Array separately to the main loop might be quicker than the Steinhaus–Johnson–Trotter algorithm but I haven't got round to testing it yet.

Re: optimise recursive method that prints all possible rows in a 2D array

If your interested, here is my final version. I documented the changes with explanations.

Code:

`private static List<int[]> toRows(int[][] g) {`

int i[] = new int[g.length];

List<int[]> list = new ArrayList<>();

/**

In stead of calculating max number of entries, just loop until the first index exceeds number of "rows" of supplied

matrix

*/

while (i[0] < g.length) {

int[] v = new int[g.length];

for (int rr = 0; rr < g.length; rr++) {

v[rr] = g[rr][i[rr]];

}

list.add(v);

int j = g.length - 1;

i[j]++;

/**

Earlier for loop with break is basically a while loop

*/

while (j > 0 && i[j] >= g[j].length) {

i[j] = 0;

i[--j]++;

}

}

return list;

}

I also added a List to return the one-D arrays. This could quickly eat up storage for large matrices. I have no idea how this performs but I believe the changes make it easier to understand.

Regards,

Jim

Re: optimise recursive method that prints all possible rows in a 2D array

thanks again jim, it certainly makes it easier to read and it might be a bit faster without that loop.

Re: optimise recursive method that prints all possible rows in a 2D array

Well, nuts! I thought I did the boundary case testing but my second "improved" version seems to have problems. My first one is better (takes care of null lists and other poorly formed matrices because they are 0 length and no iteration will happen). I just read an article about "optimizing" ones code. It goes something like this. Don't optimize! Unless you are sure of your solution. And then don't optimize. I clearly violated that tenet.

Note to self: leave well enough alone!

Regards,

Jim

Re: optimise recursive method that prints all possible rows in a 2D array

Quote:

Originally Posted by

**Daedalus** What strikes me as funny is that the algorithms of jos and jims to create every combination of rows in a matrix is much more elegant than the somewhat simpler task i'm now faced with, which is creating every combination of values from a single int[] array (each unique row from the matrix). I've seen impementations of the Steinhaus–Johnson–Trotter algorithm which is most commonly use for this task but they are not very compact to say the least.

eg,

PermutationUtils xref

That stuff is about permutations, not combinations. The particular algoarithm generates permutations by swapping adjacent elements (only two of them) for each permutation. If you're interested, I can give you a much shorter iterative algorithm that also generates all permutations (no additional storage needs, just one method boolean nextPermutation(int[] perm);)

kind regards,

Jos