TheDeveloperBlog.com


Java

Java Array Examples and Performance

Arrays are linear collections of elements. They do not automatically resize. They have fixed lengths. This makes them harder to use but faster.


Fundamental. Arrays are a fundamental type, used often inside other types. We find helpful methods in the Arrays class, from java.util.Arrays.


Syntax. Arrays use the square brackets to index elements. These brackets are also used in array declarations. We create an array of five int elements.

First index: The first index in an array is zero. When there are no elements, index 0 is out of range.

Last index: The last index of an array is equal to the array length minus one. This is true when at least one element exists.

Based on:

Java 7

Java program that uses array

public class Program {
    public static void main(String[] args) {

	// Create int array.
	int[] array = new int[5];

	// Assign first three elements.
	array[0] = 1;
	array[1] = 10;
	array[2] = 100;

	// Loop over elements.
	for (int i = 0; i < array.length; i++) {
	    // Get value.
	    int value = array[i];
	    // Print value.
	    System.out.println(value);
	}
    }
}

Output

1
10
100
0
0

Length, loops. Every array has a length, even if it has zero elements (but be careful to check the reference for null when needed). We often use length in for-loops as the upper boundary.

Array LengthFor

Types. An array can have any type. Here we create a four-element array of chars. We assign characters to the indexes 0 through 3. And then we use a loop to iterate.

Tip: For-each loop syntax is often applied to arrays. This reduces syntax complexity—no index variable is used.

Java program that uses char array, loop

public class Program {
    public static void main(String[] args) {

	// Create an array of four chars.
	char[] values = new char[4];
	values[0] = 'j';
	values[1] = 'a';
	values[2] = 'v';
	values[3] = 'a';

	// Loop over array with for-loop.
	for (char value : values) {
	    System.out.println(value);
	}
    }
}

Output

j
a
v
a

Initialize. A shorter, simpler syntax can be used to initialize an array. We must use curly brackets. We specify the initial elements within these brackets.

Syntax: Here we see the syntax for an int array and a String array. Each array in this example has three elements.

Java program that initializes arrays

public class Program {
    public static void main(String[] args) {

	// Two input arrays.
	int[] array1 = {1, 3, 5};
	String[] array2 = {"frog", "toad", "squirrel"};

	// Array lengths.
	System.out.println(array1.length);
	System.out.println(array2.length);

	// First elements in each array.
	System.out.println(array1[0]);
	System.out.println(array2[0]);
    }
}

Output

3
3
1
frog

Loop in reverse. Sometimes we want to do things backwards. To loop over an array from end to start, we begin at the last index (equal to length minus one). We decrement and proceed to 0.

Java program that loops over array in reverse

public class Program {
    public static void main(String[] args) {

	boolean[] values = { false, true, true, true };

	// Loop over array elements in reverse order.
	for (int i = values.length - 1; i >= 0; i--) {
	    System.out.println(values[i]);
	}
    }
}

Output

true
true
true
false

Empty. How can we create an empty array? The array initializer syntax (with curly brackets) works. Or we can allocate a new array, as usual, but specifying zero as its length.

Java program that creates empty arrays

public class Program {
    public static void main(String[] args) {

	// Two empty arrays.
	int[] array1 = {};
	int[] array2 = new int[0];

	// Each has zero length.
	System.out.println(array1.length);
	System.out.println(array2.length);
    }
}

Output

0
0

Null arrays. An empty array is different from a null array. With an empty, zero-element array, we safely use fields and methods. With a null array, this provokes a NullPointerException.

Exceptions

Sort. We sort an array with the Arrays.sort method. This is part of the java.util.Arrays class. This method sorts the array in-place, meaning no value is assigned to the sort method.

Ascending: The Arrays.sort method by default uses an ascending sort, meaning elements are ordered from low to high.

Java program that sorts array

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	int[] array = { 100, 20, 0, 200 };

	// Call Arrays.sort on the int array.
	Arrays.sort(array);

	for (int elem : array) {
	    System.out.println(elem);
	}
    }
}

Output

0
20
100
200

Fill. Often an array needs to be filled with a certain value. We invoke the Arrays.fill method: we specify an array, and a value. Each element is set to that value.

Java that uses Arrays.fill

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	int[] values = new int[10];

	// Fill array with this number.
	Arrays.fill(values, 5);

	for (int value : values) {
	    System.out.print(value);
	    System.out.print(' ');
	}
    }
}

Output

5 5 5 5 5 5 5 5 5 5

Arrays.copyOf. This method creates a copy of a target array. We specify the length of the new array. So we can reduce or increase the size, filling new elements with default values.

Resize: This is essentially a resize method. An array's length is not dynamic. Resizing can only be done when copying.

Java that uses Arrays.copyOf

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	int[] values = { 10, 20, 30, 40 };

	// Copy and display first 3 elements.
	int[] copy = Arrays.copyOf(values, 3);
	for (int value : copy) {
	    System.out.println(value);
	}
	System.out.println();

	// Copy five elements.
	int[] copy2 = Arrays.copyOf(values, 5);
	for (int value : copy2) {
	    System.out.println(value);
	}
    }
}

Output

10
20
30

10
20
30
40
0

Arrays.copyOfRange. With this method, we specify a start index and an end index. A new array, containing only that range, is created and returned. The last index is exclusive.

Java that uses Arrays.copyOfRange

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	int[] values = { 0, 10, 20, 30, 40, 50 };

	// Copy elements from index 2 to 5 (2, 3, 4).
	int[] result = Arrays.copyOfRange(values, 2, 5);
	for (int value : result) {
	    System.out.println(value);
	}
    }
}

Output

20
30
40

Sentinels. In an array, we can store special values that indicate the array ends. These are sentinel elements. In this program, we use the value -1 for a sentinel.

And: We readjust the sentinel value without modifying the rest of the array. This is a fast way to change the conceptual length.

With sentinels: We can optimize program store use buffers and arrays. This makes programs faster.

Java that tests for sentinel

public class Program {

    static void scan(int[] buffer) {
	for (int i = 0; i < buffer.length; i++) {
	    // Terminate loop when sentinel element is detected.
	    if (buffer[i] == -1) {
		break;
	    }
	    System.out.println(buffer[i]);
	}
	System.out.println();
    }

    public static void main(String[] args) {

	// The sentinel element is the sixth one.
	int[] buffer = { 10, 20, 30, 25, 35, -1, 50, 55 };
	scan(buffer);
	// Make the third element the sentinel.
	buffer[2] = -1;
	scan(buffer);
    }
}

Output

10
20
30
25
35

10
20

Arrays.toString. This method is helpful when displaying arrays. This is a static method. It uses square brackets and commas to display an array.

Java that uses Arrays.toString

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	int[] values = { 505, 100, 605 };
	// Call Arrays.toString to display the elements.
	System.out.println(Arrays.toString(values));
    }
}

Output

[505, 100, 605]

Merge two arrays. This program merges two arrays. It allocates a third array—this is large enough to hold both of the arrays. We then use for-loops to copy into this array.

Note: The second loop uses an offset value, equal to values.length to assign into the merged array.

Java that merges two arrays

import java.util.Arrays;

public class Program {
    public static void main(String[] args) {

	int[] values = { 10, 20, 30 };
	int[] values2 = { 100, 200, 300 };

	// Merge the two arrays with for-loops.
	int[] merge = new int[values.length + values2.length];
	for (int i = 0; i < values.length; i++) {
	    merge[i] = values[i];
	}
	for (int i = 0; i < values2.length; i++) {
	    merge[i + values.length] = values2[i];
	}

	// Display the merged array.
	System.out.println(Arrays.toString(merge));
    }
}

Output

[10, 20, 30, 100, 200, 300]

Speed. Arrays are harder to use than ArrayLists. But they yield a speed advantage, even on simple element accesses. Here I sum two 100-element collections: an array and an ArrayList.

And: We find accessing all elements in a loop is faster with an array. The lower-level code has a benefit in speed.

Thus: Arrays are helpful when performance is key. The extra logic needed to accommodate array size is worthwhile in certain spots.

Java that times array, ArrayList

public class Program {
    public static void main(String[] args) {

	// ... Create array.
	int[] array = new int[100];
	array[0] = 1;

	// ... Create ArrayList.
	ArrayList<Integer> list = new ArrayList<>();
	list.add(1);
	for (int i = 1; i < 100; i++) {
	    list.add(0);
	}

	long t1 = System.currentTimeMillis();

	// Version 1: sum all elements in an array.
	for (int i = 0; i < 1000000; i++) {

	    int sum = 0;
	    for (int v = 0; v < array.length; v++) {
		sum += array[v];
	    }
	    if (sum != 1) {
		System.out.println(false);
	    }
	}

	long t2 = System.currentTimeMillis();

	// Version 2: sum all elements in an ArrayList.
	for (int i = 0; i < 1000000; i++) {

	    int sum = 0;
	    for (int v = 0; v < list.size(); v++) {
		sum += list.get(v);
	    }
	    if (sum != 1) {
		System.out.println(false);
	    }
	}

	long t3 = System.currentTimeMillis();

	// ... Times.
	System.out.println(t2 - t1);
	System.out.println(t3 - t2);
    }
}

Results

38 ms, int[],     array[i]
91 ms, ArrayList, list.get(i)

Locality of reference. Elements nearer together in memory are faster to access. We can exploit this principle to optimize programs. Here we use locality of reference in an array.

Version 1: This loop reads the values of 100 elements in an array. The elements are packed together.

Version 2: This loop instead loads 100 elements, but they are spaced 100 elements apart each.

Result: The loop that accesses the elements that are packed tight together is faster. The programs has no other important differences.

Java that shows locality of reference

public class Program {
    public static void main(String[] args) {

	// Create an array and fill it with values.
	int[] values = new int[1000000];
	for (int i = 0; i < values.length; i++) {
	    values[i] = i;
	}

	long t1 = System.currentTimeMillis();

	// Version 1: sum 100 elements that are packed together.
	for (int i = 0; i < 1000000; i++) {
	    int sum = 0;
	    for (int x = 0; x < 100; x++) {
		sum += values[x];
	    }
	    if (sum == 0) {
		System.out.println(false);
	    }
	}

	long t2 = System.currentTimeMillis();

	// Version 2: sum 100 elements spaced apart by 100 slots each.
	for (int i = 0; i < 1000000; i++) {
	    int sum = 0;
	    for (int x = 0; x < 10000; x += 100) {
		sum += values[x];
	    }
	    if (sum == 0) {
		System.out.println(false);
	    }
	}

	long t3 = System.currentTimeMillis();

	// ... Times.
	System.out.println(t2 - t1);
	System.out.println(t3 - t2);
    }
}

Results

35 ms,  access 100 packed elements (more locality)
61 ms,  access 100 sparse elements

BinarySearch. A large, sorted array can be searched faster with binarySearch. This method "hones" in on a target value. It occasionally is useful.

Arrays.binarySearch

Two-dimensional. Complexity increases when we add another dimension to our arrays. We use two indexes to access and store elements. Jagged arrays, and 3D arrays, are also used.

2D Arrays

Array types. Often in programs we deal with large amounts of text. This data is effectively stored in string arrays. Numeric types like int are also often placed in arrays.

Char ArraysInt ArraysObject ArraysString Arrays

Filter, IntStream. We can convert an array to a stream (like an IntStream) with the Arrays.stream method. Then we can use methods like filter, with lambdas, to modify our collections.

Filter

ArrayList. Often we do not know how many elements will be added. An array makes this problem hard. We must copy it to resize it. With ArrayList resizing is automatic.

ArrayListArrayList: Add Array

Low-level. Arrays are a lower-level construct, of a static memory size. We must create a new array to resize. An advantage of arrays is blazing speed.


Compatibility. Arrays are often expected by other methods. This makes them important for interoperability. They are essential in many programs.