Dynamic array of unknown number of dimensions

This is a discussion on Dynamic array of unknown number of dimensions within the C Programming forums, part of the General Programming Boards category; Edit: Can a mod please rename this thread to "dynamic array of unknown number of dimensions?" the autofill suggestion popped ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    3

    Dynamic array of unknown number of dimensions

    Edit:
    Can a mod please rename this thread to "dynamic array of unknown number of dimensions?"
    the autofill suggestion popped up, and pressing enter posted the thread instead of selecting the text to autofill


    Hi.

    I'm working on engineering calculations, which involve hundreds of functions, some of which are called a million times or more.

    To speed things up, I wrote a function that would keep track of all argument values a particular function receives, and store them into an array to fetch if those arguments come up again.

    To be able to use this precalculation function in any other function regardless of number of arguments, I wanted it to accept a generic double* pointer for the array of precalculated values, because that array will have as many dimensions as there are arguments to the function we're optimizing. It would then be dereferenced an appropriate number of times.



    Example of how I would optimize a 3-argument function:

    Code:
    double f_T_tipspivot (double p, double theta_slide, double w) {
    	double f () {
    		original function body goes here
    		most of these are very expensive to recalculate, like integration or equation solvers (and terms depend on 50 other functions)
    	}
    
    	double res;			// result
    	double args[3] = {p, theta_slide, w};
    	static int nargs[3] = {0};	// number of different values received for each argument
    	static double **argarr;		// 2-d array to store collected argument values
    	static double ***ooo;		// 3-d array to store results
    	static int once = 0;
    	if (once == 0) {
    		argarr = malloc(3*sizeof(double*));
    		argarr[0] = malloc(sizeof(double));	// store values for argument p
    		argarr[1] = malloc(sizeof(double));	// 			                theta_slide
    		argarr[2] = malloc(sizeof(double));	//			                w
    		// for oo array, have to malloc a pointer to pointer for each dimension except last, and malloc the last array with one double (for the value oo[[0][0][0]...)
    		ooo = malloc(sizeof(double*));
    		ooo[0] = malloc(sizeof(double*));
    		ooo[0][0] = malloc(sizeof(double));
    		ooo[0][0][0] = NAN;						
    		once = 1;
    	}
    	optany (&f, &res, __func__, 3, args, nargs, &argarr, (double******)&ooo);
    	return res;
    }

    Here's the relevant code from the optimization function, "optany", where I'm trying to dynamically allocate the oo array.

    Code:
    void optany (double (*f)(), double *res, const char *caller, int n, double *args, int *nargs, double ***argarr, double ******oo) {
    
    	// return pointer to result array location with given indeces
    	// lim -> how many dereferencing operations will be performed (how many indeces to "unwrap")
    		// if n (number of dimensions) is passed, we get pointer to value oo[index1][index2]...[index_n]
    		// anything less, and we get a pointer to array (of values in last dimension if lim = n - 1), or to array of pointers to arrays of values in last dimension, and so forth
    	double *ooval (int *indeces, int lim) {
    		int m;
    		double **curadd = (double**) *oo;	// curadd has to be a lvl2 pointer because we dereference it later and store it into itself after some address arithmetic... and dereferencing a lvl1 pointer would produce a double which we couldn't store into curadd (nor could we cast a double to double*)
    		
    		for (m=0; m < lim; m++) {
    			if (m == n-1) {	// if unwrapping last index
    				curadd = curadd + indeces[m]*(int)(((double)sizeof(double)/sizeof(double*)));	// fetching the double value stored at full set of indeces...
    			}
    			else {
    				curadd = (double**) *(curadd + indeces[m]);
    			}
    		}
    		
    		return (double*) curadd;
    	}
    	// get value from the address found above
    	double getooval (int *indeces, int lim) {
    		return * (ooval (indeces, lim));
    	}
    	// store value to that address
    	void setooval (int *indeces, int lim, double val) {
    		*(ooval(indeces, lim)) = val;
    	}
    
    
    	// int inc[n] -> those are set before this part, equal to 1 if that argument value is new (and this dimension needs to be incremented), 0 if not
    	// used in dynamic allocation... if a higher dimension was incremented, we need to malloc all of the lower dimensions at that index
    	// k always > 0
    	void go_down (int k) {
    		int l;
    		int start = 0;
    		// if we're just one dimension below the one that was incremented, only need to malloc at that new index
    		if (inc[k-1] == 1) {
    			start = nargs[k-1] - 1;
    		}
    		// otherwise, need to malloc at [new index of incremented dimension][ALL INDECES OF THIS LOWER DIMENSION][ALL INDECES]...
    		for (l=start; l<nargs[k-1]; l++) {
    			indeces[k-1] = l;
    			if (k != n-1) {
    				//*((double**)ooval(indeces,k-1)) = malloc(nargs[k]*sizeof(double*));
    				
    				if (k == 1) {
    					*(*oo+indeces[0]) = malloc(nargs[k]*sizeof(double*));
    				}
    				else if (k == 2) {
    					*(*(*oo + indeces[0]) + indeces[1]) = malloc(nargs[k]*sizeof(double*));
    				}
    				else if (k == 3) {
    					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = malloc(nargs[k]*sizeof(double*));
    				}
    				
    				go_down (k+1);
    			}
    			else {
    				//*((double**)ooval(indeces,k-1)) = malloc(nargs[k]*sizeof(double));
    				
    				// same as above, only mallocing as sizeof (double), not (double*)
    				if (k == 1) {
    					*(*oo + indeces[0]) = malloc(nargs[k]*sizeof(double));
    				}
    				else if (k == 2) {
    					*(*(*oo + indeces[0]) + indeces[1]) = malloc(nargs[k]*sizeof(double));
    				}
    				else if (k == 3) {
    					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = malloc(nargs[k]*sizeof(double));
    				}
    				else if (k == 4) {
    					*(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) + indeces[3]) = malloc(nargs[k]*sizeof(double));
    				}
    				
    				for (o=0; o<nargs[k]; o++) {
    					indeces[k] = o;
    					setooval(indeces,k+1,NAN);
    				}
    			}
    		}
    	}
    	// used in dynamic allocation, if a dimension that's not last was incremented, will call go_down to create elements for all lower dimensions... otherwise, will realloc the last dimension
    	void loop (int k) {
    		int l;
    		
    		if (inc[k] == 1) {
    			if (k != n-1) {
    				//*((double**)ooval(indeces,k-1)) = realloc(ooval(indeces,k),nargs[k]*sizeof(double));
    				
    				if (k == 0) {
    					*oo = realloc(*oo,nargs[k]*sizeof(double*));
    				}
    				else if (k == 1) {
    					*(*oo + indeces[0]) = realloc(*(*oo + indeces[0]),nargs[k]*sizeof(double*));
    				}
    				else if (k == 2) {
    					*(*(*oo + indeces[0]) + indeces[1]) = realloc(*(*(*oo + indeces[0]) + indeces[1]),nargs[k]*sizeof(double*));
    				}
    				else if (k == 3) {
    					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = realloc(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]),nargs[k]*sizeof(double*));
    				}
    				
    				
    				indeces[k] = nargs[k] - 1;
    				go_down(k+1);
    			}
    			else {
    				//*((double**)ooval(indeces,k-1)) = realloc(ooval(indeces,k),nargs[k]*sizeof(double));
    					
    				if (k == 0) {
    					*oo = realloc(*oo,nargs[k]*sizeof(double));
    				}
    				else if (k == 1) {
    					*(*oo + indeces[0]) = realloc(*(*oo + indeces[0]),nargs[k]*sizeof(double));
    				}
    				else if (k == 2) {
    					*(*(*oo + indeces[0]) + indeces[1]) = realloc(*(*(*oo + indeces[0]) + indeces[1]),nargs[k]*sizeof(double));
    				}
    				else if (k == 3) {
    					*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) = realloc(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]),nargs[k]*sizeof(double));
    				}
    				else if (k == 4) {
    					*(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) + indeces[3]) = realloc(*(*(*(*(*oo + indeces[0]) + indeces[1]) + indeces[2]) + indeces[3]),nargs[k]*sizeof(double));
    				}
    				
    				
    				indeces[k] = nargs[k]-1;
    				setooval(indeces,k+1,NAN);
    			}
    		}
    		for (l=0; l < nargs[k]; l++) {
    			indeces[k] = l;
    			if (k != n-1) {
    				loop (k+1);
    			}
    		}
    	}
    
    	loop(0);
    
    
    
    }
    I'm trying to use dynamic allocation for the ooo array (the precalculated values), mainly to save my own time, because I want to insert this optimization function into many many other functions in many programs. So far I've found searching even through 2000 previous argument values on each call is still faster than recalculating the whole function. Also I'm aware that increasing array size by one every time a new argument value is encountered is not too efficient, but I'll worry about that later.

    Anyway, you can see in function loop and go_down a bunch of if statements that basically just do different number of dereferencing operations depending on k.
    *(address + index), or
    *(*(address + index1) + index2), and so forth

    However, I'm limited in number of dimensions to however many if statements I write.
    I tried returning the address of the pointer that I need to realloc with my function ooval, but of course the left side has to be an l-value.

    Then I tried this (commented out before each big block of if's):
    *((double**)ooval(indeces,k-1)) = malloc(nargs[k]*sizeof(double))
    which is supposed to replace all the if statements. However, that gave me the error you get when you try reallocing something that hasn't been malloced yet.
    (And I did have a separate if to handle the case of k=0 for the above call).

    I haven't been able to find what exactly they mean in the reference for realloc function when they say your pointer has to be a "Pointer to a memory block previously allocated with malloc, calloc or realloc". Apparently passing the address my pointer points to doesn't work if I obtain it from a function call.

    Does anyone know how I can replace these big if statements with something that would work for any number of dimensions?
    Last edited by gamask; 04-23-2011 at 02:28 PM.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why do you need more than 2 dimension? One dimension for the function, and one for the arguments to each function. Or maybe three, one for each different set of arguments passed to the function. I can't see why you would need an unknown number of arguments. You are basically just making an array of arguments, with the argument number unknown, that's fine, because you can have that dimension's length be dynamic.

    But why is it you think you need a 10D array exactly? I'm just not seeing it.

    Also, if any of your realloc calls fails, the way you are doing it now, you lose everything you have allocated. Never directly assign to the same pointer you are calling realloc on.

    So anyway, from where I sit, all you really need is a two or three D array. I can't figure out why you think you need an infinite number of dimensions.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    3
    Some of the functions that I want to apply this to have 5 arguments, so I need a 5d array for any combination of values that those arguments can take. I know that some of those arguments take on only a few different values, so it's not a problem to store, say, something like 100 * 100 * 50 * 10 * 3.


    Others have 4 arguments, others 3.

    I've already written the if statements for up to 5 dimensions, but I'd like to know if there's a cleaner way to do it.
    And why doesn't this work:

    int *a = malloc (sizeof(double));
    int *b = a;
    b = realloc (b, 2*sizeof(double));

    Why is this not the same as reallocing "a" directly? Does realloc care about variable names when establishing if something was allocated before?
    (This is essentially what I tried to do instead of the big if blocks, only b is returned by function ooval).


    And thanks for reminding me to check for what realloc returns. I usually leave things like that till the end if things work out while testing.
    Last edited by gamask; 04-23-2011 at 07:26 PM.

  4. #4
    Registered User
    Join Date
    Jun 2010
    Location
    In a house
    Posts
    15
    Why not just malloc an array to fit those values, as quzah said a more than two dimensional array just doesn't make much sense. In two dimensional array, one array have the function name as the key and link to an array for the function arguments.

    array 1................................................. .............. array 2
    ---------------------------------------------------
    |function name| pointer to argument values| -------->| 100 | 50 | 25 | 1 |
    ---------------------------------------------------
    |another name | pointer to argument values| -------->|2 | 3|
    ---------------------------------------------------
    .
    .
    .

    as a some what dynamic array, make the array 1 like a hundred starting size and if that ran out then malloc a new array like double the previous size of increase by a fixed size then copy the array 1 memory to the new array.

    Have you considered something like hashing or a tree style since you said that there are gonna be many functions that you want to store and access. Arrays are not very good.
    Last edited by tripleA; 04-23-2011 at 08:46 PM.

  5. #5
    Registered User
    Join Date
    Apr 2011
    Posts
    3
    Thanks for the input.

    I figured out my original problem of mallocing into an address returned from a function, it works, I was just doing it wrong.
    And I decided to scrap the whole "dynamic" thing, and instead I set some limits on dimensions, and if I get too many argument values, reset the whole thing.

    That works just fine in some cases. If argument values come in some sort of pattern, there's no need to retain the results for previous argument values which will not be used again later in the program.


    However, in other situations, like solving equations, the solver algorithms can call functions in the equation(s) with any argument values, and that's not really something I can control.
    In those cases, I want to hold on to all precalculated results because they are likely to be used again, I just don't know when and where.
    So a huge array would be beneficial.
    However, too huge, and we run out of RAM, and things get super slow with writing to disk.

    Any suggestions on where I could learn more about memory management?





    As for linked lists, I don't think that would work for me. How would I go about looking up the precalculated value for a 5-argument function, with each argument taking on 50 different values?
    That's 50^5 combinations that I need to store.

    @quzah - The optimization function "optany" receives an argument n for number of dimensions, equal to number of arguments that a given function takes. That can range from 1 to 5. I don't see how I could use a 2d array.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by gamask View Post
    @quzah - The optimization function "optany" receives an argument n for number of dimensions, equal to number of arguments that a given function takes.
    And returns what exactly?
    Quote Originally Posted by gamask View Post
    That can range from 1 to 5. I don't see how I could use a 2d array.
    Why?
    Quote Originally Posted by gamask View Post
    As for linked lists, I don't think that would work for me. How would I go about looking up the precalculated value for a 5-argument function, with each argument taking on 50 different values?
    That's 50^5 combinations that I need to store.
    Code:
    struct args
    {
        size_t argc;
        void **argv;
    
        struct args *next;
    } argtable[ numoffunctions ];
    No then, since I have no idea what it is your function is thinking it's returning, you get a list of void pointers to play with. If you actually knew what it was you were doing, you could tailor that to match each set of args. Now loop through it:
    Code:
    struct args *n;
    for( n = argtable[ functionindexbyname( "foo" ) ]; n; n = n->next )
        if( compargs( n ) == whateveritisithinkiwant )
            return n or whateveritisithinkiamtoreturn;
    return fail;
    You could also make that a crude hash table, or even just an array of lists arguments, 0 to 5, to speed up your search by 5.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding array dimensions
    By deviousdexter in forum C# Programming
    Replies: 3
    Last Post: 11-12-2008, 10:34 AM
  2. Set an array with unknown dimensions as global
    By paok in forum C Programming
    Replies: 11
    Last Post: 12-07-2007, 01:37 PM
  3. Structures and undifined array dimensions...
    By Tyrant in forum C Programming
    Replies: 24
    Last Post: 12-03-2007, 03:36 AM
  4. Array with user-defined dimensions
    By Jasel in forum C++ Programming
    Replies: 2
    Last Post: 11-02-2003, 09:58 AM
  5. Using variables for array dimensions
    By Leeman_s in forum C++ Programming
    Replies: 3
    Last Post: 05-16-2003, 07:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21