ArrayList. движок.

 
 
 
Зарегистрирован:28.11.10
Откуда:
Сообщения:32
Вопрос возник через непонимания фундаментов построения ArrayList.
при создании ArrayList list = new ArrayList(); // без ensureCapasity(int n)
и заполнении обєктами for(int i = 0; i < 100 * 1000; i++) list.add(new Object()); // добавление в конец масива
операция занимает от 0 до 16 милисекунд (мгновенно).
при формировании списка следующим способом: for(int i = 0; i < 100 * 1000; i++) list.add(0, new Object()); // добавление в начало списка
операция занимает 9150 милисекунд.
Вопрос:
Так как "движок" ArrayList - обычный массив(array[]) - я понимаю, почему так много времени занимает операция add(0, new Object()); (уничтожение предедущего массива, создание нового).
Но как к сущестующему массиву array = new arra[20] можно додать (розширить массив) 21-ый елемент Не Уничтожая предыдущего ??

И вопрос по ensureCapasity(int n):
если создать new ArrayList(100*1000) то добавление елемента в конец листа занимает от 0 до 16мс, а в начало - 9255мс.
Где можно реально увидеть ефект от использования ensureCapasity(int n) ??
 
 
Зарегистрирован:25.06.09
Откуда:Ukraine
Сообщения:87
При добавлении в конец происходит следующий процесс:
* если в массиве есть место для еще одного элемента то он просто добавляется
* если же места нет то создается новый массив (побольше), старые айтемы копируются в него, новая добавляется в конец.

При добавлении элемента не в конец (в начало в нашем случае) все элементы >= index передвигаются на одну позицию дальше. И чем их больше тем дольше времени занимает операция копирования.

Вот, смотрите исходик:
public void add(int index, E element) {
	if (index > size || index < 0)
		throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

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


Quote:
Но как к сущестующему массиву array = new arra[20] можно додать (розширить массив) 21-ый елемент Не Уничтожая предыдущего ??

Вы учитывайте то что массив расширяется не при каждом добавлении. Реально существует массив больше чем мы положили элементов. Когда же его начинает нехватать он увеличивается не на 1. А по формуле:

int newCapacity = (oldCapacity * 3)/2 + 1;


См. ensureCapacity метод.

Может Вам стоит использовать LinkedList? Там операция добавления в начало занимает O(1). Еще вариант при заполнении массива добавлять элементы в конец, а потом его перевернуть.

"Профессиональный разработчик отличается от "кодера" тем, что он понимает, что происходит."
Евгений Матюшкин
 
 
Зарегистрирован:28.11.10
Откуда:
Сообщения:32
Большое спасибо за ответ.
System.coppyarray() - рулет. Компилятор автоматически понимает, что создавать еще один массив на основании текущего "+" один елемент - пустая трата ресурсов.

Можно сразу вопрос:
гди вы берете информацию о том, что творится в методе add(E e) ??
в апи Оракла download.oracle.com/javase/6/docs/api/ - не написано.
есть какой-то сайт-аналог?
(в апи самой Джавы лезть не хочу)
 
 
Зарегистрирован:03.06.10
Откуда:Москва, Россия
Сообщения:6506
vehpsr:
Можно сразу вопрос:
гди вы берете информацию о том, что творится в методе add(E e) ??
в апи Оракла download.oracle.com/javase/6/docs/api/ - не написано.
есть какой-то сайт-аналог?
(в апи самой Джавы лезть не хочу)


<JAVA_SDK_INSTALL_DIR>/src.zip

Неожиданно, правда? :)

P.S. А у меня вообще полные исходники, включая закрытые пакеты и native-код. Берется там же, у Oracle, по лицензии JRL.

С уважением,
Евгений aka Skipy
www.skipy.ru
P.S. Я НЕ решаю задачи ЗА других!
 
 
Зарегистрирован:25.06.09
Откуда:Ukraine
Сообщения:87
vehpsr:

Можно сразу вопрос:
гди вы берете информацию о том, что творится в методе add(E e) ??
в апи Оракла download.oracle.com/javase/6/docs/api/ - не написано.
есть какой-то сайт-аналог?
(в апи самой Джавы лезть не хочу)

Как уже сказали в поставке JDK есть архив. Очень удобно Еклипсу указать путь к нему, тогда просмотр исходников в Еклипсе становится очень удобным.

"Профессиональный разработчик отличается от "кодера" тем, что он понимает, что происходит."
Евгений Матюшкин
 
 
Зарегистрирован:28.11.10
Откуда:
Сообщения:32
great tnx!
будем знать, будем пользоватся.
 
Модераторы:Петрsgdreadмсье клоц
Сейчас эту тему просматривают:Нет