Com*_*tix 1 java optimization arraylist treeset data-structures
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 不是 returnedMap 中的键，则将其添加到 PresidentWithoutStates TreeSet 中，并且当我将其打印出来时，我需要对其进行排序。我应该使用 TreeSet 并进行排序，还是应该使用数组列表并在最后进行排序。我看到了一个类似的问题，但那个人并没有像我一样不断添加元素。
编辑：没有重复项
让我们分解一下运行时间：
\n\n数组列表：
\n\nn插入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\nn插入O(log n)每一个，给我们O(n log n).
迭代它需要O(n)
总计 = O(n log n + n)=O(n log n)
结论：
\n\n渐近地，我们有相同的性能。
\n\n实际上，ArrayList可能会稍微快一些。
我为什么这么说呢？好吧，我们假设事实并非如此。然后，我们可以使用TreeSet比专门对数组进行排序的方法更快地对数组进行排序（不必插入所节省的空间ArrayList相当小）。这似乎违反直觉，不是吗？如果这是（始终）正确的，Java 开发人员只需将该方法替换为TreeSet，不是吗？
人们可以分析与排序和 相关的常数因子TreeSet，但这可能相当复杂，并且程序运行的条件也会影响常数因子，因此它不可能准确。
关于重复的注意事项：
\n\n上面假设没有任何重复项。
\n\n如果存在重复项，您绝对不应该检查contains是否要使用 an ArrayList，而是随后进行重复项删除（这可以通过简单地忽略排序后迭代期间相同的连续元素来完成）。contains应避免检查的原因是因为它需要O(n)，这可能会使整个事情变得需要O(n\xc2\xb2)。
如果有很多重复项，TreeSet可能会更快，因为它只需要O(n log m)，其中m是重复项的数量。排序选项不会如此直接地处理重复项，因此，除非m非常小，或者您很幸运，否则最终仍然会采用O(n log n).
TreeSet比排序选项更快的确切点确实需要进行基准测试。