ArrayList add (index, object) сложность add (object)

Мне был задан следующий небольшой вопрос с множественным выбором в моем классе APCS относительно добавления элементов в ArrayList, и хотя один ответ кажется мне интуитивно правильным (выбор B), Я не совсем уверен, является ли это на самом деле правильно или что на самом деле происходит за кулисами производительности мудрыми:ArrayList add (index, object) сложность add (object)

//Consider the following methods 
public static List<Integer> process1(int n) { 
    List<Integer> someList = new ArrayList<Integer>(); 
    for (int k = 0; k < n; k++) { 
     someList.add(new Integer(k)); 
    } 
    return someList; 
} 
public static List<Integer> process2(int n) { 
    List<Integer> someList = new ArrayList<Integer>(); 
    for (int k = 0; k < n; k++) { 
     someList.add(k, new Integer(k)); 
    } 
    return someList; 
} 

//Which of the following best describes the behavior of process1 and process2? 
//(A) Both methods produce the same result and take the same amount of time 
//(B) Both methods produce the same result and process1 is faster than process2 
//(C) The two methods produce different results and process1 is faster than process2 
//(D) The two methods produce different results and process2 is faster than process1

Примечание: Я сделал тест оба метода на моем компьютере, используя достаточно большие параметры, и оба весьма близки но метод 1 кажется немного более быстрым. Кроме того, это не проблема, домашнее задание быть включен или что-нибудь, так что нет необходимости испытывать беспокойство о предоставлении мне с ответами :)

источник

2016-03-11 Nick

Я думаю, что в методе 'process2' вы хотите протестировать с помощью' someList.add (0, new Integer (k)); 'вместо' someList.add (k, new Integer (k)); '. Тогда вы можете заметить разницу. Поскольку 'add (int, element)' будет 'перемещает элемент в данный момент в этой позиции (если есть) и любые последующие элементы вправо'. На мой взгляд, это будет O (n). С текущим кодом вы всегда добавляете элемент в следующий элемент, который доступен, и я думаю, поэтому номера производительности одинаковы для обоих методов. Где «add (element)» имеет сложность O (1). –

public boolean add(E e) { 
     ensureCapacity(size + 1); // Increments modCount!! 
     elementData[size++] = e; 
     return true; 
}

против

public void add(int index, E element) { 
     rangeCheckForAdd(index); 

     ensureCapacity(size+1); // Increments modCount!! 
     System.arraycopy(elementData, index, elementData, index + 1, 
          size - index); 
     elementData[index] = element; 
     size++; 
    }

так это выглядит, как метод имеет больше кода, чтобы сделать в дополнение к общему коду, совместно используемому как

источник

2016-03-11 05:23:53

От the JDK source (воспроизведенный в ответе @ ScaryWombat), кажется, что первый будет немного быстрее.

В контексте, System.arraycopy на самом деле ничего не сделает, но звонок будет по-прежнему выполнен. В противном случае они по существу идентичны. Первый имеет один дополнительный вызов функции, поэтому, вероятно, будет крошечный бит медленнее (увеличенный большим n).

источник

2016-03-11 05:27:13 andars

А, я вижу, я решил, что это должен был сделать какой-то дополнительный (хотя и пустой в этом случае) метод звонит за кулисами – Nick

ArrayList add (index, object) сложность add (object)

ответ

Смежные вопросы