创建一个 SortedSet（对象）并向其插入元素或创建一个 ArrayList 并在之后对其进行排序是否更快？

Question

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

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

做一个TreeSet会不会更快？

Answer 1

两种方法都在 (n log(n)) 时间内：将一个项目添加到 ArrayList 的最坏情况为 (n)，但通常在常数时间内完成，当后备数组为足够长了。实际排序在 (n log(n)).

根据 docs，将项目添加到 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;
    }
}

创建一个 SortedSet（对象）并向其插入元素或创建一个 ArrayList 并在之后对其进行排序是否更快？

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

java

sorting

arraylist