java - 用 ArrayList 或 TreeSet 优化代码？

Question

TreeMap<String,ArrayList<String>> statesToPresidents = new TreeMap<String,ArrayList<String>>();
    TreeMap<String,String> reversedMap = new TreeMap<String,String>();
    TreeSet<String> presidentsWithoutStates = new TreeSet<String>();
    TreeSet<String>statesWithoutPresidents = new TreeSet<String>(); while (infile2.ready())
    {
        String president = infile2.readLine();
        if (reversedMap.containsKey(president)==false)
            presidentsWithoutStates.add(president);
    }

    infile2.close();

    System.out.println( "\nThese presidents were born before the states were formed:\n");  // DO NOT REMOVE OR MODIFY

    // YOUR CODE HERE TO PRINT THE NAME(S) Of ANY PRESIDENT(s)
    //  WHO WERE BORN BEFORE THE STATES WERE FORMED = 10%

    Iterator<String> iterator = presidentsWithoutStates.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }

我想知道如果我使用 ArrayList 而不是 TreeSet，我的程序是否会运行得更快。如果字符串 president 不是 reversedMap 中的键，我将它添加到 presidentWithoutStates TreeSet 中，当我打印出来时，我需要它排序。我应该使用 TreeSet 并边走边排序，还是应该只使用 arraylist 而不是在最后排序。我看到了一个类似的问题，但那个人并没有像我一样不断添加元素。

编辑:没有重复

Answer 1

让我们分解一下运行时间:

数组列表:

• n 插入每个都分摊 O(1)，给我们 O(n)

• 排序需要 O(n log n)，假设您使用内置的 Collections.sort，或者 O(n log n ) 排序算法。

• 遍历它需要 O(n)

总计 = O(n + n log n) = O(n log n)

树集:

• n 插入每个 O(log n)，给我们 O(n log n)。

• 遍历它需要 O(n)

总计 = O(n log n + n) = O(n log n)

结论:

渐近地，我们有相同的性能。

在实践中，ArrayList 可能会稍微快一些。

我为什么这么说？好吧，让我们假设它不是。然后我们可以使用 TreeSet 对数组进行排序，比专门用于排序的方法更快(不必插入到 ArrayList 中的节省相当小)。这似乎违反直觉，不是吗？如果这是(始终)正确的，Java 开发人员会简单地用 TreeSet 替换该方法，不是吗？

可以分析与排序和 TreeSet 相关的常数因子，但这可能相当复杂，而且程序运行的条件也会影响常数因子，因此它可以准确地说。

重复注意事项:

以上假定没有任何重复项。

如果有重复，你绝对不应该做一个contains检查你是否要使用一个ArrayList，而是在之后做重复删除(这可以通过简单地忽略排序后迭代期间相同的连续元素来完成)。应该避免 contains 检查的原因是因为它需要 O(n)，这可能会使整个事情变成 O(n²) .

如果有很多重复项，TreeSet 可能会更快，因为它只需要 O(n log m)，其中 m是重复的数量。排序选项不会如此直接地处理重复项，因此，除非 m 非常小，或者您很幸运，最终仍会采用 O(n log n)。

TreeSet 变得比排序选项更快的确切点确实需要进行基准测试。