Java Array Performance

By: Stephen Patrick | 25 May 2016 | Category: Java Array

Related Contents

Java Array Performance

In previous sections we described what an array is in java. If we recall an array has a type, and every element in a java array has the same type. So every element in an array is of a certain type, but an array also has a length. In this sense if we have an array that has a length of five and has a type of integer we say that we have a fixed size array of five integers. Moreover, this array is five continuous memory address, that we can access individually using an index.

Array Performance

In computer science we use a common notation for describing performance of a data structure. We call this measurement Big O Notation. Big O Notation is a means of measuring the performance of a data structure under certain operations as a consequence of the size of that data structure. We are only going to consider array performance at high level and we are not going to go in to all the details of the performance characteristics of any array data structure or different data structures for that matter, that is something we will cover later.

The performance of a java array we can see is intrinsic to its structure. So in Big O Notation the fastest operation performs in O(1) we say O(1) because no matter the size of the array the time to perform the operation is constant.

Can you think of an operation on an array that we talked about that performs in O(1) ?

Array Indexing Performance

Array indexing performance always performs in O(1) it is the fast operation that can be performed on a data structure. Why is that ? Well, if we remember that the array data structure has a fixed size and has N continuous memory locations we can access each element of the array by an index independent of the size of the array.

Array Searching

In general looking for an element in an array takes O(N), we say O(N) because the time to find an element of an array is proportional to its size. It, is important to point out we are talking about a sequential search algorithm, there are other algorithms we could use to perform a search on an array which we won’t cover in this section such as binary search, which operates on a sorted array in O(logN). Think about why iterating through an array takes O(N) again it is due to the structure of the array N continuous memory locations and we are going to start at the first element and iterate through the array until we find a matching element or we reach the end of the array.

   int[] intArray = {2,45,3,234,23,1};

   for (int i=0; i<intArray.length; i++) {
       if (intArray[i]  == 1) {
           System.out.println("Found element 1 at index: " + i);
       }
   }

Above we use a simple example of a java for loop to iterate through an array of 5 elements, looking for the element with value 1.

Arrays Have Fixed Size

As we have mentioned arrays have a fixed size. So how do we add a new element to an array that exceeds its bounds. Well, simple answer you can’t do that in Java. You might say well I can do it in C++. Then I would answer well you can in C++ but is that a safe operation?, and then you might say Oh yeah its a buffer overflow and it leaves my code vulnerable to attack. Anyway, since arrays have a fixed size in java if you want to perform this operation you have to create an array with the new size and copy the elements of the existing array to the new array.

What do you think the performance of this is in Big O Notation ?

In this section we have covered at a high level some of the performance characteristics and implications of using an array. Think about other operations on an array such as deleting an element from an array, or updating an element from an array, how do you think these operations perform?