C++

Forum

 
flattening 2d matrix how do I fix the iterations

technologist (607)
This post is from a digression in a closed one. Am attempting to flatten a 2d matrix. Below I can peek at the output and see what's happening, if only minimally. I can get all of my 2d data into the single dimension matrix and access all of them correctly if I find them with the formula below :

index = y * x_width + x;


The only real question is 1) is it safe and 2)are the iterations in the code problematic: if you try to step through the array indices outside of the formula there is data which shouldn't be there.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
#include "pch.h"
#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

int main()
{
	std::cout << "Make Matrix Environment" << std::endl;
	int index = 0; int count = 0; int element_num = 0;
	const int x_width = 3, y_heigth = 4;
	static int arr [x_width * y_heigth] = {};
	element_num = (x_width * y_heigth);
	
	for (int x = 0; x < x_width; x++)
	{
		count = 0;

		for (int y = 0; y < y_heigth; y++)
		{
			index = y * x_width + x;
			int iRand = (rand() % 99) + 1;
			std::cout << "Random number = " << iRand << std::endl;
			std::cout << "Index # stored to: " << index << std::endl; 
			arr[index] = iRand;
			std::cout << std::endl;
		}
	}
	std::cout << "Access Matrix Environment" << std::endl;

   // work backwards

	
	
	for (int x = 0; x < x_width; x++)
	{
	
		for (int y = 0; y < y_heigth; y++)
		{
			index = y * x_width + x;
			std::cout << arr[index] << std::endl;
		}
	}
	

}


Output:

Make Matrix Environment
Random number = 42 Index # stored to: 0
Random number = 54 Index # stored to: 3
Random number = 98 Index # stored to: 6
Random number = 68 Index # stored to: 9
Random number = 63 Index # stored to: 1
Random number = 83 Index # stored to: 4
Random number = 94 Index # stored to: 7
Random number = 55 Index # stored to: 10
Random number = 35 Index # stored to: 2
Random number = 12 Index # stored to: 5
Random number = 63 Index # stored to: 8
Random number = 30 Index # stored to: 11
Access Matrix Environment
42
54
98
68
63
83
94
55
35
12
63
30
Last edited on
jonnin (11437)
its easier to see using 0-N or something like that instead of random numbers. then you can print any element with your formula and figure out what you think it should be ... eg a 3x3 you know that [1][1] should be 4, right ([0,1,2] , [3, 4 ,5]...) which is the 4th element... 1(desired row)*3(number of cols) + 1 (desired col ) is 3+1 is 4...

flattening is safe as long as the storage is one block of memory**. If you allocate vectors of vectors or double pointers, it is NOT safe. When you do those kinds of things, each row is a pointer to a block of memory with 1 set of columns in it (or, one row if you think that way). Those pointers can be anywhere in memory, and you can't therefore get to them from the first row's first element as an offset.

unflattening can be done if the result is a constant in part; it suffers the same issue as multi dimensional arrays being passed as a parameter--- you need a fixed dimension to anchor off to make it work.

the formula looks right. its number of columns * desired row + desired column. That looks like what you did on line 41
think about how ROW MAJOR memory is aligned. its r0c0 r0c1 r0c2 ... r1c0 r1c1 ... rnc0 to rncm
then you can see that it is really stored row0, row1, row2 ... in that order linearly, where each row happens to be an array as well, thats ok.

** safe is relative. it is perfectly possible to mess up any kind of pointer type access with out of bounds problems. If you have a 3x3 and try to index [42], its just as wrong as saying [11][57] ... all these access reshapes do is give you an access point, and you can bug them up. So in that sense they are not safe, and raw pointers lack a .at or any sort of bounds checking. Its safe in the sense that if you do it right, it will work fine on all systems, its well defined behavior and all that.
Last edited on
AbstractionAnon (6954)
You're not seeding the random number generator by calling srand(). That means you're going to get the same sequence of pseudo-random numbers every time you run your program. Not calling srand() may be fine for debugging, but if you want different random numbers each time you run your program, you need to call srand() once at the beginning of main().
http://www.cplusplus.com/reference/cstdlib/srand/
seeplus (6589)
For testing, consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <iostream>
#include <random>

std::mt19937 rng(std::random_device {}());

int main() {
	constexpr size_t x_width {3}, y_heigth {4};
	constexpr auto element_num {x_width * y_heigth};
	const std::uniform_int_distribution<size_t> distrib(1, 100);
	static size_t arr[element_num] {};

	std::cout << "Make Matrix Environment\n";

	for (size_t x {}, cnt{}; x < x_width; ++x)
		for (size_t y {}; y < y_heigth; ++y) {
			const auto index {y * x_width + x};
			const auto iRand {distrib(rng)};

			//std::cout << "Random number = " << iRand << '\n';
			//std::cout << "Index # stored to: " << index << '\n';
			//arr[index] = iRand;
			arr[index] = cnt++;
		}

	std::cout << "Access Matrix Environment\n";

	// work backwards
	for (size_t x {}; x < x_width; ++x)
		for (size_t y {}; y < y_heigth; ++y) {
			const auto index {y * x_width + x};

			std::cout << arr[index] << ' ';
		}

	std::cout << '\n';

	for (size_t i {}; i < element_num; ++i)
		std::cout << arr[i] << ' ';

	std::cout << '\n';
}



0 1 2 3 4 5 6 7 8 9 10 11
0 4 8 1 5 9 2 6 10 3 7 11


This shows stored in col-major order.

But consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <iostream>
#include <random>

std::mt19937 rng(std::random_device {}());

int main() {
	constexpr size_t x_width {3}, y_height {4};
	constexpr auto element_num {x_width * y_height};
	const std::uniform_int_distribution<size_t> distrib(1, 100);
	static size_t arr[element_num] {};

	std::cout << "Make Matrix Environment\n";

	for (size_t y {}, cnt{}; y < y_height; ++y)
		for (size_t x {}; x < x_width; ++x) {
			const auto index {y * x_width + x};
			const auto iRand {distrib(rng)};

			//std::cout << "Random number = " << iRand << '\n';
			//std::cout << "Index # stored to: " << index << '\n';
			//arr[index] = iRand;
			arr[index] = cnt++;
		}

	std::cout << "Access Matrix Environment\n";

	// work backwards
	for (size_t y {}; y < y_height; ++y)
		for (size_t x {}; x < x_width; ++x) {
			const auto index {y * x_width + x};

			std::cout << arr[index] << ' ';
		}

	std::cout << '\n';

	for (size_t i {}; i < element_num; ++i)
		std::cout << arr[i] << ' ';

	std::cout << '\n';
}



0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11


which is now row-major
Last edited on
technologist (607)
flattening is safe as long as the storage is one block of memory**.


Seeing that I need to calculate the number of elements and compare to 1 block size doesn't seem that straight forward. If the indexes were simply 1,2,3,4...etc it would be easier but instead I am left to calculate from the index flattening formula "skips"-- which I see as memory addresses that got skipped over b/c the formula lands before and after. I could be totally off base but it would be good to nail down the storage size for my understanding with this size array.

What's the best way to calculate the memory the array will use? E.g.400 x 700 x 2 i.e.
Last edited on
MikeyBoy (5631)
Seeing that I need to calculate the number of elements and compare to 1 block size doesn't seem that straight forward. If the indexes were simply 1,2,3,4...etc it would be easier but instead I am left to calculate from the index flattening formula "skips"-- which I see as memory addresses that got skipped over b/c the formula lands before and after. I could be totally off base but it would be good to nail down the storage size for my understanding with this size array.

It's not clear what you're actually saying here, but just to clarify on the memory sizes:

If we're talking about C-style arrays (which is what you have in the code you've posted), it doesn't matter whether you define the array in terms of multiple dimensions or a single dimension, you get the same memory - a single, contiguous block of memory big enough to hold all the elements. For example:

int my_array[i][j];

will get you a single, contiguous block of memory containing storage for exactly i * j consecutive integers.

int my_array[i * j];

will get you exactly the same memory - a single, contiguous block of memory containing storage for exactly i * j consecutive integers.

What's the best way to calculate the memory the array will use? E.g.400 x 700 x 2 i.e.

For an array:

T my_matrix[i][j][k]

the amount of memory will allocated be:

i * j * k * sizeof(T)
Last edited on
technologist (607)
Awesome. So a flattened 3D to 1D matrix has negligible performance differences compared to similar matrices and access methods? So for a 400 x 700 x 2 array access times will have negligible diffs?I was just getting into the whole flattening the matrix thing. I really liked the idea to reduce the 3D's to 1-D.

For an array:

T my_matrix[i][j][k]

the amount of memory will allocated be:

i * j * k * sizeof(T)


Thank you for that. Back in the post(s) someone wrote that that amount of memory allocated shouldn't exceed 1 contiguous memory block (at least for 400 x 700 x 2) for the 3D-1D. Why is that? And given my matrix dimensions and your formula for array memory, what's my max?
Last edited on
jonnin (11437)
Awesome. So a flattened 3D to 1D matrix has negligible performance differences compared to similar matrices and access methods?

Pretty much. you can always noob it up, but at the end of the day, you have a starting point and an offset from there. As long as its one block of memory, that is about as efficient as it gets one way or another. If you access it wrong (eg, going down one column in a 2-d) you can have performance problems (the computer and design are made to go across a row, not down a column, and youll pay for it to go the other way, consider storing it transposed if you always do it the wrong way).

I think you are referring to a comment I made, and you didn't understand it. You can exceed a PAGE of memory, one 'block' a the operating system / hardware level. Pages are actually quite small and you WILL do this frequently. Not a problem, as long as you use one page to death before getting another one (see above on running down columns, that would cause it to grab pages more often inefficiently). When I say a block of memory, I mean that your array starts at some location, and the last location is rows*cols*depth*spaceandtime*otherdimension*sizeof(data_being_stored) -1.

let me see if I can restate that part again:


you CAN NOT DO IT if the memory is not one block of bytes.  
Vectors and C arrays ensure this to be true.  Linked lists, trees, 
or C style arrays allocated via double or triple pointers DO NOT 
ensure that.   If you try to flatten arrays created from MORE 
THAN ONE pointer, it will have access violations and either 
crash or do something awful.

vectors have one pointer each, so vectors of vectors is just like double pointer and you canna flatten that.

Here are some reason to flatten / do this sort of stuff.
- you need to touch every element, its possible depending on compiler smarts that its faster to have 1 loop instead of nested loops to do that. The difference is probably microscopic on most data on modern hardware and honestly, if you had really big data, you would use threading anyway.

- you want to 'reshape' (stolen from a matlab function that does exactly that) a matrix. You want your 10x10 to really be a 2x50. Both multiply out to 100, so that is OK... but its really hard to do if you allocated it 2d to begin with..! Speaking of transpose, to transpose 'in place' you need to reshape it as well..!

Last edited on
Topic archived. No new replies allowed.