0

I was doing some work handling a lot of information and my partner told me that I was using too many matrices to manipulate the variables of the problem. The idea was to use one dimension arrays int a[] instead of the 2 dimensional arrays int b[][], to save memory and processing speed of the algorithm. How certain is that this change will accelerate the speed of execution or compilation of my code in c ++?

user3869145
  • 1
  • 1
  • 3
    It should make no difference, if you really are talking about 1D vs. 2D arrays. The data layout is contiguous for both. The 2D array has clever indexing, which you would have to implement by hand when using a 1D array in lieu of a 2D one. – juanchopanza Aug 19 '14 at 21:50
  • 1
    This change would have no effect on the compilation speed. It does have a potential of reducing the memory footprint, in cases when you allocate `int b[MAX_SIZE][MAX_SIZE]` and use only a portion of it. – Sergey Kalinichenko Aug 19 '14 at 21:52
  • 1
    For whatever it's worth, there's always something to say for readability too though. Speed wise, the difference is negligible at best. – user2366842 Aug 19 '14 at 21:56
  • 1
    Considering how far compiler-transformations go, you are likely to get the same result for both. Measure and compare, don't theorize without any data. Premature optimization is the root of much evil. – Deduplicator Aug 19 '14 at 21:56
  • Actually rectangular 2D arrays, `int b[R][C]`, will end up to be 1D array. –  Aug 19 '14 at 21:57
  • 3
    You can always *treat* the 2D array (if it really is one, i.e. is not a jagged array) as a 1D array, because the Holy Standard guarantees that arrays are contiguous with no padding. This stems from the `sizeof` guarantees. That said, for a 2D array of dynamic size it's usually simplest to implement it in terms of a single 1D array, e.g. use a `std::vector` as storage. – Cheers and hth. - Alf Aug 19 '14 at 22:02
  • Note, above advice only applies for non-dynamically allocated arrays. – Xarn Aug 19 '14 at 22:05
  • `and my partner told me that I was using too many matrices to manipulate the variables of the problem.` ... `to save memory and processing speed of the algorithm` I think you should seriously consider getting a different partner. – PaulMcKenzie Aug 19 '14 at 22:10
  • Plain old 2d arrays, no difference. However, sometimes 2d arrays are represented as an array of pointers to arrays. In that case, each row is in a different location in memory and there are extra levels of indirection to reach the data. This can harm performance, as there is poor data locality. A 1d array using an indexing calculation to simulate a 2d array can help that. This is essentially what normal 2d arrays do. – Neil Kirk Aug 19 '14 at 22:12
  • @user2366842 - Also, if your 2D arrays are truly dynamic, there are ways of creating the data contiguously *and* keep the `[][]` syntax. See here: http://stackoverflow.com/questions/21943621/how-to-create-a-contiguous-2d-array-in-c/21944048#21944048 – PaulMcKenzie Aug 19 '14 at 22:16

1 Answers1

2

Your question invites to guesswork, but:

How certain is that this change will accelerate the speed of execution or compilation of my code in c ++?

Prognosis is extremely uncertain. The only proper response is to measure.

Measuring is knowing. You can quote me on that.

Captain Giraffe
  • 14,407
  • 6
  • 39
  • 67