Оптимизировать код с 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 в PresidentWithStates TreeSet, если это не ключ в reversedMap, и когда я его распечатываю, мне нужен отсортированный порядок. Должен ли я использовать TreeSet и сортировать по ходу или я должен просто использовать вместо него arraylist и сортировать в конце. Я видел похожий вопрос по этому поводу, но этот человек не постоянно добавлял элементы, как я.

Редактировать: нет дубликатов

Answer 1

Давайте разберем время выполнения:

ArrayList:

• 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)

TreeSet:

• 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 становится быстрее, чем опция сортировки действительно что-то для сравнения.