创建一个（对象的）SortedSet 并向其中插入元素更快，还是创建一个ArrayList 然后对其进行排序更快？

Question

我的文件中有一百万行。从每一行创建一个对象并将其添加到集合中。compareTo()必须使用类的自定义方法对集合进行排序。

目前我ArrayList按照阅读顺序将对象添加到 an 中，然后执行Collections.sort().

制作 TreeSet 会更快吗？

Answer 1

两种方法都需要 (n log(n)) 时间：向 an 中添加一项的ArrayList最坏情况为 (n)，但当后备数组足够长时，通常会在恒定时间内完成。实际的排序是在(n log(n))中。

根据文档，向 a 添加一个项目TreeSet是 (log n)。您执行此操作 n 次，因此总体时间复杂度为 (n log(n))。

然而Collections.sort在实践中似乎更快。

此代码片段打印timeArray: 380和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;
    }
}