Page 1 of 2 12 LastLast
Results 1 to 20 of 24
Like Tree1Likes

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

  1. #1
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

    Lightbulb 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.

    Java 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?

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

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

    here you go>

    Java 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]

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

    Default 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:

    Java 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:

    Java 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:

    Java Code:
    int[] index= new int[matrix.length];
    
    do {
       process(comb(index, matrix);
    }
    while (next(index, matrix);
    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

    Default 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.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,329
    Rep Power
    5

    Default 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.

    Java 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
    Last edited by jim829; 08-28-2013 at 05:57 PM.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  8. #8
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

    Default 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.
    gimbal2 likes this.

  9. #9
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,329
    Rep Power
    5

    Default 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
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  10. #10
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

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

    Quote Originally Posted by Daedalus View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,188
    Rep Power
    19

    Default 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 ...
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

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

    Quote Originally Posted by DarrylBurke View Post
    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 ;-)
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,590
    Rep Power
    5

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

    Quote Originally Posted by Daedalus View Post
    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.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  14. #14
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,329
    Rep Power
    5

    Default 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
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  15. #15
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

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

    Quote Originally Posted by jim829 View Post
    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 ;-)
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

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

    Quote Originally Posted by gimbal2 View Post
    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.

  17. #17
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,329
    Rep Power
    5

    Default 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.

    Java 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
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  18. #18
    Daedalus is offline Member
    Join Date
    Sep 2008
    Posts
    14
    Rep Power
    0

    Default 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.

  19. #19
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,329
    Rep Power
    5

    Default 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
    Last edited by jim829; 08-30-2013 at 04:16 AM.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  20. #20
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,305
    Blog Entries
    7
    Rep Power
    20

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

    Quote Originally Posted by Daedalus View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

Page 1 of 2 12 LastLast

Similar Threads

  1. Recursive method to sort array
    By artur in forum New To Java
    Replies: 2
    Last Post: 03-19-2012, 12:49 PM
  2. Replies: 8
    Last Post: 01-15-2011, 09:39 PM
  3. Array out of bound- Recursive Method
    By hpayandah in forum New To Java
    Replies: 2
    Last Post: 11-12-2010, 08:02 PM
  4. Recursive method using int array, help needed
    By chupalo17 in forum New To Java
    Replies: 4
    Last Post: 09-07-2009, 11:15 PM
  5. Replies: 1
    Last Post: 02-16-2008, 09:10 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •