Serialize a multi-dimensional array in a dynamic order

When you work with multi-dimensional arrays, sometimes you need to serialize the data into a one-dimensional array. This might be due to several reasons. Maybe some third-party method cannot handle multi-dimensionaly arrays, you want to store the array in a file or whatever reason there might be. There are several situations where multi-dimensional arrays are convenient. Images and volumes are a common example that use those form of memory representation. But there are lots of other examples. Usually a serialization looks somehow like this:

float[,,] myMultiDimensionalArray = new float[10, 20, 30];
float[] mySerialArray = new float[10 * 20 * 30];
int idx = 0;
for(var x = 0; x < 10; ++x)
    for(var y = 0; y < 20; ++y)
        for(var z = 0; z < 30; ++z)
            mySerialArray[idx++] = myMultiDimensionalArray[x, y, z];

That’s pretty straight forward and sufficient in most cases. However, when you need to change the serialization order, you have to change the whole code. For example, you might want to serialize along the x-axis first. Then you would need to:

for(var z = 0; x < 30; ++z)
    for(var y = 0; y < 20; ++y)
        for(var x = 0; z < 10; ++x)
            mySerialArray[idx++] = myMultiDimensionalArray[x, y, z];

Changing the code is ok if it is a one-time change. If you need to change the order at run-time, you’re stuck. Unless you want to compile the loop for each possible permutation, you need another approach for this.

What we can observe in the two example is that every time we iterate the domain of the array. Only the order in the output array is different. So let’s keep a skeleton of the serialization and just change the order by calculating the correct index:

for(var x = 0; x < 10; ++z)
    for(var y = 0; y < 20; ++y)
        for(var z = 0; z < 30; ++x)
            mySerialArray[CalculateIndex(x,y,z)] = myMultiDimensionalArray[x, y, z];

Now, constructing this method is the relevant part. Let’s look at what happens if we just serialize in order (example 1).

The most inner loop makes its elements follow each other (z0, z1, z=2…). They have a distance of 1. That’s not true for the next loop. Successive elements are 30 units apart from each other, because the whole z-row has to be serialized first (y0z0, y0z1, y0z2…, y0z29, y1z0…). Finally, the elements of the most outer loop are 20*30 = 60 units apart.

We can use this observation to construct a recursive function that creates a function. This assumes that we know the array size at construction time:


enum StreamComponent
{
    X, Y, Z //enumerate the dimensions of your array
}

//Adapt the function type based on the dimensionality of the array
private Func<int, int, int, int> ConstructStreamOrder(StreamComponent[] components, int offset, int currentStride)
{
    // The first component will become the inner loop. 
    // The offset defines which component to process next.
    // The currentStride defines the current distance of already processed components
    if (components.Length - offset <= 0)
        return (x, y, channel, c) => 0;

    var cmp = components[offset];

    switch (cmp)
    {
        case StreamComponent.X:
            return (x, y, z) => x * currentStride + ConstructStreamOrder(components, offset + 1, currentStride * arraySizeX)(x, y, z);
        case StreamComponent.Y:
            return (x, y, z) => y * currentStride + ConstructStreamOrder(components, offset + 1, currentStride * arraySizeY)(x, y, z);
        //...
        default:
            return (x, y, channel, c) => 0;
    }
}

private Func<int, int, int, int> ConstructStreamOrder(params StreamComponent[] components)
{
    return ConstructStreamOrder(components, 0, 1);
}

Which you can then use as:

var streamOrder = ConstructStreamOrder(StreamComponents.X, StreamComponents.Y, StreamComponents.Z);

for(var x = 0; x < 10; ++z)
    for(var y = 0; y < 20; ++y)
        for(var z = 0; z < 30; ++x)
            mySerialArray[streamOrder(x,y,z)] = myMultiDimensionalArray[x, y, z];

That’s it. You may even define other serialization schemes. For example, a zig-zag serialization like in the JPEG compression:

byte[] zigzag=
       { 0, 1, 5, 6,14,15,27,28,
	2, 4, 7,13,16,26,29,42,
	3, 8,12,17,25,30,41,43,
	9,11,18,24,31,40,44,53,
	10,19,23,32,39,45,52,54,
	20,22,33,38,46,51,55,60,
	21,34,37,47,50,56,59,61,
	35,36,48,49,57,58,62,63 };

 //...
     case StreamComponent.ZigZag: return (x, y, z) =>zigzag[z] * currentStride + ConstructStreamOrder(components, offset + 1, currentStride * 64)(x, y, z); //Assuming that z is in the range [0, 63]
Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: