Performant Concatenating 2D Arrays stored as sub-arrays

Question

Imagine we got a couple of 3x3 2D arrays that are identified by a X Y coordinate.

Pseudo code:

Array 0-0     Array 1-0
[[1,2,1]      [[1,2,1]  
 [2,3,2]       [2,3,2]
 [3,1,2]]      [3,1,2]]
 
Array 0-1     Array 1-1
[[1,2,1]      [[1,2,1]  
 [2,3,2]       [2,3,2]
 [3,1,2]]      [3,1,2]]

And we also have an index array, to index all this sub-arrays.

chunk_array = [
   [Array 0-0, Array 0-1],
   [Array 1-0, Array 1,1]
]

The problem is how to quickly create a final array, 6x6 containing all sub-arrays without having to iterate all elements of the array as this is a very critical place that has to operate in the minimal time possible.

So question: What would be the quickest way to perform this operation ? I've looked at Buffer copy, but not sure still what would be the best approach here.

Answer 1

Here's a solution based on the suggestion of Alexei Levenkov in the comments. From his comment: Fastest way to do something is not to do it at all... Does that work in your case (i.e. by wrapping all 4 into a class that exposes indexing the way you like)?

You create your four individual arrays and then add them to a wrapper capable of holding those arrays in a rectangular array. I use a function to access the individual elements, but you could use an indexer instead (if you are inclined that way - I'm not, that accessor seems a bit too complex for a simple indexer).

Here's the main class:

public class CompositeArray<T> where T:new()
{
    private readonly T[,][,] _componentArray = null;

    public int IndividualArrayWidth { get; }
    public int IndividualArrayHeight { get; }
    public int ComponentArrayWidth { get; }
    public int ComponentArrayHeight { get;  }
    public int OverallArrayWidth => IndividualArrayWidth * ComponentArrayWidth;
    public int OverallArrayHeight => IndividualArrayHeight * ComponentArrayHeight;

    public CompositeArray(int individualArrayWidth, int individualArrayHeight, int componentArrayWidth,
        int componentArrayHeight)
    {
        IndividualArrayWidth = individualArrayWidth;
        IndividualArrayHeight = individualArrayHeight;
        ComponentArrayWidth = componentArrayWidth;
        ComponentArrayHeight = componentArrayHeight;
        _componentArray = new T[ComponentArrayWidth, ComponentArrayHeight][,];
    }

    public void SetIndividualArray(int x, int y, T[,] array)
    {
        if (x < 0 || x >= IndividualArrayWidth)
        {
            throw new ArgumentOutOfRangeException(nameof(x), x, $@"Must be between 0 and {IndividualArrayWidth - 1}");
        }
        if (y < 0 || y >= IndividualArrayHeight)
        {
            throw new ArgumentOutOfRangeException(nameof(y), y, $@"Must be between 0 and {IndividualArrayHeight - 1}");
        }
        if (array.GetLength(0) != IndividualArrayWidth || array.GetLength(1) != IndividualArrayHeight)
        {
            throw new ArgumentOutOfRangeException(nameof(array),  $@"Must be between an array that is {IndividualArrayWidth} by {IndividualArrayHeight}");
        }

        _componentArray[x, y] = array;
    }

    public T GetOverallElement(int x, int y)
    {
        if (x < 0 || x >= OverallArrayWidth)
        {
            throw new ArgumentOutOfRangeException(nameof(x), x, $@"Must be between 0 and {OverallArrayWidth - 1}");
        }
        if (y < 0 || y >= OverallArrayHeight)
        {
            throw new ArgumentOutOfRangeException(nameof(y), y, $@"Must be between 0 and {OverallArrayHeight - 1}");
        }

        int whichArrayX = x / IndividualArrayWidth;
        int innerX = x % IndividualArrayWidth;
        int whichArrayY = y / IndividualArrayHeight;
        int innerY = y % IndividualArrayHeight;

        return (_componentArray[whichArrayX, whichArrayY][innerX, innerY]);
    }
}

Note that I create a rectangularly jagged rectangular array. It took a bit to figure out the syntax.

Note that there is no copying at all. You only pay for two integer divisions and two integer modulus operations per element access. If you only use 2x2 arrays, you could reduce that to two bit-shifts and two bit-tests (since division by two is a simple bit-shift, and checking for even/odd is simply a test of the least significant bit).

Here's some code that exercises that class:

 int[,] array00 = new int[,]
 {
     {1, 2, 3},
     {4, 5, 6},
     {7, 8, 9}
 };
 int[,] array01 = new int[,]
 {
     {11, 12, 13},
     {14, 15, 16},
     {17, 18, 19}
 };
 int[,] array10 = new int[,]
 {
     {21, 22, 23},
     {24, 25, 26},
     {27, 28, 29}
 };
 int[,] array11 = new int[,]
 {
     {31, 32, 33},
     {34, 35, 36},
     {37, 38, 39}
 };

 CompositeArray<int> bigArray = new CompositeArray<int>(array00.GetLength(0), array00.GetLength(1), 2,2);
 bigArray.SetIndividualArray(0, 0, array00);
 bigArray.SetIndividualArray(0, 1, array01);
 bigArray.SetIndividualArray(1, 0, array10);
 bigArray.SetIndividualArray(1, 1, array11);

 var shouldBe2 = bigArray.GetOverallElement(0, 1);
 var shouldBe6 = bigArray.GetOverallElement(1, 2);
 var shouldBe28 = bigArray.GetOverallElement(5, 1);
 var shouldBe16 = bigArray.GetOverallElement(1, 5);
 var shouldBe32 = bigArray.GetOverallElement(3, 4);

Answer 2

I think the best you can do is copy chunks of 3 values as they are all the source values that are contiguous in the destination array:

var ans = new int[6,6];

for (int row = 0; row < 2; ++row) {
    for (int col = 0; col < 2; ++col) {
        var srcArray = chunk_array[row, col];
        for (int subRow = 0; subRow < 3; ++subRow) {
            Array.Copy(srcArray, subRow*3, ans, subRow*6+row*18+col*3, 3);
        }
    }
}

Some performance testing doesn't show much optimization of this code possible.