[Home]CodeSnippets/DeepRecursion

Robo Home | CodeSnippets | Changes | Preferences | AllPages

Showing revision 10
Beautiful.
for (int i = 0; i < data.length; i++) {
	for (int ii = 0; ii < data[i].length; ii++) {
		for (int iii = 0; iii < data[i][ii].length; iii++) {
			for (int iv = 0; iv < data[i][ii][iii].length; iv++) {
				for (int v = 0; v < data[i][ii][iii][iv].length; v++) {
					for (int vi = 0; vi < data[i][ii][iii][iv][v].length; vi++) {
						for (int vii = 0; vii < data[i][ii][iii][iv][v][vi].length; vii++) {
							for (int iix = 0; iix < data[i][ii][iii][iv][v][vi][vii].length; iix++) {
								for (int ix = 0; ix < data[i][ii][iii][iv][v][vi][vii][iix].length; ix++) {
									for (int x = 0; x < data[i][ii][iii][iv][v][vi][vii][iix][ix].length; x++) {
										for (int xi = 0; xi < data[i][ii][iii][iv][v][vi][vii][iix][ix][x].length; xi++) {
											data[i][ii][iii][iv][v][vi][vii][iix][ix][x][xi] = 1.0F;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
}
-- David Alves

Nice variable names! =) I have lots of that kind of loops in earlier bots. I have always kept thinking there must be a much more generic way of doing it. Like recursing down the dimensions or something. I have never succeeded in doing it though. Always get stuck on some illegal cast issue and the like. -- PEZ

You could use recursion with Array.get(). I like this better though. :-) --David Alves

I think I like this better:

import java.lang.reflect.*;

class ArrayFill {
    static float[][][][][][][][][][][] data = new float[3][3][3][3][3][3][3][3][3][3][3];

    public static void main(String args[]) {
	long bins = 0;
	bins = FillRecursive(data, 1.0F);
	System.out.println(bins + " bins filled");
    }

    static long FillRecursive(Object o, float v) {
	long bins = 0;
	if (o.getClass().getComponentType() != Float.TYPE) {
	    for (int i = 0; i < Array.getLength(o); i++) {
		bins += FillRecursive(Array.get(o, i), v);
	    }
	}
	else {
	    for (int i = 0; i < Array.getLength(o); i++) {
		Array.setFloat(o, i, v);
		bins++;
	    }
	}
	return bins;
    }
}
Since I often change my mind about segmentation and stuff.

Note that this example includes usage and reporting. To just do the filling this is the gist:

    static void FillRecursive(Object o, float v) {
	if (o.getClass().getComponentType() != Float.TYPE) {
	    for (int i = 0; i < Array.getLength(o); i++) {
		FillRecursive(Array.get(o, i), v);
	    }
	}
	else {
	    for (int i = 0; i < Array.getLength(o); i++) {
		Array.setFloat(o, i, v);
	    }
	}
    }
-- PEZ

I've done similar stuff to this in FloodGrapher, but it has alway looked more like this:

	static void fillRecursive(Object o, float v)
	{
		if (o instanceof float[])
			for (int i=0; i<((float[])o).length; i++)
				((float[])o)[i] = v;
		else
			for (int i=0; i<((Object[])o).length; i++)
				fillRecursive(((Object[])o)[i], v);
	}
-- Kawigi

Your code might be efficient, but where's the entertainment value? :-)

Kawigi, does your snippet work? Always when I've tried something like that I've got illegal cast errors. -- PEZ

i do it like this:

  public interface Action<T,R>
  {
    public R forThis(T t);
  }

  public static final void forEach(Object[] o, Action a)
  {
    for (int i = o.length; --i >= 0;)
    {
      Object o1 = o[i];
      if (o1 instanceof Object[])
      {
        forEach((Object[]) o1, a);
      } else {
        o[i] = a.forThis(o1);
      }
    }
  }

every Object[][][]...... is an Object[], so i can traverse the levels. in action, it looks like:

    CollectionUtils?.forEach(segments, new CollectionUtils?.Action<Segment,Segment>()
    {
      public Segment forThis(Segment segment)
      {
        return new Segment();
      }
    });
for the filling. segments is currently a Segment[][], but could be much deeper.


You could just use a big one dimensional array of floats, and then use a function to get the index. i.e. instead of float deepArray[3][3][3] use:

float flatArray[3*3*3]; int getIndex(int a, int b, int c) {

  return a*3*3+b*3+c;
}

This is almost certainly faster and more efficient, especially if your nesting is that deep.

~Pog

I'm not sure that would be faster. I would expect most compilers to emit bytecode that does exactly the same. -- Dummy

Multi-dimensional Java arrays aren't one long 1D array, but an array of the first dimension containing pointers to arrays of the second dimension, which in turn contain pointers to arrays of the third dimension, etc. I think you could even replace them with something of a completely different type. Anyway, it results in a whole lot of memory accesses. -- Jonathan (noticed this in my inbox)

Ah, I see why they do that. I guess it is necessary when the arrays in the 2nd dimension (or 3rd, 4th...) are not all the same size. (e.g. array[0][] = new int[5]; array[1][] = new int[8];) On the other hand, it shouldn't be too hard for compilers to recognize declarations like in Pog's example and create a 1D array anyway. Aw, well. I'm not exactly a compiler expert. --Dummy

I think you overestimate the power of the compiler - it might (at best) unroll the loops. Java has to bounds-check each seperate level of access, for example, making it highly improbable the compiler would optimise out the nesting, and in addition meaning that the super-nested version at the top of this discussion needs to do 10 array bounds checks for every element access! ~Pog

Sorry, my bad. I didn't realize that you meant it as an optimization to the code on top of this page with all the for loops :-p. I was only comparing flatarray[a*9+b*3+c] to deepArray[a][b][c]. I'm fairly certain that multidimensional arrays are allocated in one big 1D array in C (I could be wrong), so that's why I thought it should be possible in JAVA as well. :-p --Dummy


Robo Home | CodeSnippets | Changes | Preferences | AllPages
Edit revision 10 of this page | View other revisions | View current revision
Edited July 29, 2006 11:37 EST by Dummy (diff)
Search: