Feb 1, 2018 2:14 PM PT
Java programming fundamentals: Datastructures and algorithms in Java

Java 101: Datastructures and algorithms in Java, Part 3

Working with multidimensional arrays and the Matrix Multiplication algorithm

Peaches&Cream (CC BY 2.0)

In Datastructures and algorithms in Java, Part 2 I introduced a variety of techniques for searching and sorting one-dimensional arrays, which are the simplest arrays. In this article we'll explore multidimensional arrays. I'll introduce the three techniques for creating multidimensional arrays, then show you how to use the Matrix Multiplication algorithm to multiply elements in a two-dimensional array. I'll also introduce ragged arrays and show you why they are popular for big data applications. Finally, I will answer the question of whether an array is or is not a Java object. 

This article sets you up for Part 4, where I'll introduce searching and sorting with singly linked lists.

Introducing multidimensional arrays

A multidimensional array associates each element in the array with multiple indexes. The most commonly used multidimensional array is the two-dimensional array, also known as a table or matrix. A two-dimensional array associates each of its elements with two indexes.

We can conceptualize a two-dimensional array as a rectangular grid of elements divided into rows and columns. We use the (row, column) notation to identify an element, as shown in Figure 1.

Jeff Friesen

Figure 1. A conceptual view of a two-dimensional array reveals a grid of elements

Because two-dimensional arrays are so commonly used, I'll focus on them. What you learn about two-dimensional arrays can be generalized to higher-dimensional ones.

Creating two-dimensional arrays

There are three techniques for creating a two-dimensional array in Java:

  • Using an initializer
  • Using the keyword new
  • Using the keyword new with an initializer

Using an initializer to create a two-dimensional array

The initializer-only approach to creating a two-dimensional array has the following syntax:

'{' [rowInitializer (',' rowInitializer)*] '}'

rowInitializer has the following syntax:

'{' [expr (',' expr)*] '}'

This syntax states that a two-dimensional array is an optional, comma-separated list of row initializers appearing between open- and close-brace characters. Furthermore, each row initializer is an optional, comma-separated list of expressions appearing between open- and close-brace characters. Like one-dimensional arrays, all expressions must evaluate to compatible types.

Here's an example of a two-dimensional array:

{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }

This example creates a table with two rows and three columns. Figure 2 presents a conceptual view of this table along with a memory view that shows how Java lays out this (and every) table in memory.

Jeff Friesen

Figure 2. Conceptual and memory views of a two-dimensional array

Figure 2 reveals that Java represents a two-dimensional array as a one-dimensional row array whose elements reference one-dimensional column arrays. The row index identifies the column array; the column index identifies the data item.

Keyword new-only creation

The keyword new allocates memory for a two-dimensional array and returns its reference. This approach has the following syntax:

'new' type '[' int_expr1 ']' '['int_expr2 ']'

This syntax states that a two-dimensional array is a region of (positive) int_expr1 row elements and (positive) int_expr2 column elements that all share the same type. Furthermore, all elements are zeroed. Here's an example:

new double[2][3] // Create a two-row-by-three-column table.

Keyword new and initializer creation

The keyword new with an initializer approach has the following syntax:

'new' type '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'

where rowInitializer has the following syntax:

'{' [expr (',' expr)*] '}'

This syntax blends the previous two examples. Because the number of elements can be determined from the comma-separated lists of expressions, you don't provide an int_expr between either pair of square brackets. Here is an example:

new double [][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }

Two-dimensional arrays and array variables

By itself, a newly-created two-dimensional array is useless. Its reference must be assigned to an array variable of a compatible type, either directly or via a method call. The following syntaxes show how you would declare this variable:

type var_name '[' ']' '[' ']'
type '[' ']' '[' ']' var_name

Each syntax declares an array variable that stores a reference to a two-dimensional array. It's preferred to place the square brackets after type. Consider the following examples:

double[][] temperatures1 = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };
double[][] temperatures2 = new double[2][3];
double[][] temperatures3 = new double[][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } };

Like one-dimensional array variables, a two-dimensional array variable is associated with a .length property, which returns the length of the row array. For example, temperatures1.length returns 2. Each row element is also an array variable with a .length property, which returns the number of columns for the column array assigned to the row element. For example, temperatures1[0].length returns 3.

Given an array variable, you can access any element in a two-dimensional array by specifying an expression that agrees with the following syntax:

array_var '[' row_index ']' '[' col_index ']'

Both indexes are positive ints that range from 0 to one less than the value returned from the respective .length properties. Consider the next two examples:

double temp = temperatures1[0][1]; // Get value.
temperatures1[0][1] = 75.0;        // Set value.

The first example returns the value in the second column of the first row (30.6). The second example replaces this value with 75.0.

If you specify a negative index or an index that is greater than or equal to the value returned by the array variable's .length property, Java creates and throws an ArrayIndexOutOfBoundsException object.

Multiplying two-dimensional arrays

Multiplying one matrix by another matrix is a common operation in fields ranging from computer graphics, to economics, to the transportation industry. Developers usually use the Matrix Multiplication algorithm for this operation.

How does matrix multiplication work? Let A represent a matrix with m rows and p columns. Similarly, let B represent a matrix with p rows and n columns. Multiply A by B to produce a matrix C, with m rows and n columns. Each cij entry in C is obtained by multiplying all entries in A's ith row by corresponding entries in B's jth column, then adding the results. Figure 3 illustrates these operations.

Jeff Friesen

Figure 3. Each of A's rows is multiplied (and added) with each of B's columns to produce an entry in C.

The following pseudocode expresses Matrix Multiplication in a 2-row-by-2-column and a 2-row-by-1-column table context. (Recall that I introduced pseudocode in Part 1.)

// ==      ==   == ==   ==                     ==
// | 10  30 |   | 5 |   | 10 x 5 + 30 x 7 (260) |
// |        | X |   | = |                       | 
// | 20  40 |   | 7 |   | 20 x 5 + 40 * 7 (380) | 
// ==      ==   == ==   ==                     ==

DECLARE INTEGER a[][] = [ 10, 30 ] [ 20, 40 ]
DECLARE INTEGER b[][] =  [ 5, 7 ]
DECLARE INTEGER m = 2 // Number of rows in left matrix (a)
DECLARE INTEGER p = 2 // Number of columns in left matrix (a)
                      // Number of rows in right matrix (b)
DECLARE INTEGER n = 1 // Number of columns in right matrix (b)
DECLARE INTEGER c[m][n] // c holds 2 rows by 1 columns
                        // All elements initialize to 0
FOR i = 0 TO m - 1
   FOR j = 0 TO n - 1
      FOR k = 0 TO p - 1
         c[i][j] = c[i][j] + a[i][k] * b[k][j]
      NEXT k
   NEXT j
NEXT i
END

Because of the three FOR loops, Matrix Multiplication has a time complexity of O(n3), which is pronounced "Big Oh of n cubed." Matrix Multiplication offers cubic performance, which gets expensive time-wise when large matrixes are multiplied. It offers a space complexity of O(nm), which is pronounced "Big Oh of n*m," for storing an additional matrix of n rows by m columns. This becomes O(n2) for square matrixes.

I've created a MatMult Java application that lets you experiment with Matrix Multiplication. Listing 1 presents this application's source code.

Listing 1. MatMult.java

public final class MatMult
{
   public static void main(String[] args)
   {
      int[][] a = {{ 10, 30 }, { 20, 40 }};
      int[][] b = {{ 5 }, { 7 }};
      dump(a);
      System.out.println();
      dump(b);
      System.out.println();
      int[][] c = multiply(a, b);
      dump(c);
   }

   private static void dump(int[][] x)
   {
      if (x == null)
      {
         System.err.println("array is null");
         return;
      }

      // Dump the matrix's element values to the standard output in a tabular
      // order.

      for (int i = 0; i < x.length; i++)
      {
         for (int j = 0; j < x[0].length; j++)
            System.out.print(x[i][j] + " ");
         System.out.println();
      }
   }

   private static int[][] multiply(int[][] a, int[][] b)
   {
      // ====================================================================
      // 1. a.length contains a's row count
      //
      // 2. a[0].length (or any other a[x].length for a valid x) contains a's
      //    column count
      //
      // 3. b.length contains b's row count
      //
      // 4. b[0].length (or any other b[x].length for a valid x) contains b's
      //    column count
      // ====================================================================

      // If a's column count != b's row count, bail out

      if (a[0].length != b.length)
      {
         System.err.println("a's column count != b's row count");
         return null;
      }

      // Allocate result matrix with a size equal to a's row count times b's
      // column count

      int[][] result = new int[a.length][];
      for (int i = 0; i < result.length; i++)
         result[i] = new int[b[0].length];

      // Perform the multiplication and addition

      for (int i = 0; i < a.length; i++)
         for (int j = 0; j < b[0].length; j++)
            for (int k = 0; k < a[0].length; k++) // or k < b.length
               result[i][j] += a[i][k] * b[k][j];

      // Return the result matrix

      return result;
   }
}

MatMult declares a pair of matrixes and dumps their values to standard output. It then multiplies both matrixes and dumps the result matrix to standard output.

Compile Listing 1 as follows:

javac MatMult.java

Run the resulting application as follows:

java MatMult

You should observe the following output:

10 30 
20 40 

5 
7 

260 
380

Example of matrix multiplication

Let's explore a problem that is best solved by matrix multiplication. In this scenario, a fruit grower in Florida loads a couple of semitrailers with 1,250 boxes of oranges, 400 boxes of peaches, and 250 boxes of grapefruit. Figure 4 shows a chart of the market price per box for each kind of fruit, in four different cities.

Jeff Friesen

Figure 4. Market price for oranges, peaches, and grapefruit in four different cities

Our problem is to determine where the fruit should be shipped and sold for maximum gross income. To solve that problem, we first reconstruct the chart from Figure 4 as a four-row by three-column price matrix. From this, we can construct a three-row by one-column quantity matrix, which appears below:

==    ==
| 1250 |
|      |
|  400 |
|      |
|  250 |
==    ==

With both matrixes on hand, we simply multiply the price matrix by the quantity matrix to produce a gross income matrix:

==                  ==              ==        ==
| 10.00  8.00  12.00 |   ==    ==   | 18700.00 | New York
|                    |   | 1250 |   |          |
| 11.00  8.50  11.55 |   |      |   | 20037.50 | Los Angeles
|                    | X |  400 | = |          |
|  8.75  6.90  10.00 |   |      |   | 16197.50 | Miami 
|                    |   |  250 |   |          |
| 10.50  8.25  11.75 |   ==    ==   | 19362.50 | Chicago
==                  ==              ==        ==

Sending both semitrailers to Los Angeles will produce the highest gross income. But when distance and fuel costs are considered, perhaps New York is a better bet for yielding the highest income.

Ragged arrays

Having learned about two-dimensional arrays, you might now wonder whether it's possible to assign one-dimensional column arrays with different lengths to elements of a row array. The answer is yes. Consider these examples:

double[][] temperatures1 = { { 20.5, 30.6, 28.3 }, { -38.7, -18.3 } };
double[][] temperatures2 = new double[2][];
double[][] temperatures3 = new double[][] { { 20.5, 30.6, 28.3 }, { -38.7, -18.3 } };

The first and third examples create a two-dimensional array where the first row contains three columns and the second row contains two columns. The second example creates an array with two rows and an unspecified number of columns.

After creating temperature2's row array, its elements must be populated with references to new column arrays. The following example demonstrates, assigning 3 columns to the first row and 2 columns to the second row:

temperatures2[0] = new double[3];
temperatures2[1] = new double[2];

The resulting two-dimensional array is known as a ragged array. Here is a second example:

int[][] x = new int[5][];
x[0] = new int[3];
x[1] = new int[2];
x[2] = new int[3];
x[3] = new int[5];
x[4] = new int[1];

Figure 5 presents a conceptual view of this second ragged array.

Jeff Friesen

Figure 5. A ragged array specifies rows with varying numbers of column elements

Ragged arrays are useful datastructures because of their memory-saving capability. For example, consider a spreadsheet with the potential for 100,000 rows by 20,000 columns. If we attempt to use a matrix to hold the spreadsheet, we require a great deal of memory. But suppose most of the spreadsheet's cells contain default values, such as 0 for numeric cells and null for nonnumeric cells. If we use a ragged array instead of a matrix, we store only those cells that contain nonnumeric data. (Of course, we need some kind of mapping mechanism that maps spreadsheet (row, column) coordinates to ragged array (row, column) coordinates.)

Arrays are objects

According to the first sentence of Chapter 10 in the Java Language Specification arrays are objects in Java. Under the hood, each array is an instance of a hidden class that inherits java.lang.Object's 11 methods. The array instance overrides Object's protected Object clone() throws CloneNotSupportedException method, allowing the array to be shallowly cloned. The hidden class additionally provides a .length field.

Listing 2's ArrayIsObject source code demonstrates the association between arrays and objects.

Listing 2. ArrayIsObject.java

public final class ArrayIsObject
{
   public static void main(String[] args)
   {
      double[] a = { 100.5, 200.5, 300.5 };
      double[] b = { 100.5, 200.5, 300.5 };
      double[] c = b;
      System.out.println("a's class is " + a.getClass());
      System.out.println("a and b are " + ((a.equals(b)) ? "" : "not ") +
                         "equal ");
      System.out.println("b and c are " + ((b.equals(c)) ? "" : "not ") +
                         "equal ");
      double[] d = (double[]) c.clone();
      System.out.println("c and d are " + ((c.equals(d)) ? "" : "not ") +
                         "equal ");
      for (int i = 0; i < d.length; i++)
         System.out.println(d[i]);
   }
}

ArrayIsObject creates a-referenced and b-referenced double precision floating-point arrays with the same contents and lengths. For the a-referenced array, a.getClass() returns class [D, where [D is the name of the array's hidden class.

Despite the two arrays having the same contents, a.equals(b) returns false because equals() compares references (not contents), and a and b contain different references. b's reference is assigned to c, and b.equals(c) returns true because b and c reference the same array. c.clone() creates a shallow clone of c, and a reference to this new array is assigned to d.

To prove that the d-referenced array contains the same contents as the c-referenced array, the for loop iterates over all elements and prints their contents to the standard output. The loop reads the contents of d's read-only .length field to determine over how many elements to iterate.

Compile Listing 2 as follows:

javac ArrayIsObject.java

Run the resulting application as follows:

java ArrayIsObject

You should observe the following output:

a's class is class [D
a and b are not equal 
b and c are equal 
c and d are not equal 
100.5
200.5
300.5

Conclusion to Part 3

This article has introduced multidimensional arrays and the techniques for creating and using them in your Java programs. One very common technique is to multiply one matrix by another matrix. I showed you how to use the Matrix Multiplication algorithm to solve a real-world problem encoded as a pair of two-dimensional arrays. I also introduced ragged arrays and explained why they are especially valuable for big data applications. Finally, I addressed the question of whether arrays are objects in Java. Revealing the hidden class demonstrates that arrays are indeed objects, with all the powers inherited from java.lang.Object.

Stay tuned for Part 4, where we will explore singly linked lists and their algorithms!