"Expanding" a 2d array into a 1d array

Question

I'm attempting to write a (hopefully) efficient way of "expanding" a 2d array into a 1d array. Let me illustrate what I mean:

Given the 2d array

{{1, 2},
 {3, 4}}

and a block width of 2 and a block height of 2, we can "expand" into a 1d array

{1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 4, 4, 3, 3, 4, 4}

Notice, if newlines are added this looks like

{1, 1, 2, 2,
 1, 1, 2, 2,
 3, 3, 4, 4, 
 3, 3, 4, 4}

And the original has been "expanded"!

The code I have currently is

public int[] expand(int[][] src, int blockWidth, int blockHeight) {
    int[] dest = new int[src.length * src[0].length * blockWidth * blockHeight];
    for (int i = 0; i < src.length; i++) {
        for (int j = 0; j < src[i].length; j++) {
            int fromIndex = i * blockWidth * blockHeight * src[i].length + j * blockWidth;
            int toIndex = fromIndex + blockWidth;
            Arrays.fill(dest, fromIndex, toIndex, src[i][j]);
        }
        int srcPos = i * blockWidth * blockHeight * src[i].length;
        for (int k = 1; k < blockHeight; k++) {
            int destPos = srcPos + k * blockWidth * src[i].length;
            System.arraycopy(dest, srcPos, dest, destPos, src[i].length * blockWidth);
        }
    }
    return dest;
}

This method:

Creates the destination array equal to the total size of the source array times the block dimensions.
For each color in a row, fill the first row of the destination.
Copy the first row into the rest of the rows, completing the blocks.

I wonder if there's a way to make this method more efficient or cleaner?

Thanks!

(I'd need a machine model to reason about efficiency (beyond redundant effort).) — greybeard
– greybeard, Commented Oct 13, 2016 at 5:42

rolfl · Accepted Answer · 2016-10-13 04:51:17Z

Problems like this are often "academic" in nature (although the principles can be applied to other problem-spaces too).

In this instance, I believe that the challenge is to use the correct form of "modulo" and integer-division type arithmetic and to have a "simple" conversion function for each target element.

Your initial output array creation looks good:

int[] dest = new int[src.length * src[0].length * blockWidth * blockHeight];

Note that a zero-sized, or null src array will cause an Exception to be thrown when indexing src[0]. You should probably be more defensive about that...

if (src == null || src.length == 0) {
    return new int[0];
}

Now, in your dest, the value of each cell is a function of its index. There are a few critical values:

target rowsize -> source row-size * block-width
source row -> ( target index / target rowsize) / block-height
source column -> ( target index % target rowsize ) / block-width

Now, the above logic is far from "obvious", but it makes for a remarkably simple loop:

public static int[] expand(int[][] src, int blockWidth, int blockHeight) {
    int span = src[0].length * blockWidth;
    int[] dest = new int[src.length * blockHeight * span];
    for (int i = 0; i < dest.length; i++) {
        dest[i] = src[(i / span) / blockHeight][(i % span) / blockWidth];
    }
    return dest;
}

You can see the above running in ideone: https://ideone.com/sJhksT

Note that the concept of describing an element in an output array as a function of the output index is sometimes a nice "trick" and neatens things up. You have to be able to spot this, though, in real code. Note that the above code basically says dest[i] = fn(i) where fn(i) is some function taking i as an argument.

Your code, on the other hand, works off the source index, and it tries to calculate the indexes in the output array from the source location. That's not "wrong", but as you can see, it makes for a nested, and ugly loop.

Knowing when to reverse the logic is more of an art than a science, but being able to identify these logic inversions is important.

Wow, very nice, thanks! I'll have to remember when I get into situations like this to not forget to investigate iterating by the dest index as well as by the src. — geofflittle
– geofflittle, Commented Oct 13, 2016 at 18:35

Stack Exchange Network

"Expanding" a 2d array into a 1d array

1 Answer 1

You must log in to answer this question.

Hot Network Questions

"Expanding" a 2d array into a 1d array

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions