Programming Examples

Are you a Programmer or Application Developer or a DBA? Take a cup of coffee, sit back and spend few minutes here :)

Performance Study – ArrayList vs TreeSet

1. TreeSet Performance vs ArrayList Performance

In the past examples, we came across ArrayList and TreeSet. We know how Binary Tree of TreeSet involves in search efficiency. In this example, we will compare performance of the TreeSet with ArrayList, Here, we use our Product class and add Millions of it to both TreeSet & ArrayList and then search for specific items in it. We do this test to know operation performance for both adding the items as well as finding the items.

2. Instant & Duration Classes

The Instant Class refers to a specific point in a timeline scale which started from 01/01/1970 Midnight & continuing till date and time. We can use this time Instant Class to punch a single time slot on the time scale. This example marks two time slots: t1 and t2 on the timeline. The time slot t1 refers to the operation start, and t2 refers the operation end.

With these Instant objects t1 & t2 in hand, we can use the Duration object to get time-elapse between them in Nano Seconds precision. So, we use this Instant and Duration together to test performance of the TreeSet and ArrayList. Below is the declaration for Instant:

3. Create ArrayList – 9 Million Items

The below code runs a ‘for loop’ Nine Million times and in each iteration, it adds an Integer object to the ArrayList. Recall, Java Collection performs boxing to wrap int value into Integer object. At line 2 & 6, we get the Time Instances and at line 8, we calculate the time in Milli Seconds for adding 9 Million items to the ArrayList.

4. Create TreeSet – 9 Million Items

After creating ArrayList with such a huge number of items, we follow the same technique to create the same number of items in the TreeSet. We do record time Instances and evaluate the time taken for the TreeSet construction with 9 Million Tree Nodes. Note, how we get the Duration instance from two time instances from & to. Also note how the toMillis method called on the Duration object returned. The code is below:

5. Construction – TreeSet Performance vs ArrayList

When we run the sample, it produces the following console output message:

Array Created in: 263 mSecs
TreeSet Created in: 11457 mSecs

From the above result, we carry out that building the TreeSet is taking more time than the ArrayList. This is because, for each new node TreeSet involves comparing the items, finding a proper place in the tree structure, and balancing it. So, construction vice, the ArrayList is the winner.

6. Searching Elements in ArrayList

The next test is searching for a specific item. First, we try this out in our ArrayList of Millions of Numbers. In the below code, we picked 5 numbers and searched that in the ArrayList via the contains method. Then calculated the time spawn for the operation using Instant and Duration Java SDK APIs. Note, this time we use toNanos to increase the accuracy as these operations are much faster compared to adding elements.

7. Searching Elements in TreeSet

Our ArrayList and TreeSet contains a same set of numbers. In this TreeSet also, we search for same four numbers as we did for the ArrayList. We do this so that we do not bias our comparison. The code snippet is same, but this time we use TreeSet in place of ArrayList. The code is below:

8. Search – TreeSet Performance vs ArrayList

From the console output below, we can see how fast the TreeSet in finding an item. Note, we measured the search action in Nano seconds using the toNanos function of the Duration class. While ArrayList takes 33 Milli-Seconds, the TreeSet takes just 1 Millisecond for the same search. Here, clearly the TreeSet is the Winner. Most of the software programs involve more search than the collection construction and alteration. But it is a developer’s call which one to use based on how frequently the collection items are altered and queried.

9. TreeSet Performance Test – Complete Code Example

Below is the complete code example for the Performance Test comparison between TreeSet and ArrayList:

10. Watch TreeSet Performance Test – YouTube Video

Categories: Java

Tags: , , , ,

Do you like this Example? Please comment about it for others!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.