Thread: Multidimensional Arrays

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    75

    Multidimensional Arrays

    Many languages reserve a block of memory large enough to hold all elements of the full, rectangular, array (number of rows times number of columns times the element size). Java doesn't do this. Instead Java builds multi-dimensional arrays from many one-dimensional arrays, the so-called "arrays of arrays" approach. [C++ supports both styles.]

    I even found a picture.
    http://www.brainbell.com/tutors/Visu...es/F04AI02.jpg


    What's the advantage of one over the other?
    And in the picture it seems that the C way would waste memory by creating a chunk of memory that is bigger than the requirements.

    Thanks.

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Advantage to doing it the Java way over making one uniform block of memory is that you have no other way by which to do this in Java. Other than that, I think having one solid block of memory makes the most sense. One advantage to having data segmented is that if you do have a buffer overflow, it may not destroy elements from an adjacent block of data. But that is an issue of programmer error more than anything.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Sparse arrays.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    It's possible in C to simulate a ragged array through the use of pointers. For simplicity, presume you want a 5-row array of int:
    Code:
    int *a[5];
    a[0] = malloc(5 * sizeof *a[0]);
    a[1] = malloc(3 * sizeof *a[1]);
    a[2] = malloc(4 * sizeof *a[2]);
    a[3] = malloc(8 * sizeof *a[3]);
    a[4] = malloc(10 * sizeof *a[4]);
    Real code would check the return value of malloc().

    Now you can access a[0][0] to a[0][4], a[1][0] to a[1][2], and so on. It doesn't act precisely how a multidimensional array acts (in C, a multidimensional array is really an array of arrays, believe it or not.) But it's very, very similar since the syntax to access this ragged array is the same as the syntax for a 2d array.

    Whether it's worth the extra effort is up to you. If you're worried about calling malloc() so many times, it's possible to do it with only one malloc() call; I just did it the above way because I think it's better for demonstrative purposes.

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    Comparison 1: Accessing an element

    Accessing an element from an array stored as a single contiguous chunk of memory will be more efficient. This is because each access will only require a single level of indirection. You presumably will have a pointer to the first element of the array, and you can calculate an offset from there based on the dimensions of the array.

    With a jagged array, more indirection is involved. First you calculate the offset to the row that you want and retrieve the address there. Using that address, you calculate the offset to the column you want. And if you have a higher dimensional array, more levels of indirection will be involved.

    Comparison 2: Cache Efficiency

    Having a single contiguous chunk of memory will obviously be more cache efficient. Spatial locality is as good as its going to get.

    A jagged array will be less cache efficient for obvious reasons - the memory for each row is not guaranteed to be adjacent to the memory for its neighboring rows.

    Comparison 3: Initialization

    A single chunk of memory is easy to allocate and initialize. Calculate how much memory you need, allocate it, and a simple loop will initialize it.

    A jagged array is slightly more complicated to allocate and initialize. First you allocate an array that will hold pointers to the rows. Then for each row you allocate memory for the columns in that row. You continue in the same fashion for higher dimensional array. I've seen many new programmers fail at this task because they didn't realize each row needed to be allocated as well.

    Comparison 4: Flexibility

    Using a single chunk of memory makes it impossible to have rows of differing sizes unless you specifically account for this by storing the row sizes separately or using some other complicated scheme to achieve this. This can result in wasted memory if you won't completely fill each row.

    Jagged arrays are very flexible. Since each row is allocated separately they can each be a different size. There is no need to waste space.

    Comparison 5: Adding new rows

    Adding a new row to a single chunk of memory will only be a problem if there isn't enough contiguous space available after the end of the array. In this case a reallocation will result in the entire array being moved in memory.

    Adding a row to a jagged array will not be a problem 99% of the time.

    Comparison 6: Adding new columns

    Oh dear. Adding a new column to single contiguous array is quite a task. Many items will need to be moved around.

    Adding a column to a jagged array isn't nearly as bad. Plus, you can add a column to a single row if you want. There's no need to change the size of every row.

    (Disclaimer: Obviously I'm assuming row-major ordering here.)

    Conclusion

    A simple chunk of memory is usually the most efficient way to store data. If you are writing a crucial algorithm that requires extreme efficiency, you will probably want to use a simple contiguous array unless you have a compelling reason not to.

    However, in most code extreme efficiency isn't needed. If you're responding to an button event in a form, or some timer that ticks once every couple hundred milliseconds or so, efficiency probably isn't your primary concern. Usually its better to use a more robust, easily modifiable data structure. Try to write code that is easy to read, maintain, and extend. Worry about efficiency only when and where it is a problem.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multidimensional Arrays?
    By CreatedByShadow in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2006, 10:35 PM
  2. Pointers to Multidimensional Arrays
    By kidburla in forum C Programming
    Replies: 10
    Last Post: 10-29-2005, 10:45 PM
  3. Multidimensional arrays in Korn shell
    By Yasir_Malik in forum Tech Board
    Replies: 3
    Last Post: 04-11-2004, 02:16 PM
  4. Adding multidimensional arrays
    By newbie2C++ in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2001, 04:05 PM
  5. Replies: 4
    Last Post: 11-05-2001, 02:35 PM