0

I'm working on an open source scientific library (written in C) and one of the operations we want to support is to have a "consumer" copy out arbitrary slices of a multidimensional array from a "producer". For example, let's suppose we have a 4x5 2D array (I apologize for the formatting):

10, 20, 30, 40

50, 60, 70, 80

90, 100, 110, 120

130, 140, 150, 160

170, 180, 190, 200

These are exposed though as a linear array of size 20: 10, 20, 30, 40, 50, 60,..., 200

The user code basically passes in offsets and counts (basically coordinates)that it wants to select:

start[2] = {0, 2} (x start, y start)

count[2] = {3, 2} (x count, y count)

This means that for the x dimension, starting at the 0 position, give me 3 (x coordinate ranges are [0:2], and for the y dimension, starting at position 2, give me 2 (y coordinate ranges then are [3,4]).

This should result in

130, 140, 150, 170, 180, 190

copied into the users buffer (which will be of length 6).

So what is known: we know the dimension sizes of the array (4x5), the number of dimensions (2), and the "coordinates" that the user wants.

The array dimensions can be any number of dimensions... 1, 2, 3.. 6? 100? as it's quite common in scientific apps to have very large dimensions for your arrays.

This is C code, and I honestly can't think of an algorithm and turn it into code to solve the problem. I come from a biology background, so I'm not too experienced with the algorithmic thinking side of coding.

Dos anyone have any suggestions on how to solve this? Much help is appreciated!

Dunn
  • 11
  • 2
  • See my answer [here](http://stackoverflow.com/questions/30409991/use-a-dope-vector-to-access-arbitrary-slices-of-a-multidimensional-array/30409992#30409992). – luser droog May 23 '15 at 09:02

2 Answers2

0

In order to get the start in the linear array, you have to use start[0] * numColumns + start[1]. And you have to have a loop, like

Even with linear array, you could access an element with multidimensional syntax, because c stores multidimensional array as linear one internally.

 for(int i = start[0], countx = 0, count < xcount; countx++, i++) {
      for( int j = start[1], county = 0; county < ycount; county++, j++) {
           // copy array[i][j] into another array.
      }
 }
Karthikeyan
  • 990
  • 5
  • 12
  • Thank you for the reply. This will work for 2 dimension arrays. However, I am having trouble extending this basic concept for arbitrary dimension arrays. Do you have any ideas how I could extend this to n dimensions? Thanks! – Dunn Jul 26 '13 at 20:55
  • I guess to be clear, I don't know the array dimensions at compile time; the array to be exchanged is determined at run time. – Dunn Jul 26 '13 at 22:48
0

you must compute the offset for start of each dimension.

Given array[5][6][7][8] ;//indices a, b,c,d, etc. and dimensions dim(a)=5, dim(b) =6, dim(c)=7, dim(d) =8

for index a, position(0): pos(a[0]) = 0 which is really 0*6*7*8

for index a, position(a[1]) is 0 {pos(a[0]} + 1 (current value of index a) *6*7*8

and in general for index a, position(n) = pos(a[0]) + n * dim(b)*dim(c)*dim(d)

now in a linear arrangement such as this, your problem becomes an onion, peel away the outer dimiension to locate a position within the inner dimensions

for index b, position (or value) 0 is dependent on value of index a

so for index b we write a position relative to pos(a[2]) as pos(a[2]b[0]) = pos(a[2]) + position(b[0])

like pos(a[0]), pos(b[0]) is also 0; <0*dim(c)*dim(d)>, but its now relative to pos(a[n]) for any valid value 0<=n<=dim(a)

so pos(a[2]b[0]) = pos(a[2]) + 0

pos(a[2]b[1]) is pos(a[2]) + pos(b[1]) where posb[1] is 0 + 1 * dim(c)*dim(d)

so for any given coordinate pos(a[i]b[j]c[k],d[l]) your stating position is pos(a[i])+ pos(b[j], +pos(c[k])+pos(d[l])

to select any number of elements, you values will actually be coming from the set of the last dimension d.

if you wanted 2 units from a, 3 units from b, 1 unit from c and 2 units from d you would need to advance to pos(a[i]b[j]c[k]d[l]) and choose element d[l] and d[l+1]

then backtrack to pos(a[i],b[j+1],c[k],d[l]) and again choose two items d[l] and d[l+1].

clearly this solution would best be served by a recursive function.

I'm tied up with a project deadline(2.5 weeks left) but I could try to set up the code after that... if no one else dares to accept your challenge.

DRD
  • 43
  • 1
  • 6