将2D数组映射到1D数组

For fun, I am trying to represent a 2D array in 1D array. How can I map a 2-dimensional array to 1 dimensional array?

为了好玩,我试图在一维数组中表示一个二维数组。如何将二维数组映射到一维数组?

For example, suppose we are given an array:

例如,假设我们得到一个数组:

char[][] 2dArray = new char[4][4];

In 2-dimensional space, the range (0,0),(2,2) would represent 9 elements (represented as O below): O, O, O, X O, O, O, X O, O, O, X X, X, X, X

在二维空间中,范围(0,0),(2,2)将代表9个元素(以下表示为O):O,O,O,XO,O,O,XO,O,O,XX, X,X,X

If we represent the two-dimensional array as a 1-dimensional array:

如果我们将二维数组表示为一维数组:

char[] 1dArray = new char[16];

it would look like this:

它看起来像这样:

O, O, O, X, O, O, O, X, O, O, O, X, X, X, X, X

I already know that I can find the index of a single point in my 1-dimensional array via the formula: (rows * x + y).

我已经知道我可以通过以下公式在我的1维数组中找到单个点的索引:(rows * x + y)。

i.e. the 2d point (2,3) would map to the 1d index 11 in the given example.

即,在给定示例中,2d点(2,3)将映射到1d索引11。

Given a pair of 2D coordinates, How can I map a rectangular section of points to a 1D array? I prefer not to use loop nesting, if possible.

给定一对2D坐标,如何将矩形截面的点映射到一维数组?如果可能的话,我不想使用循环嵌套。

4 个解决方案

#1

Let assume rectangular 2D array of chars like these:

假设像这样的字符的矩形2D数组:

const int xs=6; // columns
const int ys=4; // rows
char dat2D_xy[xs][ys]=
    {
    "06ci",
    "17dj",
    "28ek",
    "39fl",
    "4agm",
    "5bhn",
    };
char dat2D_yx[ys][xs]=
    {
    "012345",
    "6789ab",
    "cdefgh",
    "ijklmn",
    };
dat2D_xy[5][3] == dat2D_yx[3][5] == 'n';

Then to convert x,y coordinates to 1D index and back you can use:

然后将x,y坐标转换为1D索引并返回,您可以使用:

i=x+(xs*y);
x=i%xs;
y=i/xs;

Or this:

i=y+(ys*x);
x=i%ys;
y=i/ys;

Does not matter which it just changes the order of items in the 1D array. To copy whole array to 1D you need to use 2 nested loops or just single one with addition to DMA or any other memory transfer. Something like this:

无论它只改变1D数组中项目的顺序。要将整个数组复制到1D,您需要使用2个嵌套循环或仅添加一个DMA或任何其他内存传输的单个循环。像这样的东西:

int i,x,y;
char dat1D[xs*ys];
for (i=0,y=0;y<ys;y++)
 for (x=0;x<xs;x++,i++)
  dat1D[i]=dat2D_xy[x][y];
//dat1D[i]=dat2D_yx[y][x];

//dat1D[]="0123456789abcdefghijklmn";

or:

int i,x,y;
for (i=0,x=0;x<xs;x++)
 for (y=0;y<ys;y++,i++)
  dat1D[i]=dat2D_xy[x][y];
//dat1D[i]=dat2D_yx[y][x];

//dat1D[]="06ci17dj28ek39fl4agm5bhn";

There are no X needed ... unless you want to add also the null termination characters at the end of each row/line to ease up debug view or process rows or columns as strings. In such case you add +1 for line size and add your termination character.

除非您想在每行/每行的末尾添加空终止字符以简化调试视图或将行或列作为字符串处理,否则不需要X ...在这种情况下,您为行大小添加+1并添加终止字符。

#2

It is easy, first decide for a storage order (column major or row major), then with a nested loop you fill from 2D matrix A the 1D array B:

这很容易,首先决定存储顺序(列主要或行主要),然后使用嵌套循环从2D矩阵A填充1D数组B:

Example:

A is a NxM matrix

A是NxM矩阵

for i in 
    for j in M
        B[i*M + j] = A[i][j]

#3

I think you will need some language features if you don't want neseted loop. This is my example in python.

我想如果你不想要neseted循环,你将需要一些语言功能。这是我在python中的例子。

First lets create a list a of dimension 4 x 4 where a[i][j] is a tuple of (i, j)

首先让我们创建一个维度为4 x 4的列表a,其中[i] [j]是(i,j)的元组

a = [[(i, j) for j in range(4)]for i in range(4)]

Now suppose we only want the submatrix from (1, 1) to (2, 3). First lets filter elements from row 1 to row 2

现在假设我们只想要从(1,1)到(2,3)的子矩阵。首先让过滤元素从第1行到第2行

rows = a[1:3]

行= a [1:3]

Then we get the elements between col 1 and col 3 to get the submatrix.

然后我们得到col 1和col 3之间的元素来获得子矩阵。

submatrix = [row[1:4] for row in rows]

submatrix = [行[1:4]为行中的行]

Now we have the submatrix, to convert it to 1d list, we can use sum

现在我们有子矩阵,将它转换为1d列表,我们可以使用sum

ans = sum(submatrix, [])

ans = sum(子矩阵,[])

Finally if we print ans, we will have

最后,如果我们打印ans,我们将有

[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)]

[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]

Combining things together, we have this function, where a is the input matrix, p1 and p2 are input points for locating the submatrix

将事物组合在一起,我们有这个函数,其中a是输入矩阵,p1和p2是用于定位子矩阵的输入点

def f(a, p1, p2):
    x1, y1 = p1
    x2, y2 = p2

    return sum([row[y1:y2 + 1] for row in a[x1:x2 + 1]], [])

#4

It is possible without nested loop and no language support (and wasn't mentioned yet), but I doubt it will be faster (array with n rows and m columns):

没有嵌套循环并且没有语言支持(并且还没有提到),但是我怀疑它会更快(具有n行和m列的数组):

for (int i = 0; i < n * m; i++)
    arr1D[i] = arr2D[i / m][i % m];

The modulo obviously gives 0, 1, 2, ..., m - 1 and then starts at 0 again, as it should and the result of the integer division is increased by one after a row is full. Or to read column by column (worse in most languages, better read row by row as above):

模数显然给出0,1,2,...,m - 1,然后再次从0开始,就像它应该的那样,整数除法的结果在一行满之后增加1。或者逐列阅读(在大多数语言中更糟糕,如上所述,更好地逐行阅读):

for (int i = 0; i < n * m; i++)
    arr1D[i] = arr2D[i % n][i / n];

However this works only with rectangular matrices. Counter example:

然而,这仅适用于矩形矩阵。反例:

int[][] arr2D = new int[2][];
arr2D[0] = new int[1];
arr2D[1] = new int[2];

In this case it would be best to do it in the standard way, using a list here because I don't know what the length of the result is going to be (add null checks if null is a possibility):

在这种情况下,最好以标准方式进行,使用此处的列表,因为我不知道结果的长度是多少(如果null是可能的话,添加null检查):

List<Integer> list = new ArrayList<>();
for (int i = 0; i < arr2D.lengh; i++)
    for (int j = 0; j < arr2D[i].length; j++)
        list.add(arr2D[i][j]);

#1