is it faster to create a SortedSet (of objects) and insert elements to it or create an ArrayList and sort it afterwards?

Question

I have one million lines in a file. An object is created out of each line and added to a collection. The collection has to be sorted using the custom compareTo() method of class.

Currently I add objects to an ArrayList in the order of reading, then do Collections.sort().

Would it be faster to make a TreeSet?

It would probably be slower, but trying out takes about three lines of code. — Marko Topolnik, Feb 17 '15 at 11:07
@FINDarkside, I am a beginner as of now so I would like to not only see it in action, but understand the theory behind it too. I am trying it out now. — Euphe, Feb 17 '15 at 11:09
arraylist has complexity of O(n) for add operation and after sorting will take time n log(n) and at the same level treeset has inbuilt custom comparator with complexity of log(n) for add and for addall() operation will give O(n log n) — Bhargav Modi, Feb 17 '15 at 11:12
Take a look at this question: [java-collections-sort-performance](http://stackoverflow.com/questions/2883821/java-collections-sort-performance) — David SN, Feb 17 '15 at 11:16

R2-D2 · Accepted Answer · 2015-02-17T16:52:52.657

Both methods are in (n log(n)) time: adding an item to an ArrayList has a worst case of (n), but usually is done in constant time, when the backing array is long enough. The actual sorting is in (n log(n)).

According to the docs, adding an item to a TreeSet is in (log n). You do this n times, so overall time complexity is (n log(n)).

However Collections.sort seems faster in practice.

This code snippet prints timeArray: 380 and timeTree: 714.

import java.util.Collections;
import java.util.ArrayList;
import java.util.TreeSet;
import java.util.Random;

class Test {
    public static void main(String[] args) {
        int steps = 1000000;    // one million lines

        System.out.print("timeArray: ");
        System.out.println(timeArray(steps));
        System.out.print("timeTree: ");
        System.out.println(timeTree(steps));
    }

    private static long timeArray(int steps) {
        long t1 = System.currentTimeMillis();

        ArrayList<Integer> arr = new ArrayList<>();
        Random rnd = new Random();

        for (int i = 0; i < steps; i++) {
            arr.add(rnd.nextInt());
        }
        Collections.sort(arr);

        return System.currentTimeMillis() - t1;
    }

    private static long timeTree(int steps) {
        long t1 = System.currentTimeMillis();

        TreeSet<Integer> tree = new TreeSet<>();
        Random rnd = new Random();

        for (int i = 0; i < steps; i++) {
            tree.add(rnd.nextInt());
        }

        return System.currentTimeMillis() - t1;
    }
}

is it faster to create a SortedSet (of objects) and insert elements to it or create an ArrayList and sort it afterwards?

1 Answers1