How Does One Sum Dimensions of an Array Specified at Run-Time?

Question

Hi all, I am working on a function to establish the entropy of a distribution. It uses a copula, if any are familiar with that. I need to sum up the values in the array based on which dimensions are "cared about."

Example: Consider the following example...

Dimension 0 (across)
_ _ _ _ _ _ _ _ _ _ _ _ _
|_ 0 _|_ 0 _|_ 0 _|_ 2 _|  Dimension 1
|_ 1 _|_ 0 _|_ 2 _|_ 0 _|   (down)
|_ 0 _|_ 3 _|_ 0 _|_ 6 _|
|_ 0 _|_ 0 _|_ 0 _|_ 0 _|

I "care about" dimension 0 only, and "don't care" about the rest (dim 1).
Summing this array with the above specifications will
"collapse" the "stacks" of dimension 1 down to a single 4 x 1 array:

_ _ _ _ _ _ _ _ _ _ _ _ _ 
|_ 1 _|_ 3 _|_ 2 _|_ 8 _|

This can then be summed, or have any operation performed.

I need to do this with an array of 'n' dimensions, which could feasibly be 20. Also, I need to be able to do this, caring about certain dimensions, and collapsing the rest. I am having an especially hard time with this because I cant visualize 20 dimensions :p . If anyone could help me set up some c/c++ code to collapse/sum, I would be very very grateful.

Answer 1

Actually, by colllapsing the colums you already summed them, so the dimension doesn't matter at all for your example. Did I miss something or did you?

Answer 2

I need help collapsing them when I dont know how many there are :p I guess i wasn't clear enough, heh

Answer 3

I think the best thing to do here would be one/both of two things:

1. Rethink the design, if its too complex, find a less-complex way.
2. Stop trying to visualise it.. :P Just store the dimensions in question that you need to sum, then do them one at a time. Once you have the base code, then look at improving the efficiency of your algorithm.

Answer 4

Unfortunately there isnt really a simpler way to do this.

Answer 5

I beg to differ, there is ALWAYS another way..

And if you really cannot refactor, then you need to break the problem down into smaller parts.. Like I said, establish which dimensions you need to sum, then hit them one at a time..

Also, stop changing the edits, they are correcting your spelling errors, they are trying to help you ;)

Answer 6

When you say you don't know how many dimensions there are, how exactly are you defining the data structures?

At some point, someone needs to create this array, and to do that, they need to know the dimensions of the array. You can force the creator to pass in this data along with the array.

Unless the question is to define such a data structure...

MSN

Answer 7

Runt-Time isn't a word - stop changing those edits!

Answer 8

Ed, I'm looking at your post history and wondering if you're trying to pull an extended gag on Stack Overflow.

Do any of your questions make sense?

Answer 9

You're doing this in c/c++... so you have an array of array of array... you don't have to visualize 20 dimensions since that isn't how the data is laid out in memory, for a 2 dimensional:

[1] --> [1,2,3,4,5,6,...]
[2] --> [1,2,3,4,5,6,...]
[3] --> [1,2,3,4,5,6,...]
[4] --> [1,2,3,4,5,6,...]
[5] --> [1,2,3,4,5,6,...]
 .           .
 .           .
 .           .

so, why can't you iterate across the first one summing it's contents? If you are trying to find the size, then sizeof(array)/sizeof(int) is a risky approach. You must know the dimension to be able to process this data, and set the memory up, so you know the depth of recursion to sum. Here is some pseudo code of what it seems you should do,

sum( n_matrix, depth )
  running_total = 0
  if depth = 0 then
    foreach element in the array
      running_total += elm
  else 
     foreach element in the array
       running_total += sum( elm , depth-1 )
  return running_total

Answer 10

@Jeff

I actually think this is an interesting question. I'm not sure how useful it is, but it is a valid question.

@Ed

Can you provide a little more info on this question? You said the dimension of the array is dynamic, but is the number of elements dynamic as well?

EDIT: I'm going to try and answer the question anyways. I can't give you the code off the top of my head (it would take a while to get it right without any compiler here on this PC), but I can point you in the right direction ...

Let's use 8 dimensions (0-7) with indexes 0 to 3 as an example. You care about only 1,2 and 6. This means you have two arrays. First, array_care[4][4][4] for 1,2, and 6. The array_care[4][4][4] will hold the end result.

Next, we want to iterate in a very specific way. We have the array input[4][4][4][4][4][4][4][4] to parse through, and we care about dimensions 1, 2, and 6.

We need to define some temporary indexes:

int dim[8] = {0,0,0,0,0,0,0,0};

We also need to store the order in which we want to increase the indexes:

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

This order is important for doing what you requested.

Define a termination flag:

bool terminate=false;

Now we can create our loop:

while (terminate)
{
array_care[dim[1]][dim[2]][dim[6]] += input[dim[0]][dim[1]][dim[2]][dim[3]][dim[4]][dim[5]][dim[6]][dim[7]];

while ((dim[increase_index_order[i]] = 3) && (i < 8))
{
dim[increase_index_order[i]]=0;
i++;
}

if (i < 8) {
dim[increase_index_order[i]]++; i=0;
} else {
terminate=true;
}
}

That should work for 8 dimensions, caring about 3 dimensions. It would take a bit more time to make it dynamic, and I don't have the time. Hope this helps. I apologize, but I haven't learned the code markups yet. :(

Answer 11

Before we continue this guessing game why don't you tell us how this variable-dimension matrix is implemented (i.e. how do you query a value or the size of a dimension?), then perhaps we can help.

Answer 12

x = number_of_dimensions;
while (x > 1)
{
  switch (x)
  {
    case 20:
      reduce20DimensionArray();
      x--;
    break;
    case 19:
      .....
  }
}

(Sorry, couldn't resist.)

Answer 13

If I understand correctly, you want to sum all values in the cross section defined at each "bin" along 1 dimension. I suggest making a 1D array for your destination, then looping through each element in your array adding the value to the destination with the index of the dimension of interest.

If you are using arbitrary number of dimensions, you must have a way of addressing elements (I would be curious how you are implementing this). Your implementation of this will affect how you set the destination index. But an obvious way would be with if statements checked in the iteration loops.

Answer 14

This kind of thing is much easier if you use STL containers, or maybe Boost.MultiArray. But if you must use an array:

#include <iostream>
#include <boost/foreach.hpp>
#include <vector>

int sum(int x) {
    return x;
}

template <class T, unsigned N>
int sum(const T (&x)[N]) {
    int r = 0;
    for(int i = 0; i < N; ++i) {
        r += sum(x[i]);
    }
    return r;
}

template <class T, unsigned N>
std::vector<int> reduce(const T (&x)[N]) {
    std::vector<int> result;
    for(int i = 0; i < N; ++i) {
        result.push_back(sum(x[i]));
    }
    return result;
}

int main() {
    int x[][2][2] = {
        { { 1, 2 }, { 3, 4 } },
        { { 5, 6 }, { 7, 8 } }
    };

    BOOST_FOREACH(int v, reduce(x)) {
        std::cout<<v<<"\n";
    }
}

Answer 15

Just got home. Here is some info to answer your questions:

1. Sorry for rolling back the edits, I was hoping when I clicked roll-back it would show me the changes so I could see what I messed up, a bit like wikipedia. This wasn't the case, as I found out.
2. @jeff - What doesnt make sense? I am using this great service for (what I think is) a legit reason. I want to get better at my hobby, which is all it is, as I am in high school. Many of my posts regard implementing a genetic algorithm (This post, sparsearray, rank an array, pointer manipulation).
3. I am using a sparse array representation, as it is possible to exceed the number of molecules in the universe using a traditional (dense) array. For now, the implementation of the sparsearray itself doesnt matter a whole lot, as I am working to make it work with a standard array before going to a sparse representation. For those who havent seen my previous questions, I am using a binary search tree as the structure to contain the sparse array points, and a "driver" function to traverse the tree as necessary, returning whatever the function is designed to do. This is flexible, so I can accomodate a lot of different methods of accessing the array.
4. The structure is a hypercube, and the number of dimensions is specified at run time, as well as the lenght of each dimension (which are all the same, as it is a hypercube).

Thanks everyone for your imput.

Answer 16

This could have applications. Lets say you implemented a 2D Conway's Game of Life (which defines a 2D plane, 1 for 'alive', 0 for 'dead') and you stored the Games history for every iteration (which then defines a 3D cube). If you wanted to know how many bacteria there was alive over history, you would use the above algorithm. You could use the same algorithm for a 3D, (and 4D, 5D etc.) version of Game of Life grid.

I'd say this was a question for recursion, I'm not yet a C programmer but I know it is possible in C. In python,

def iter_arr(array):
  sum = 0
  for i in array:
    if type(i) == type(list()):
      sum = sum + iter_arr(i)
    else:
      sum = sum + i
  return sum 

1. Iterate over each element in array
2. If element is another array, call the function again
3. If element is not array, add it to the sum
4. Return sum

You would then apply this to each element in the 'cared about' dimension.

This is easier in python due to duck-typing though ...