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:
|
1 2 |
//Sample 01: To Get Time Difference Instant from, to; |
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.
|
1 2 3 4 5 6 7 8 |
//Sample 02: Create ArrayList with 9 Million Elements from = Instant.now(); List<Integer> arrList = new ArrayList<Integer>(); for (int i=10; i<9000000; i++) arrList.add(i); to = Instant.now(); System.out.println("Array Created in: " + Duration.between(from,to).toMillis() + " mSecs"); |
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:
|
1 2 3 4 5 6 7 8 |
//Sample 04: Create TreeSet with 9 Million Elements from = Instant.now(); SortedSet<Integer> theSet = new TreeSet<Integer>(); for (int i=10; i<9000000; i++) theSet.add(i); to = Instant.now(); System.out.println("TreeSet Created in: " + Duration.between(from,to).toMillis() + " mSecs"); |
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.
|
1 2 3 4 5 6 7 8 9 |
//Sample 05: Let us find 5 elements in ArrayList from = Instant.now(); System.out.println("Test Element 120000 exists : " + arrList.contains(120000)); System.out.println("Test Element 546352 exists : " + arrList.contains(546352)); System.out.println("Test Element 5736453 exists : " + arrList.contains(5736453)); System.out.println("Test Element 8243557 exists : " + arrList.contains(8243557)); to = Instant.now(); System.out.println("Search of 4 Elements took " + Duration.between(from,to).toNanos() + " Nano Secs in ArrayList"); |
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:
|
1 2 3 4 5 6 7 8 9 |
//Sample 06: Find same 5 elements in TreeSet from = Instant.now(); System.out.println("Test Element 120000 exists : " + theSet.contains(120000)); System.out.println("Test Element 546352 exists : " + theSet.contains(546352)); System.out.println("Test Element 5736453 exists : " + theSet.contains(5736453)); System.out.println("Test Element 8243557 exists : " + theSet.contains(8243557)); to = Instant.now(); System.out.println("Search of 4 Elements took " + Duration.between(from,to).toNanos() + " Nano Secs in TreeSet"); |
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.
|
1 2 3 4 5 6 7 8 9 10 |
Test Element 120000 exists : true Test Element 546352 exists : true Test Element 5736453 exists : true Test Element 8243557 exists : true Search of 4 Elements took 33000000 Nano Secs in ArrayList Test Element 120000 exists : true Test Element 546352 exists : true Test Element 5736453 exists : true Test Element 8243557 exists : true Search of 4 Elements took 1000000 Nano Secs in TreeSet |
9. TreeSet Performance Test – Complete Code Example
Below is the complete code example for the Performance Test comparison between TreeSet and ArrayList:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
//Sample 01: Package Required import java.time.Duration; import java.time.Instant; import java.time.LocalDateTime; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.SortedSet; import java.util.TreeSet; public class TreeSetNumberPerf { public static void main(String[] args) { //Sample 01: To Get Time Difference Instant from, to; //Sample 02: Create ArrayList with 9 Million Elements from = Instant.now(); List<Integer> arrList = new ArrayList<Integer>(); for (int i=10; i<9000000; i++) arrList.add(i); to = Instant.now(); System.out.println("Array Created in: " + Duration.between(from,to).toMillis() + " mSecs"); //Sample 04: Create TreeSet with 9 Million Elements from = Instant.now(); SortedSet<Integer> theSet = new TreeSet<Integer>(); for (int i=10; i<9000000; i++) theSet.add(i); to = Instant.now(); System.out.println("TreeSet Created in: " + Duration.between(from,to).toMillis() + " mSecs"); //Sample 05: Let us find 5 elements in ArrayList from = Instant.now(); System.out.println("Test Element 120000 exists : " + arrList.contains(120000)); System.out.println("Test Element 546352 exists : " + arrList.contains(546352)); System.out.println("Test Element 5736453 exists : " + arrList.contains(5736453)); System.out.println("Test Element 8243557 exists : " + arrList.contains(8243557)); to = Instant.now(); System.out.println("Search of 4 Elements took " + Duration.between(from,to).toNanos() + " Nano Secs in ArrayList"); //Sample 06: Find same 5 elements in TreeSet from = Instant.now(); System.out.println("Test Element 120000 exists : " + theSet.contains(120000)); System.out.println("Test Element 546352 exists : " + theSet.contains(546352)); System.out.println("Test Element 5736453 exists : " + theSet.contains(5736453)); System.out.println("Test Element 8243557 exists : " + theSet.contains(8243557)); to = Instant.now(); System.out.println("Search of 4 Elements took " + Duration.between(from,to).toNanos() + " Nano Secs in TreeSet"); } } |
10. Watch TreeSet Performance Test – YouTube Video
Categories: Java
Tags: Duration, Duration.between, Instant, toMillis, toNanos
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.